Is there any relationship between KKT and duality?

Question

I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.

Answer 1

KKT and duality are indeed closely related. To demonstrate this, I will look at a convex minimization problem in which all functions are convex and smooth. I will make use of Lagrange duality. Linear programming duality is just a special case of Lagrange duality applied to linear programs.

Consider the following convex minimization problem

\begin{align} p^* = \min_x & ~f(x)\\ \text{s.t.} & ~g_i(x) \le 0 & \forall i = 1,\dots,m \end{align}

which we will call the primal problem.

The Lagrangian dual problem is given by \begin{equation} d^* = \max_{\lambda \ge 0} \min_x\left\{ f(x) + \sum_{i=1}^m \lambda_i g(x)\right\}. \end{equation}

Let $p$ be the value of the primal problem for a given $x$, and let $d$ be the value of the dual problem for a given $\lambda$. By definition, $p \ge p^*$ (due to the minimum), $d \le d^*$ (due to the maximum), and $p \ge d$ (by weak duality).

It follows that if we can find an $x$ and a $\lambda$ such that $p=d$, then it must be that $p=p^*$ and $d=d^*$. That is, we have found the optimal solution! By strong duality, we know that this is possible for convex problems (given some technical conditions).

Goal: find $x$ and $\lambda$ such that $p = d$.

1. The $x$ that we find should be feasible for the primal problem, or $p$ would be considered to have value $\infty$. So we need primal feasibility: $g_i(x) \le 0$ $\forall i = 1,\dots,m$.
2. In the same way, our $\lambda$ should be consistent with our definition of the dual problem. So we need dual feasibility: $\lambda \ge 0$.
3. For a given $\lambda$ in the dual problem, the $x$ in the dual problem should actually minimize $f(x) + \sum\limits_{i=1}^m \lambda_i g(x)$. Otherwise, we would be cheating. Due to convexity and smoothness, minimizing this function over $x$ is equivalent to finding a stationary point. So we add stationarity: $\nabla f(x) + \sum\limits_{i=1}^m \lambda_i \nabla g_i(x) = 0$.
4. Now that everything is properly defined, we just add the condition $p=d$: $f(x) = f(x) + \sum\limits_{i=1}^m \lambda_i g(x)$, or equivalently $\sum\limits_{i=1}^m \lambda_i g(x) = 0$.

If you meet the above conditions, you are guaranteed to have found an optimal solution (in the case of strong duality).

Note that the above conditions are almost the KKT conditions. To arrive at the KKT conditions, we state condition 4. slightly stronger.

4. ALTERNATIVE: By conditions 1. and 2. it follows that $\lambda_i g_i(x) \le 0$. By condition 4. we have $\sum\limits_{i=1}^m \lambda_i g(x) = 0$. It follows immediately that all $\lambda_i g_i(x)$ must be equal to 0. We call this complementary slackness.

To summarize

In the convex case, the KKT conditions are neccesary and sufficient conditions for a primal dual pair $(x,\lambda)$ to obtain zero duality gap $p=d$, which implies optimality.