Suppose I have the following optimization problem:
\begin{align}
\min &f(x) \\
& f_1(x) \leq 0 \\
& \vdots \\
& f_k(x) \leq 0 \\
& g_(x) = 0 \\
\end{align}
where $f, f_1,…,f_k$ are convex functions, and $g$ is an affine function. If I write out the lagrangian, we have:
$$ L(x, \lambda, \rho) = f(x) + \sum^k_{i=1}\lambda_if_i(x) + \rho g(x) $$
where $\lambda = [\lambda_1, \cdots, \lambda_k]^T$. If we have $\lambda_i \geq 0$ ($0 \leq i \leq k$), then we achieve the well known inequality:
$$ L(x, \lambda, \rho) \leq f(x),$$
and when we minimize $L$ over $x$ we obtain the dual of $f$ s.t :
$$ d(\lambda, \rho) = \inf_x (L(x, \lambda, \rho)) \leq f(x).$$
My question is that if $\lambda_i$ is not necessarily positive, then this inequality doesn't necessarily hold, then why does $\lambda_i$ have to be positive and why do we need this inequality to hold?
Best Answer
We need the $\lambda_i$s positive in order to penalize a violation of the constraints $f_i(x)\leq 0$. More precisely, if they were negative, minimizing $L$ would likely give $x$s for which $f_i(x)>0$ (because then $\lambda_if_i(x)<0$ making $L$ smaller) which is in violation to our primal problem. The final inequality holds by construction of the $L$. All of this is much nicer explained in
https://www.google.com.sg/url?sa=t&source=web&rct=j&url=http://www.net.in.tum.de/fileadmin/TUM/NET/NET-2011-07-2/NET-2011-07-2_20.pdf&ved=0ahUKEwjjgNuBqMXKAhWTBo4KHetBAHwQFggzMAU&usg=AFQjCNFwWb2H6N8SM1ITLlnkoZ43g1Zkpw