# How to use Karush-Kuhn-Tucker (KKT) conditions in inequality constrained optimization

I am trying to understand how to use the Karush-Kuhn-Tucker conditions, similar as asked but not answered in this thread.

Assume the target function is given by $f(x)$, where $x$ a vector. Let $g(x) \ge 0$ be an inequality constraint under which we wish to maximize $f$.

The Lagrange function is given by $L(x,\lambda)=f(x)+\lambda g(x)$. From a textbook I know that I have to maximize this function "with respect to the conditions":

$$g(x) \ge 0 \\ \lambda \ge 0 \\ \lambda g(x) = 0$$

Now I do not fully understand what this means. Does this mean I have to maximize $L$ as if $g(x)=0$ and then I 'check' whether the three conditions are met?

An example. Let $f(x)= 1 - x_1^2 - x_2^2$ and $g(x)= 1-x_1-x_2$. We find

$$\nabla_x L = 2 \begin{bmatrix} -1 & 0 \\ 0 & -1 \\ \end{bmatrix} x + \lambda \begin{bmatrix} -1 \\ -1 \\ \end{bmatrix} =0$$

$$\nabla_{\lambda} L = \begin{bmatrix} -1 \\ -1 \\ \end{bmatrix} x + 1 = 0$$

From here we can simplify to find $\lambda=-1$ and

$$x=\begin{bmatrix} 1/2 \\ 1/2 \\ \end{bmatrix}$$

We can verify $g(x) = 0$ as well as $\lambda g(x) = 0$ as required. However, $\lambda<-1$. So it seems the optimizations 'failed', but I am not sure what this means. It seems to suggest we found a minimum? Please help me with how to work with these constraints.

• How are you simplifying to get $\lambda = -1$? Oct 4, 2016 at 20:42
• @measure_theory I forgot to add the zero constraints. Does this clarify it? Oct 4, 2016 at 20:43

Think about what an inequality constraint means for optimality:

• either the optimum is away from the boundary of the optimization domain, and so the constraint plays no role;
• or the optimum is on the constraint boundary. In this case $f$ has a local minimum if the "downhill direction" is directly opposed to the constraint: $$\nabla f = \lambda \nabla g$$ for some positive $\lambda$. (Consider that if $\nabla f$ is merely parallel to $\nabla g$, but has opposite direction, then you can lower $f$ by moving slightly inside the domain -- separating from the constraint boundary. And of course if $\nabla f$ and $\nabla g$ are not parallel, you can decrease $f$ either by sliding along the constraint boundary, or moving inside the domain.)

This either-or condition is usually called complementarity and the difficult part of solving an inequality-constrained minimization problem is figuring out the status of each constraint: classifying it either as inactive (first case above, where $g(x) > 0$ at the optimum) or active (second case above, where $g(x) = 0$.)

The trio of conditions \begin{align*} g(x) &\geq 0\\ \lambda &\geq 0\\ g(x)\lambda &= 0 \end{align*} is just a clever way of encoding that every inequality constraint must be either active or inactive.

As a practical matter, you can solve the optimization problem by trying all possible active sets: i.e., for a single constraint, try solving the problem assuming the constraint is active, and solve it again assuming the constraint is inactive. Check which of the solutions are valid, as you suggest in your post.

Of course for large numbers $n$ of inequality constraints this method doesn't scale well, since there are $2^n$ possible active sets. Sophisticated numerical algorithms exist which try to deal with this.

Keywords for further study: active set methods, interior point methods.

• If I understand correctly, it would be adequate to characterize an inactive constraint as $\lambda=0$ and an active constraint as $\lambda \ne 0$? Thus in the example above for $\lambda=0$ we find a solution $x=(0,0)^T$ which is valid given the other conditions. So this is a solution, whereas for the case of $\lambda \ne 0$ we have $\lambda=-1$ in the example which is not a valid solution. Is this reasoning correct? Oct 4, 2016 at 22:27
• Yes, that sounds right. Oct 4, 2016 at 22:29
• So this is actually the interplay of conditions 1 and 3. If $\lambda=0$ then $g(x)\lambda = 0$ and hence the condition is met. Under $\lambda=0$, $\nabla L= \nabla f(x)=$ only. If $\lambda \ne 0$ the third condition requires us to have $g(x)=0$ and hence we are left with a simple Lagrangian multiplier problem. Oct 4, 2016 at 22:33