Constrained Optimization Lagrangian

Karush-Kuhn-Tucker Conditions

Karush-Kuhn-Tucker (KKT) conditions generalize Lagrange multipliers from equality-constrained problems to constrained optimization problems with both equality and inequality constraints.

The usual minimization form is:

$$\begin{array}{rl}\underset{x}{\min }& f(x)\\ \text{s.t.}& g_i(x)\le 0,i=1,\dots ,m\\ & h_j(x)=0,j=1,\dots ,p\end{array}$$

The Lagrangian is:

$$\mathcal{L}(x,\lambda ,\nu )=f(x)+\sum _{i=1}^m{\lambda }_i{g}_i(x)+\sum _{j=1}^p{\nu }_j{h}_j(x)$$

where:

• ${\lambda }_i$ are multipliers for inequality constraints
• ${\nu }_j$ are multipliers for equality constraints

Conditions

At an optimal point $x^{\ast }$, the KKT conditions are:

1. Stationarity

$${\nabla }_x\mathcal{L}(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })=0$$

The gradient of the objective is balanced by the gradients of the active constraints.

2. Primal feasibility

$$g_i(x^{\ast })\le 0,h_j(x^{\ast })=0$$

The solution must satisfy the original constraints.

3. Dual feasibility

$${\lambda }_i^{\ast }\ge 0$$

For a minimization problem with constraints written as $g_i(x)\le 0$, inequality multipliers must be nonnegative.

4. Complementary slackness

$${\lambda }_i^{\ast }{g}_i(x^{\ast })=0$$

This is the key idea for inequalities:

• If a constraint is inactive, $g_i(x^{\ast })<0$, then ${\lambda }_i^{\ast }=0$
• If ${\lambda }_i^{\ast }>0$, then the constraint must be active, so $g_i(x^{\ast })=0$

Intuition

KKT says that at the optimum, no feasible local movement can improve the objective.

An inactive inequality constraint should not affect the solution, so its multiplier becomes $0$. An active inequality constraint acts like an equality constraint at the boundary, so it can have a nonzero multiplier.

The multiplier ${\lambda }_i$ can be interpreted as a shadow price: how much the optimal value changes if the constraint is relaxed slightly.

When KKT Is Enough

KKT conditions are necessary for many smooth constrained optimization problems, assuming a constraint qualification holds.

For convex optimization, KKT becomes especially powerful:

• If $f$ and $g_i$ are convex and $h_j$ are affine, then any point satisfying KKT is globally optimal.
• If Slater’s condition holds, then KKT conditions are also necessary.

So for convex optimization, solving KKT often means solving the original optimization problem.

Example

Minimize $x^2$ subject to $x\ge 1$.

Rewrite the constraint in the standard form:

$$1-x\le 0$$

The Lagrangian is:

$$\mathcal{L}(x,\lambda )=x^2+\lambda (1-x)$$

KKT:

$$2x-\lambda =0$$ $$1-x\le 0,\lambda \ge 0$$ $$\lambda (1-x)=0$$

The solution is $x^{\ast }=1$ and ${\lambda }^{\ast }=2$.

The unconstrained minimum would be $x=0$, but that violates the constraint. The constraint is active at the solution, so its multiplier is nonzero.

Common Sign Mistake

The sign of $\lambda$ depends on how the constraint is written.

For minimization:

• If using $g_i(x)\le 0$, then ${\lambda }_i\ge 0$
• If using $g_i(x)\ge 0$, then ${\lambda }_i\le 0$

Pick one convention and keep it consistent.

Related

• Constrained Optimization
• Method of Lagrange
• Convex Optimization
• Quadratic Programming