KKT Conditions

334. KKT Conditions

Conditions that a solution must satisfy in order to be optimal for a nonlinear optimization problem

Conditions are necessary for optimality, and sufficient if:

is convex
are convex
linear

334.0.1. Setup

: objective function
: inequality constraints
: equality constraints

334.0.2. KKT Multipliers

We introduce:

: for each inequality constraint (Lagrange multipliers)
: for each equality constraint

The Lagrangian is:

For variables and constrains:

primal variables () and dual variables ()
equalities for dual feasibility
equalities for complementary slackness

334.0.3. KKT Conditions

At local optimum there exists multipliers () such that:

Stationarity

Minimization:

Stationarity is like a generalized version of “set the derivative to zero”, but accounting for the constraints

Primal feasibility

The solution must satisfy all the original constraints — it must lie inside the feasible region

Dual Feasibility

Complementary Slackness

Complementary slackness only applies to inequalities

Inactive (non-binding) constraint

The constraint does not affect the optimum
The feasible region is “loose” at the optimum — the optimum lies strictly inside it
Economically, the shadow price is zero: relaxing the constraint wouldn’t change the objective

Active (binding) constraint

The constraint is tight at the optimum — it holds with equality
is the shadow price:
- It measures how much the objective value would improve per unit relaxation of the constraint
  - The objective would decrease by per unit of relaxation (if convex)

Example

Step 1. Standardize constraints

Constraints already in the form for minimization

Sign convention

Step 2. Formulate Lagrangian

Step 3. Stationarity

Solve for :

Solve for

Candidate point:

Step 4. Primal Feasibility

Constraint:

Substitute and

Step 5. Dual Feasibility

Step 6. Complementary Slackness

Constraint:

Condition:

Candidate point:

Evaluate :

Substitute and

Solve:

But because of Dual Feasibility , so

Constraint is non-binding at optimum:

Step 7. Solve for Optimum

Step 8. Check Convexity

Example

Step 1. Standardize constraints

Constraints already in the form for minimization

Sign convention

Step 2. Formulate Lagrangian

Step 3. Stationarity

Solve for :

Candidate point:

Step 4. Primal Feasibility

Constraint:

Substitute and :

Step 5. Dual Feasibility

Step 6. Complementary Slackness

Constraint:

Condition:

Candidate point:

Evaluate :

Substitute and

Solve:

But because of Primal Feasibility, if , and , thus

Constraint is binding at optimum:

Step 7. Solve for Optimum

Step 8. Check Convexity

334.0.4. Calculating Lagrangian Multipliers

To find the multipliers () and the optimal point , solve the KKT system of equations:

Example

Retailer Maximizing Profit under a Capacity Constraint

A retailer sells product 1 and 2 with quantities and . For product the market-clearing prices are:

Where .

The retailer maximizes total profit subject to a capacity constraint:

Formulation

The objective is concave because

is positive semi-definite.

The unconstrained FOC solution is:

If , this solution is feasible.

Lagrangian

Introduce KKT multiplier for the inequality constraint:

KKT Conditions

1. Stationarity

2. Primal Feasibility

3. Dual Feasibility

4. Complementary Slackness

Solving KKT system

Case 1: Unconstrained ()

First-Order Condition

Set derivatives to 0 (stationarity)

Unconstrained Solution:

The second derivative check confirms it’s a maximum because:

Feasible if

Case 2: Binding Constraint ()

We now include the capacity constraint:

If it binds (active) then

Lagrangian

First-Order Condition

Set derivatives to 0 (stationarity)

When we take the derivative of the Lagrangian with respect to the multiplier we recover the constraint itself.

Solve system of equations

Solution:

Feasible if

Optimal Solution

Intuition:

If capacity is large enough, the retailer produces unconstrained quantities.
If is tight, the total production hits the limit, and the optimal quantities are shared according to the relative parameters

Example

This NLP is nonconvex

1️⃣ Lagrangian

Introduce multipliers for the inequalities. The Lagrangian is

The solution is a local maximum only if there exists such that

2️⃣ KKT Conditions

Primal feasibility

Dual Feasibility

Stationarity

Complimentary Slackness

3️⃣ Examine all 4 cases for

Case 1. ()

Step 1: Complementary Slackness

Since both multipliers are positive, the corresponding constraints must be active:

Solve this system two candidate points:

Step 2: Primal Feasibility

✅ Both satisfy primal feasibility.

Step 3: Stationarity / First-order conditions (DFF)

Plug each candidate point into the gradient equations and solve the system:

For :

Solving the system we get:

✅ Both dual feasibility satisfied.

For :

Solving the system we get:

✅ Both dual feasibility satisfied.

