【OR-notes】互补松弛性

Complementary slackness

Assuming that the strong duality holds, and $x^{\ast }$ is the primal optimal, and $(x^{\ast },v^{\ast })$ is dual optimal. Then $f_0(x^{\ast })=g(x^{\ast },v^{\ast })={\inf }_{x\in D}(f_0(x)+{\sum }_{i=1}^m{\lambda }_i^{\ast }{f}_i(x)+{\sum }_{i=1}^p{\nu }_i^{\ast }{h}_i(x)\le f_0(x^{\ast })$.
when the = holds, we have
$$\sum _{i=1}^m{\lambda }_i^{\ast }{f}_i(x^{\ast })=0$$

KKT conditions

• primal inequal constraints: $f_i(x)\le 0,i=1,2,\dots ,m$.
• primal equal constraints: $h_i(x)=0,i=1,2,\dots ,p$.
• complementary slackness: ${\lambda }_i{f}_i(x)=0,i=1,2,\dots ,m$.
• $\nabla f_0(x)+\sum {\lambda }_i\nabla f_i(x)+{\nu }_i\nabla h_i(x)=0$.
• $\lambda \ge 0$.

if strong duality holds, and $x,\lambda ,\nu$ are optimal. they must satisfy KKT condition.

KKT for convex problem

If the primal problem is convex, then KKT is the condition for $\tilde{x},\tilde{\lambda },\tilde{\nu }$ is optimal and strong duality sufficient and necessary condition.

Proof for sufficient condition: From the first two conditions in KKT, $\tilde{x}$ is primal feasible point. $L(x,\tilde{\lambda },\tilde{\nu })$ is a convex problem, due to $\lambda >0$.
$$\begin{array}{rl}& L=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x)\\ g(\tilde{\lambda },\tilde{\nu })& =f_0(\tilde{x})+\sum {\tilde{\lambda }}_i{f}_i(x)+\sum {\tilde{\nu }}_i{h}_i(x)\\ & =f_0(\tilde{x})\end{array}$$
Due to $f_0(x)\ge p^{\ast }\ge g(\tilde{\lambda },\tilde{\nu })$, then $\tilde{x}$ is primal optimal, $\tilde{\lambda },\tilde{\nu }$ is dual optimal, and $d^{\ast }=p^{\ast }$ strong duality.

Demo

$$\begin{array}{rl}\min & \frac{1}{2}{x}^{\prime }Px+q^{\prime }x+t\\ s.t.& Ax=b\end{array}$$
where $P\in {\mathbb{S}}_{+}^n$.
The KKT condition is as follows:
$$\begin{array}{rl}& A{x}^{\ast }=b\\ & P{x}^{\ast }+q+A^{\prime }{\nu }^{\ast }=0\end{array}$$
that is
$$\left[\begin{array}{cc}P& A^{\prime }\\ A& 0\end{array}\right]\left[\begin{array}{c}{x}^{\ast }\\ {\nu }^{\ast }\end{array}\right]=\left[\begin{array}{c}-q\\ b\end{array}\right]$$

Demo2: Water-filling

$$\begin{array}{rl}\min & -\sum _{i=1}^n\log (x_i+{\alpha }_i)\\ s.t.& x\ge 0,1^{\prime }x=1\end{array}$$
KKT condition is as follows:
$$\begin{array}{rl}& x\ge 0,1^{\prime }x=1,{\lambda }_i\ge 0,{\lambda }_i{x}_i=0,i=1,2,\dots ,m\\ & -\frac{1}{x_i+{\alpha }_i}-{\lambda }_i+\nu =0\end{array}$$
we have
$$\begin{array}{rl}& {\lambda }_i=-\frac{1}{x_i+{\alpha }_i}+\nu \ge 0\\ & \nu \ge \frac{1}{{\alpha }_i+x_i}\\ & x_i(\nu -\frac{1}{{\alpha }_i+x_i})=0\end{array}$$
The solution can be obtained by analyzing the following cases:
case 1:
$$\nu <\frac{1}{{\alpha }_i}$$
if $x_i=0$, then $\nu \ge \frac{1}{{\alpha }_i}$ is contradicted to $\nu <\frac{1}{{\alpha }_i}$. $x_i>0,x_i=\frac{1}{\nu }-{\alpha }_i$.
case 2:
$\nu \ge \frac{1}{{\alpha }_i}\to$ contradiction.

As a result,
$$x_i=\{\begin{array}{rlr}& \frac{1}{\nu }-{\alpha }_i& {\alpha }_i\le \frac{1}{\nu }\\ & 0& {\alpha }_i>\frac{1}{\nu }\end{array}$$
that is, x i = max ⁡ { 0 , 1 ν − α i } x_i=\max\{0, \frac{1}{\nu}-\alpha_i\} xi​=max{0,ν1​−αi​} and $\sum x_i=1$.

Reference

B站 许志钦