Karuch-Kuhn-Tucker Conditions

The Karuch-Kuhn-Tucker (KKT) conditions are first order necessary conditions for finding the solution of an optimization problem in the form $$\begin{array}{rl}\underset{x}{\min }& f(\mathbf{x})\\ \text{s.t.}& \mathbf{g}(\mathbf{x})\le 0\\ & \mathbf{h}(\mathbf{x})=0.\end{array}$$ Furthermore, they are also sufficient conditions for convex problems, i.e. those where $\mathbf{f}(\mathbf{x})$, $\mathbf{g}(\mathbf{x})$ are convex and $\mathbf{h}(\mathbf{x})$ is affine (linear) [Boyd2004].

The conditions are as follows:

• stationarity $$\nabla f(\mathbf{x})+{\mathbf{\mu }}^{\top }\nabla \mathbf{g}(\mathbf{x})+{\mathbf{\lambda }}^{\top }\nabla \mathbf{h}(\mathbf{x})=0$$ (The linear combination of the constraints' gradients has to be equal to the objective function's gradient.)

• primal feasibility $$\begin{array}{r}\mathbf{g}(\mathbf{x})\le 0\\ \mathbf{h}(\mathbf{x})=0\end{array}$$ (Constraints of the stated optimization problem have to be satisfied.)

• dual feasibility $$\mathbf{\mu }\ge 0$$ (For a given $\mathbf{x}$, the columns of $\nabla \mathbf{g}(\mathbf{x})$ define a polyhedral cone in which ${\mathbf{\mu }}^{\top }\nabla \mathbf{g}(\mathbf{x})$ must lie.)

• complementary slackness $${\mathbf{\mu }}^{\top }\mathbf{g}(\mathbf{x})=0$$ (If $\mathbf{x}$ lies inside the feasible set w.r.t to the condition $\mathbf{g}(\mathbf{x})<0$, then $\mathbf{\mu }=0$ and therefore ${\mathbf{\mu }}^{\top }\nabla \mathbf{g}(\mathbf{x})=0$.)