For an optimization problem
$$ \begin{align} \min_{x} \quad & f(x)\\ \nonumber \text{subject to } \quad & h(x) \le \vec 0\\ \quad & l(x)=\vec 0\\ \end{align} $$
the four KKT conditions are
- Stationarity: $\vec 0 = \nabla f(x) + u^T \nabla h(x) + v^T \nabla l(x)$
- Complementary slackness: $u^T h(x) = 0$
- Primal feasibility: $h(x) \leq \vec 0$ and $l(x) = \vec 0$
- Dual feasibility: $u \geq \vec 0$
Under strong duality (Slater's condition),
$$\begin{align} f(x^*) & = \min_{x\in\mathbb{R}^n} f(x) + u^{*T} h(x) + v^{*T} l(x)\tag{1}\label{1}\\ & \leq f(x^*) + u^{*T} h(x) + 0 \\ & \implies \\ 0 & \leq u^{*T} h \end{align}$$
That is, $0 \leq u^T h$, and from primal and dual feasibility we know that $u^T h \leq 0$. So, complementary slackness is necessary for optimality under strong duality.
- Therefore, under strong duality, the complementary slackness condition is redundant. Is that correct?
Now, these slides say that the KKT conditions are always sufficient for optimality (i.e., under both strong and weak duality). But in a situation where Slater's condition isn't satisfied, it's possible for there to be a duality gap. Then the equals sign in $(\ref{1})$ becomes $\geq$, and we no longer can guarantee complementary slackness ($0 \leq u^T h$). We might get "lucky" and discover an optimal solution by searching for $x, u,$ and $v$ that satisfy the KKT conditions; on the other hand, the optimal solution might be noncomplementary.
- What would be an example of a problem that fails Slater's condition, but does have a solution that satisfies the KKT conditions (and, by sufficiency, is optimal)?
- In problems with a duality gap, is there still a way to use the KKT complementary slackness condition? (Maybe we could take the duality gap $f^* - g^* = - u^T h$ as a measure of "noncomplementarity" and try to minimize it.)