1. Karush–Kuhn–Tucker (KKT) conditions

#math/KKT-condition#optimum-condition

1. Concept of KKT Condition

(1) problems for solve

The standard-form of optimization problem is given as ^[1] :

$$\begin{array}{}\text{(1.1.1)}& \boxed{{\displaystyle \begin{array}{rl}\text{minimize}& f(x),\\ s.t.& g_i(x)\le 0\\ & h_j(x)=0\end{array}}}\end{array}$$

Where $f(x)$ is objective, $g$ are inequality constraints.

Then the Karush-Kuhn-Tucker Condition^[1:1], Firstly, we can construct the following Lagrangian function :

$$\begin{array}{}\text{(1.1.2)}& \mathcal{L}(x,\mu ,\lambda )=f(x)+{\mu }^{T}g(x)+{\lambda }^{T}h(x)=\mathcal{L}(x,\alpha )\end{array}$$

Re-write (1.1.2) gives :

$$\begin{array}{}\text{(1.1.3)}& \mathcal{L}=\left[\begin{array}{cc}{\mu }^T& {\lambda }^T\end{array}\right]\left[\begin{array}{c}g(x)\\ h(x)\end{array}\right]={\alpha }^T\left[\begin{array}{c}g(x)\\ h(x)\end{array}\right]\end{array}$$

(2) The KKT condition

The Karush-Kuhn-Tucker Condition state the following sufficient and necessary conditions :

1. Sufficiency : If $(x^{\ast },{\alpha }^{\ast })$ is the saddle point of $L(x,\alpha )$ in $x\in X,\mu \ge 0$ then $x^{\ast }$ is an optimal vector for the optimization problem (1.1.1)
2. Necessity : Suppose $f(x)$ and $g_i(x)$, are convex in $X$ , and there exists :

$$\begin{array}{}\text{(1.2.1)}& x_0\in \text{relint}(X)\text{s.t.}g(x_0)<0\end{array}$$

that is, slater's condition^[2] holds, Then with an optimal vector $x^{\ast }$, for the optimization problem, there is a vector

$$\begin{array}{}\text{(1.2.2)}& {\alpha }^{\ast }=\left[\begin{array}{c}{\mu }^{\ast }\\ {\lambda }^{\ast }\end{array}\right]\end{array}$$

satisfying ${\mu }^{\ast }\ge 0$, and the $(x^{\ast }),\alpha$ is the saddle point of $\mathcal{L}(x,\alpha )$

(3) Necessary condition

For the part :

$$\begin{array}{}\text{(1.3.1)}& \underset{\alpha ,\beta \ge 0}{min}L(x,\mu ,\lambda )=f(x)+\sum _{i=1}^m{\mu }_i{g}_i(x)+\sum _{j=1}^k{\lambda }_j{h}_j(x)(g_i\le 0,h_j=0)\end{array}$$

then :

$$\begin{array}{}\text{(1.3.2)}& \boxed{{\displaystyle 0\in \partial \mathcal{L}(x^{\ast })=\partial f(x^{\ast })+\sum _{j=1}^l{\lambda }_j\partial h_j(x^{\ast })+\sum _{i=1}^m{\mu }_i\partial g_i(x^{\ast })=f(x)}}\end{array}$$

For minimizing $f(x)$, we have following conditions :

$$\begin{array}{}\text{(1.3.3)}& \boxed{{\displaystyle \{\begin{array}{ll}{h}_j(x^{\ast })=0g_i(x^{\ast })\le 0& \text{primary feasibility}\\ {\mu }_i(x^{\ast })\ge 0& \text{dual feasibility}\\ \sum _{i=1}^m{\mu }_i^{\ast }{g}_i(x^{\ast })=0& \text{Complementary Slackness}\end{array}}}\end{array}$$

The equation (1.3.2~3), or often (1.3.3) are called KKT condition

Complementary Conditions We note For (1.3.3), the KKT conditions for inequality boundaries are complementary conditions :

$${\xi }_j\ge 0x_j-{\alpha }_j\ge 0{\xi }_j(x_j-{\alpha }_j)=0$$

For an illustration, see [^3]

Feasibility :

• This is a necessary condition for finding the optimal solution, but it only holds true if the problem satisfies certain regularity (such as the Slater condition).
• For non-convex problems, points satisfying the KKT conditions may be local optima, saddle points, or even extreme points.

---

1. https://en.wikipedia.org/wiki/Karush–Kuhn–Tucker_conditions ↩︎ ↩︎

2. https://en.wikipedia.org/wiki/Slater's_condition ↩︎