✅ Both and satisfy dual feasibility both are KKT points.

Case 2. ()

Step 1. Assumptions (Activity / Inactivity)

Constraint 1: Active ()
Constraint 2: Inactive ()

Step 2. Stationarity Condition

The Lagragian:

Compute the gradients with respect to and :

Since , the equations simplify to:

Simplify:

Step 3. Substitute into Active Constraint

Using and :

Two candidate solutions and :

Step 4. Solve for and enforce

Substitute into the stationarity condition:

For :

For :

So, the surviving candidate is:

Step 5. Check the (inactive) constraint 2 for primal feasibility

Constraint 2:

Plug and :

❌ This violates the inequality

❌ is rejected because it violates the inequality

❌ is rejected because it gives

Case 3. ()

Step 1. Assumptions (Activity / Inactivity)

Constraint 1: Inactive ()
Constraint 2: Active ()

Step 2. Stationarity Condition

The Lagragian:

Compute the gradients with respect to and :

Since , the equations simplify to:

Simplify:

Step 3. Substitute into Active Constraint

Substituting and :

Two candidate solutions and :

Substitute into the stationarity condition:

For :

For :

So, the surviving candidate is:

Step 5. Check the (inactive) constraint 1 for primal feasibility

Constraint 1:

Plug and :

✅ Satisfies primal feasibility. Constraint 1 is inactive (strict inequality), as required.

✅ is a valid KKT point under this assumption.

❌ is rejected because it gives

Case 4. ()

Step 1. Assumptions (Activity / Inactivity)

Both multipliers are zero:
No constraints are forced to be active by complementary slackness

Step 2. Stationarity Condition

With and , the stationarity equations simplify to:

Step 3. Stationary Check

Both equations and are impossible

No solution exists under this assumption

❌ No KKT points exist

4️⃣ Summary

and :
and :

These are the only candidates for local maxima (and thus global maxima)

Necessary, but not sufficient for non-convex NLPs

334.0.5. Sensitivity Analysis and Shadow Prices

Lagrange multipliers measure how senitive the objective function is to changes in the constraints

334.0.5.1. Shadow Prices

The shadow price of a constraint is the value of the corresponding Lagrange multiplier at the optimal solution:

It measures how much the objective function would improve if the constraint were relaxed by one unit. For example:

The corresponding shadow price tells us the change in the optimal objective due to this relaxation. The magnitude of the Lagrange multiplier reflects the influence of its associated constraint on the optimal solution.

	Constraint Status	Shadow Price ()	Impact on Objective
Binding / Active			Relaxing improves objective
Inactive / Slack			Relaxing has no effect

Example

Primal NLP

Lagrange Dual Program

Convexity

The Lagrange Dual Program function is always convex over

Weak Duality

Strong Duality

is the primal NLP is a “regular” convex program

Example

Optimal solution

Lagragian relaxation

Where

To solve the Lagrange dual program:

First-order condition:

Plugging into :

The Lagrangian dual program is to look for and to minimize

The Lagrange dual program:

is convex over :

Since:

and , is convex

To solve

Apply KKT conditions

cannot be binding (), because division by 0, so ignore it

Let be the Lagrange multiplier for , the Lagrange is

The KKT condition requires an optional solution to satisfy (FOC)

Suppose
- Implies
- requires
- requires , which is feasible
Suppose
- requires
- Plugging into results on which is impossible
The only KKT point is
Plugging into gives us which exactly equals

So strong duality holds,

334.0.6. Lagrange Duality and LP Duality

LP duality is a special case of Lagrange Duality

For a general LP

Where ( constraints and variables)

Let be the Lagrange multipliers, the Lagrange relaxation is

Because of equality constraint, is unrestricted in sign

Lagrange dual program

Search for that minimizes

Dual program is only meaningful if , because if for any , will be unbounded because we can increase to

Thus, no choice of that violates may be optimal to the Lagrange dual program

The Lagrange dual program

If satisfies thenwe know

The Lagrange dual program becomes

Which is exactly the dual LP of

Example

What are the leading principle minors of the Hessian matrix of the objective function?

2 and 4 ✅

✅

According to the FOC of the Lagragian, what is a necessary condition for an optimal solution

Case 1.

Constraint active:

FOC (gradient w.r.t. and ):

Substitute into active constraint

Find :

Which violates

Case 2.

✅

Case 2.

What is a local optimal solution to the nonlinear program?

✅

For a linear program, linear programming duality and Lagrange duality is equivalent (i.e., the dual programs obtained through the two ways are identical). ✅

For an unconstrained nonlinear program, the KKT condition is equivalent to the first-order condition. ✅

For an unconstrained nonlinear program, the KKT condition is necessary and sufficient. ✅