As part of an applied math class for biologists I am in which is partly concerned with optimization and duality we have been referred to a text to help us understand the concepts better. I do not understand the solution to one of the questions. It is question 5.13 from the pdf: https://see.stanford.edu/materials/lsocoee364a/hw5sol.pdf. I absolutely cannot figure out how they eliminated the dual multiplier $v_i$ for this portion of the solution. Also I do not understand what the notation $min\{0,4(c_i + a_{i}^T \mu\}$ means. Forgive me for I am not a math student. I am amazed I can even understand what a relaxation is and how it is used in duality. I may have used the wrong tags for that reason as well.
I am specifically stuck here:
The step before " in order to simplify this dual..." I believe to be...
$$ \max -\frac{1}{4\mu}\Sigma_{i=1}^n (c_i + a_{i}^T \mu - v_i)^2/ v_i $$ $$s.t. \text{ } v_i \geqq 0, \mu_i \geqq 0$$
Your dual problem is $$\max -b^\top \mu - \frac{1}{4}\sum_{i=1}^n\frac{(c_i+a_i^\top\mu-\nu_i)^2}{\nu_i} \quad \mbox{s.t.} \quad \mu \geq 0, \nu \geq 0. $$ Obviously the term $b^\top \mu$ does not depend on $\nu$. Hence, to further investigate the role of $\nu$ it is suffcient to consider the latter part of the objctive function, which is $$\max - \frac{1}{4}\sum_{i=1}^n\frac{(c_i+a_i^\top\mu-\nu_i)^2}{\nu_i} \quad \mbox{s.t.} \quad \mu \geq 0, \nu \geq 0.$$ Now, the idea is to focus on the single summands and to maximize those summands. The background is that if we maximize all summands, then we also maximize the whole sum. Thus, we consider (for fixed $\mu$) the summand for an arbitrary $i = 1,\ldots,n$ which leads to the mentioned problem $$ \sup -\frac{(c_i+a_i^\top\mu-\nu_i)^2}{\nu_i} \quad \mbox{s.t.} \quad \nu_i \geq 0.$$ We find out, that the term that we want to maximize (find the supremum of) has negative sign. Also both parts of the fraction are not negative. Hence, the supremum is definitely bounded (above) by $0$. As written in the solution we can now distinguish between two cases: If $c_i+a_i^\top\mu \geq 0$ then we can always find $\nu_i \geq 0$ such that $c_i+a_i^\top\mu - \nu_i = 0$ and hence the supremum is $0$.
If $c_i+a_i^\top\mu < 0$ then one can find out analytically (using first + second derivative) that the supremum is obtained for $\nu_i = -c_i+a_i^\top\mu$. More precisely, define $$\begin{align} g(\nu_i) := &-\frac{(c_i+a_i^\top\mu-\nu_i)^2}{\nu_i}\\ = &-\frac{(c_i+a_i^\top\mu)^2+\nu_i^2-2(c_i+a_i^\top\mu)\nu_i}{\nu_i}\\ = &-\frac{(c_i+a_i^\top\mu)^2}{\nu_i}-\nu_i+2(c_i+a_i^\top\mu). \end{align}$$ Then we have $$ \begin{align} g^\prime(\nu_i) &= \frac{(c_i+a_i^\top\mu)^2}{\nu_i^2}-1\\ g^{\prime\prime}(\nu_i) &= -\frac{2(c_i+a_i^\top\mu)^2}{\nu_i^3} \end{align}$$ This is all we need to find the global maximum: $$g^\prime(\nu_i) = 0 \Leftrightarrow \nu_i^2 = (c_i+a_i^\top\mu)^2 \Rightarrow \nu_i = -(c_i+a_i^\top\mu).$$ The sign is known since we have $\nu_i \geq 0$ and $c_i+a_i^\top\mu < 0$. Also, this choice of $\nu_i$ implies $\nu_i > 0$ and thus, $g^{\prime\prime}(\nu_i) < 0$. Hence, we have $$-\frac{(c_i+a_i^\top\mu-\nu_i)^2}{\nu_i} = -\frac{(c_i+a_i^\top\mu-(-c_i+a_i^\top\mu))^2}{-c_i+a_i^\top\mu} = 4(c_i+a_i^\top\mu) \leq 0$$ in this case. For this reason, we can write that the the supremum equals the minimum of those two terms from the case destinction above, i.e., $$ \sup_{\nu_i \geq 0} -\frac{(c_i+a_i^\top\mu-\nu_i)^2}{\nu_i} = \min \{0,4(c_i+a_i^\top\mu)\}.$$ (The minimum of those two terms is $0$ if $c_i+a_i^\top\mu \geq 0$ and $c_i+a_i^\top\mu$ if $c_i+a_i^\top\mu < 0$ - exactly what we found out above.)
As $\nu$ is no longer part of that term (of the minimum above), it can be eliminated from the dual problem when inserting the minimum for the summands. This finally leads to the dual problem $$\max -b^\top \mu + \sum_{i=1}^n \min \{0,c_i+a_i^\top\mu\} \quad \mbox{s.t.} \quad \mu \geq 0.$$