Consider the following optimization problem with convex $f_i$'s:

$$\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f_0(x) \\ & \text{subject to} & & f_i(x) \leq 0, i = 1, \dots, m \end{aligned} \end{equation*}$$

and the corresponding Lagrangian

$$L(x, \lambda) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x)$$

and its Lagrange dual over feasible domain $D$

$$\begin{equation*} \begin{aligned} g(\lambda) &= \inf_{x \in D} L(x, \lambda) \\ & = \inf_{x \in D} \left( f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) \right ). \end{aligned} \end{equation*}$$

Let $x^*$ and $\lambda^*$ be the primal and dual optimal points, respectively. Strong duality means that $f_{0}(x^*) = g(\lambda^*)$, which implies that $\sum_{i=1}^{m} \lambda_{i}^* f_i(x^*) = 0$ for $i = 1, \dots, m$.

The condition $\sum_{i=1}^{m} \lambda_{i}^* f_i(x^*) = 0$ for $i = 1, \dots, m$ is called complementary slackness, which is implied by strong duality.

It seems to me (though I may be wrong) that the converse is also true, in which case I'm not sure why there's a separate term for this condition. Can anyone help me understand what I'm missing? I know complementary slackness is also one of the KKT conditions, and am not sure how that fits in here.

EDIT: I think I found my mistake. My flawed proof of why I think complementary slackness implies strong duality follows.

As before, let $x^*$ and $\lambda^*$ be the primal and dual optimal points, respectively.

This means that $x^*$ minimizes $f_0(x)$ over its feasible domain $D$, and $\lambda^*$ maximizes the dual function $g(\lambda)$ subject to $\lambda \succeq 0$.

Then, $g(\lambda^*) = \inf_{x \in D} \left( f_0(x) + \sum_{i=1}^{m} \lambda^*_i f_i(x) \right ).$ Here I incorrectly thought that complementary slackness implies $\sum_{i=1}^{m} \lambda^*_i f_i(x) = 0$, and hence, $g(\lambda^*) = \inf_{x \in D} f_0(x) = f_0(x^*)$. But it looks like the value of $x$ that minimizes $g(\lambda^*)$ need not equal $x^*$, so I can't apply complementary slackness here.

Thus for strong duality to hold, I also need to satisfy the stationarity KKT condition (gradient of $L(x, \lambda^*)$ vanishes at $x^*$), which would show that $x^*$ is indeed the minimizer of $g(\lambda^*$) and hence, $g(\lambda^*) = f_0(x^*) + \sum_{i=1}^{m} \lambda^*_i f_i(x^*) = f_0(x^*)$.

  • $\begingroup$ 1) You should add somewhere that the $f_i$'s are convex. 2) Could you supply a reference that complementary slackness implies strong duality? That is true in case of LP, but I am not sure about it in general case. $\endgroup$ – user251257 Sep 15 '15 at 14:30
  • $\begingroup$ I think I figured out my mistake and edited my original question to reflect that. Thanks! $\endgroup$ – scip Sep 16 '15 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.