Karush-Kun-Tucker Conditions

Definition

By allowing inequality constraints, generalizes the method of Lagrange multiplier, which allows only equality constraints.

Given general problem $\underset{x}{\min }f(x)$ subject to $g(x)\le 0,h(x)=0$

The KKT conditions are

• Stationarity: $\nabla \mathcal{L}(x,\mu ,\lambda )=\nabla f(x)+\lambda \nabla h(x)+\mu \nabla g(x)=0$
• Primal feasibility: $h(x)=0,g(x)\le 0$
• Dual feasibility: $\mu \ge 0$
• Complementary slackness: $\mu g(x)=0$

Facts

The gradient of inequality constraint ${\nabla }_{x}g(x)$ and the gradient of the function ${\nabla }_{x}f(x)$ should be in opposite directions.

If ${\nabla }_{x}f(x)$ and ${\nabla }_{x}g(x)$ don’t have opposite directions, then there is the area(direction) decreasing both $f(x)$ and $g(x)$

For a problem with Strong Duality, $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are optimal $\Rightarrow$ $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ satisfy the KKT conditions

For a convex optimization, $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ satisfy the KKT condition $\Rightarrow$ Strong Duality holds

Proof Since $f(x),h(x),g(x)$ are all convex function, the Lagrangian primal function $\mathcal{L}(x,\mu ,\lambda )=f(x)+\lambda h(x)+\mu g(x)$ is also convex

Let $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ be the values satisfy KKT conditions. By the stationarity condition, $\nabla \mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=\nabla f(x^{\ast })+\lambda \nabla h(x^{\ast })+\mu \nabla g(x^{\ast })=0$ So, $x^{\ast }$ is a local minimum of $\mathcal{L}(x,\mu ,\lambda )$ and by the convexity, it is also global minimum Therefore, $\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\mathcal{L}(x,{\mu }^{\ast },{\lambda }^{\ast })=q({\mu }^{\ast },{\lambda }^{\ast })$^[Lagrange dual function]

Also, by the complementary slackness and primal feasibility conditions, ${\mu }^{\ast }g(x^{\ast })=0,h(x^{\ast })=0$ So, $\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })+\lambda h(x^{\ast })+\mu g(x^{\ast })=f(x^{\ast })$ Therefore, the dual optimal value and the primal optimal value is the same. In other words, satisfy the Strong Duality condition $q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })$

$\therefore x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are optimal

For a problem with Slater’s Condition (ensure Strong Duality and convexity), and $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ satisfy the KKT condition $\iff$ $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are optimal

Proof Let $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ be the primal and dual solutions

Since ${\mu }^{\ast },{\lambda }^{\ast }$ are the dual optimal, the dual optimal value $q({\mu }^{\ast },{\lambda }^{\ast })$ can be expressed as an expression in regard to $x$ $q({\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)=f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})$ where $\bar{x}:=\underset{x}{\mathrm{argmin}}\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)$

Since $x^{\ast }$ is a feasible value, the $q({\mu }^{\ast },{\lambda }^{\ast })$ with $x^{\ast }$, $\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ is always greater than or equal to the $q({\mu }^{\ast },{\lambda }^{\ast })$ with $\bar{x}$ $f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})\le f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })=\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })$ and by the constraints of Lagrangian primal function, $h(x)=0\Rightarrow {\lambda }^{\ast }h(x^{\ast })=0$ and $g(x)\le 0\wedge \mu \ge 0\Rightarrow {\mu }^{\ast }g(x^{\ast })\le 0$ So, $f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })\le f(x^{\ast })$

In summary $q({\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)=f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})\le \mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })\le f(x^{\ast })$

Since Slater’s Condition ensures Strong Duality $q({\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })$, the inequality become the equality $q({\mu }^{\ast },{\lambda }^{\ast })=\underset{x}{\min }\left(f(x)+{\lambda }^{\ast }h(x)+{\mu }^{\ast }g(x)\right)=f(\bar{x})+{\lambda }^{\ast }h(\bar{x})+{\mu }^{\ast }g(\bar{x})=\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })=f(x^{\ast })$ Therefore, $f(x^{\ast })+{\lambda }^{\ast }h(x^{\ast })+{\mu }^{\ast }g(x^{\ast })=f(x^{\ast })\Rightarrow {\mu }^{\ast }g(x^{\ast })=0$, so the complementary slackness condition is satisfied Also, $\underset{x}{\min }\mathcal{L}(x,{\mu }^{\ast },{\lambda }^{\ast })=\mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })\Rightarrow x=\underset{x}{\mathrm{argmin}}\mathcal{L}(x,{\mu }^{\ast },{\lambda }^{\ast })\Rightarrow \nabla \mathcal{L}(x^{\ast },{\mu }^{\ast },{\lambda }^{\ast })=\nabla f(x^{\ast })+\lambda \nabla h(x^{\ast })+\mu \nabla g(x^{\ast })=0$, so the stationary condition is satisfied Finally, since $x^{\ast },{\mu }^{\ast },{\lambda }^{\ast }$ are the primal and dual solutions, the constraints of Lagrangian primal and dual function, satisfy the primal and dual feasibility condition