KKT Conditions

337. 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

337.0.1. Setup

\begin{aligned} min_{𝑥 \in ℝ^{𝑛}} & 𝑓 (𝑥) \\ 𝑠 . 𝑡 . & 𝑔_{𝑖} (𝑥) \leq 0 \forall 𝑖 = 1, \dots, 𝑚 \\ ℎ_{𝑗} (𝑥) = 0 \forall 𝑗 = 1, \dots, 𝑝 \end{aligned}

$𝑓 (𝑥)$ : objective function
$𝑔_{𝑖} (𝑥)$ : inequality constraints
$ℎ_{𝑗} (𝑥)$ : equality constraints

337.0.2. KKT Multipliers

We introduce:

$𝜆_{𝑖} \geq 0$ : for each inequality constraint (Lagrange multipliers)
$𝜇_{𝑖} \in ℝ$ : for each equality constraint

The Lagrangian is:

ℒ︀ (𝑥, 𝜆, 𝜇) = 𝑓 (𝑥) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖} 𝑔_{𝑖} (𝑥) + \sum_{𝑗 = 1}^{𝑝} 𝜇_{𝑗} ℎ_{𝑗} (𝑥)

For $𝑛$ variables and $𝑚$ constrains:

$𝑛$ primal variables ( $𝑥$ ) and $𝑚$ dual variables ( $𝜆$ )
$𝑛$ equalities for dual feasibility
$𝑚$ equalities for complementary slackness

337.0.3. KKT Conditions

At local optimum $𝑥^{*}$ there exists multipliers ( $𝜆^{*}, 𝜇^{*}$ ) such that:

Stationarity

Minimization:

\nabla 𝑓 (𝑥^{*}) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖}^{*} \nabla 𝑔_{𝑖} (𝑥^{*}) + \sum_{𝑗 = 1}^{𝑝} 𝜇_{𝑗}^{*} \nabla ℎ_{𝑗} (𝑥^{*}) = 0

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

Primal feasibility

\begin{aligned} 𝑔_{𝑖} (𝑥^{*}) & \leq 0 \\ ℎ_{𝑗} (𝑥^{*}) & = 0 \end{aligned}

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

Dual Feasibility

𝜆_{𝑖} \geq 0 \forall 𝑖

Complementary Slackness

𝜆_{𝑖} 𝑔_{𝑖} (𝑥^{*}) = 0 \forall 𝑖

Complementary slackness only applies to inequalities

Inactive (non-binding) constraint

𝑔_{𝑖} (𝑥^{*}) < 0 \Rightarrow 𝜆_{𝑖}^{*} = 0

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

𝑔_{𝑖} (𝑥^{*}) = 0 \Rightarrow 𝜆_{𝑖}^{*} \geq 0

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

\begin{aligned} min & 𝑥_{1}^{2} + 𝑥_{2}^{2} \\ 𝑠 . 𝑡 . & \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} \leq 2 \end{aligned}

Step 1. Standardize constraints

Constraints already in the form $𝑔 (𝑥) \leq 0$ for minimization

Sign convention $𝜆 \geq 0$

Step 2. Formulate Lagrangian

ℒ︀ (𝑥_{1}, 𝑥_{2}, 𝜆) = 𝑥_{1}^{2} + 𝑥_{2}^{2} + 𝜆 (\frac{𝑥_{1}^{2}}{2} - 𝑥_{2} - 2)

Step 3. Stationarity

\nabla_{𝑥} ℒ︀ = [\begin{matrix} \frac{𝜕 ℒ︀}{𝜕 𝑥_{1}} \\ \frac{𝜕 ℒ︀}{𝜕 𝑥_{2}} \end{matrix}] = [\begin{matrix} 2 𝑥_{1} + 𝜆 𝑥_{1} \\ 2 𝑥_{2} - 𝜆 \end{matrix}] = 0

Solve for $𝑥_{1}$ :

\begin{aligned} 2 𝑥_{1} + 𝜆 𝑥_{1} & = 0 \\ 𝑥_{1} (2 + 𝜆) & = 0 \\ 𝑥_{1} (2 + 𝜆) & = \frac{0}{2 + 𝜆} \\ 𝑥_{1} & = 0 \end{aligned}

Solve for $𝑥_{2}$

\begin{aligned} 2 𝑥_{2} - 𝜆 & = 0 \\ 𝑥_{2} & = \frac{𝜆}{2} \end{aligned}

Candidate point:

(𝑥_{1}, 𝑥_{2}) = (0, \frac{𝜆}{2})

Step 4. Primal Feasibility

Constraint:

𝑔 (𝑥_{1}, 𝑥_{2}) = \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} - 2 \leq 0

Substitute $𝑥_{1} = 0$ and $𝑥_{2} = \frac{𝜆}{2}$

\begin{aligned} \frac{0^{2}}{2} - \frac{𝜆}{2} - 2 & \leq 0 \\ - \frac{𝜆}{2} - 2 & \leq 0 \\ - \frac{𝜆}{2} & \leq 2 \\ 𝜆 & \geq - 4 \end{aligned}

Step 5. Dual Feasibility

𝜆 \geq 0

Step 6. Complementary Slackness

Constraint:

𝑔 (𝑥_{1}, 𝑥_{2}) = \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} - 2 \leq 0

Condition:

𝜆 \cdot 𝑔 (𝑥^{*}) = 0

Candidate point:

(𝑥_{1}, 𝑥_{2}) = (0, \frac{𝜆}{2})

Evaluate $𝑔 (𝑥^{*})$ :

𝜆 \cdot 𝑔 (𝑥^{*}) = 𝜆 (\frac{𝑥_{1}^{2}}{2} - 𝑥_{2} - 2) = 0

Substitute $𝑥_{1} = 0$ and $𝑥_{2} = \frac{𝜆}{2}$

\begin{matrix} 𝜆 (\frac{0^{2}}{2} - \frac{𝜆}{2} - 2) = 0 \\ 𝜆 (- \frac{𝜆}{2} - 2) = 0 \end{matrix}

Solve:

𝜆 (- \frac{𝜆}{2} - 2) = 0 \Rightarrow 𝜆 = 0 or 𝜆 = - 4

But because of Dual Feasibility $𝜆 \geq 0$ , so $𝜆 = 0$

Constraint is non-binding at optimum:

$𝜆 = 0$
$𝑔 (𝑥^{*}) < 0$

\begin{aligned} 𝑔 (𝑥^{*}) = \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} - 2 & \leq 0 \\ \frac{0^{2}}{2} - \frac{𝜆}{2} - 2 & \leq 0 \\ \frac{0^{2}}{2} - \frac{0}{2} - 2 & \leq 0 \\ - 2 & \leq 0 \end{aligned}

Step 7. Solve for Optimum

\begin{aligned} (𝑥_{1}, 𝑥_{2}) & = (0, \frac{𝜆}{2}) \\ = (0, \frac{0}{2}) \\ = (0, 0) \end{aligned}

Step 8. Check Convexity

Example

\begin{aligned} min & 𝑥_{1}^{2} + 𝑥_{2}^{2} \\ 𝑠 . 𝑡 . & \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} \leq - 1 \end{aligned}

Step 1. Standardize constraints

Constraints already in the form $𝑔 (𝑥) \leq 0$ for minimization

Sign convention $𝜆 \geq 0$

Step 2. Formulate Lagrangian

ℒ︀ (𝑥_{1}, 𝑥_{2}, 𝜆) = 𝑥_{1}^{2} + 𝑥_{2}^{2} + 𝜆 (\frac{𝑥_{1}^{2}}{2} - 𝑥_{2} + 1)

Step 3. Stationarity

\nabla_{𝑥} ℒ︀ = [\begin{matrix} \frac{𝜕 ℒ︀}{𝜕 𝑥_{1}} \\ \frac{𝜕 ℒ︀}{𝜕 𝑥_{2}} \end{matrix}] = [\begin{matrix} 2 𝑥_{1} + 𝜆 𝑥_{1} \\ 2 𝑥_{2} - 𝜆 \end{matrix}]

Solve for $𝑥_{1}$ :

\begin{aligned} 2 𝑥_{1} + 𝜆 𝑥_{1} & = 0 \\ 𝑥_{1} (2 + 𝜆) & = 0 \\ 𝑥_{1} & = \frac{0}{2 + 𝜆} \\ 𝑥_{1} & = 0 \end{aligned}

Solve for $𝑥_{2}$ :

\begin{aligned} 2 𝑥_{2} - 𝜆 & = 0 \\ 2 𝑥_{2} & = 𝜆 \\ 𝑥_{2} & = \frac{𝜆}{2} \end{aligned}

Candidate point:

(𝑥_{1}, 𝑥_{2}) = (0, \frac{𝜆}{2})

Step 4. Primal Feasibility

Constraint:

𝑔 (𝑥_{1}, 𝑥_{2}) = \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} + 1 \leq 0

Substitute $𝑥_{1} = 0$ and $𝑥_{2} = \frac{𝜆}{2}$ :

\begin{matrix} \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} + 1 \leq 0 \\ \frac{0^{2}}{2} - \frac{𝜆}{2} + 1 \leq 0 \\ - \frac{𝜆}{2} + 1 \leq 0 \\ - \frac{𝜆}{2} \leq - 1 \\ 𝜆 \geq 2 \end{matrix}

Step 5. Dual Feasibility

𝜆 \geq 0

Step 6. Complementary Slackness

Constraint:

𝑔 (𝑥_{1}, 𝑥_{2}) = \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} + 1 \leq 0

Condition:

𝜆 \cdot 𝑔 (𝑥^{*}) = 0

Candidate point:

(𝑥_{1}, 𝑥_{2}) = (0, \frac{𝜆}{2})

Evaluate $𝑔 (𝑥^{*})$ :

𝜆 \cdot 𝑔 (𝑥^{*}) = 𝜆 (\frac{𝑥_{1}^{2}}{2} - 𝑥_{2} + 1) = 0

Substitute $𝑥_{1} = 0$ and $𝑥_{2} = \frac{𝜆}{2}$

\begin{matrix} 𝜆 (\frac{0^{2}}{2} - \frac{𝜆}{2} + 1) = 0 \\ 𝜆 (- \frac{𝜆}{2} + 1) = 0 \end{matrix}

Solve:

𝜆 (- \frac{𝜆}{2} + 1) = 0 \Rightarrow 𝜆 = 0 or 𝜆 = 2

But because of Primal Feasibility, if $𝜆 = 0$ , $(𝑥_{1}, 𝑥_{2}) = (0, 0)$ and $𝑔 (0, 0) = 1 ≰ 0$ , thus $𝜆 = 2$

Constraint is binding at optimum:

$𝜆 = 2$
$𝑔 (𝑥^{*}) = 0$

\begin{aligned} 𝑔 (𝑥^{*}) = \frac{𝑥_{1}^{2}}{2} - 𝑥_{2} + 1 & = 0 \\ \frac{0^{2}}{2} - \frac{𝜆}{2} + 1 & = 0 \\ \frac{0^{2}}{2} - \frac{2}{2} + 1 & = 0 \\ 0 & = 0 \end{aligned}

Step 7. Solve for Optimum

\begin{aligned} (𝑥_{1}, 𝑥_{2}) & = (0, \frac{𝜆}{2}) \\ = (0, \frac{2}{2}) \\ = (0, 1) \end{aligned}

Step 8. Check Convexity

337.0.4. Calculating Lagrangian Multipliers

To find the multipliers ( $𝜆^{*}, 𝜇^{*}$ ) and the optimal point $𝑥^{*}$ , solve the KKT system of equations:

{\begin{cases} \nabla_{𝑥} ℒ︀ (𝑥, 𝜆, 𝜇) = 0 \\ 𝑔_{𝑖} (𝑥) \leq 0 & \forall 𝑖 = 1, \dots, 𝑚 \\ ℎ_{𝑗} (𝑥) = 0 & \forall 𝑖 = 1, \dots, 𝑝 \\ 𝜆_{𝑖} \geq 0 & \forall 𝑖 = 1, \dots, 𝑚 \\ 𝜆_{𝑖} 𝑔_{𝑖} (𝑥) = 0 & \forall 𝑖 = 1, \dots, 𝑚 \end{cases}

Example

Retailer Maximizing Profit under a Capacity Constraint

A retailer sells product 1 and 2 with quantities $𝑞_{1}$ and $𝑞_{2}$ . For product $𝑖$ the market-clearing prices are:

𝑝_{𝑖} = 𝑎_{𝑖} - 𝑏_{𝑖} 𝑞_{𝑖} 𝑖 = 1, 2

Where $𝑎_{𝑖}, 𝑏_{𝑖} > 0$ .

The retailer maximizes total profit subject to a capacity constraint:

𝑞_{1} + 𝑞_{2} \leq 𝐾 𝑞_{1}, 𝑞_{2} \geq 0

Formulation

\begin{aligned} max_{𝑞_{1}, 𝑞_{2} \geq 0} & 𝑞_{1} \overset{𝑝_{1}}{\overset{⏞}{(𝑎_{1} - 𝑏_{1} 𝑞_{1})}} + 𝑞_{2} \overset{𝑝_{2}}{\overset{⏞}{(𝑎_{2} - 𝑏_{2} 𝑞_{2})}} \\ 𝑠 . 𝑡 . & 𝑞_{1} + 𝑞_{2} \leq 𝐾 \end{aligned}

The objective is concave because

- \nabla^{2} 𝑓 (𝑞_{1}, 𝑞_{2}) = [\begin{matrix} 2 𝑏_{1} & 0 \\ 0 & 2 𝑏_{2} \end{matrix}]

is positive semi-definite.

The unconstrained FOC solution is:

𝑞_{1} = \frac{𝑎_{1}}{2 𝑏_{1}}, 𝑞_{2} = \frac{𝑎_{2}}{2 𝑏_{2}}

If $𝑞_{1} + 𝑞_{2} \leq 𝐾$ , this solution is feasible.

Lagrangian

Introduce KKT multiplier $𝜆 \geq 0$ for the inequality constraint:

ℒ︀ (𝑞_{1}, 𝑞_{2}, 𝜆) = \overset{𝑓}{\overset{⏞}{𝑞_{1} (𝑎_{1} - 𝑏_{1} 𝑞_{1}) + 𝑞_{2} (𝑎_{2} - 𝑏_{2} 𝑞_{2})}} + 𝜆 \overset{𝑏 - 𝑔}{\overset{⏞}{(𝐾 - 𝑞_{1} - 𝑞_{2})}}

KKT Conditions

1. Stationarity

\begin{matrix} \frac{𝜕}{𝜕 𝑞_{1}} ℒ︀ = 𝑎_{1} - 2 𝑏_{1} 𝑞_{1} - 𝜆 = 0 \\ \frac{𝜕}{𝜕 𝑞_{2}} ℒ︀ = 𝑎_{2} - 2 𝑏_{2} 𝑞_{2} - 𝜆 = 0 \end{matrix}

2. Primal Feasibility

𝑞_{1} + 𝑞_{2} \leq 𝐾 𝑞_{1}, 𝑞_{2} \geq 0

3. Dual Feasibility

𝜆 \geq 0

4. Complementary Slackness

𝜆 (𝐾 - 𝑞_{1} - 𝑞_{2}) = 0

Solving KKT system

Case 1: Unconstrained ( $𝜆 = 0$ )

\begin{aligned} max_{𝑞_{1}, 𝑞_{2} \geq 0} & 𝑓 (𝑞_{1}, 𝑞_{2}) = 𝑞_{1} (𝑎_{1} - 𝑏_{1} 𝑞_{1}) + 𝑞_{2} (𝑎_{2} - 𝑏_{2} 𝑞_{2}) \\ 𝑓 (𝑞_{1}, 𝑞_{2}) = 𝑎_{1} 𝑞_{1} - 𝑏_{1} 𝑞_{1}^{2} + 𝑎_{2} 𝑞_{2} - 𝑏_{2} 𝑞_{2}^{2} \end{aligned}

First-Order Condition

\begin{matrix} \frac{𝜕 𝑓}{𝜕 𝑞_{1}} = 𝑎_{1} - 2 𝑏_{1} 𝑞_{1} \\ \frac{𝜕 𝑓}{𝜕 𝑞_{2}} = 𝑎_{2} - 2 𝑏_{2} 𝑞_{2} \end{matrix}

Set derivatives to 0 (stationarity)

\begin{matrix} 𝑎_{1} - 2 𝑏_{1} 𝑞_{1} = 0 \Rightarrow 𝑞_{1}^{*} = \frac{𝑎_{1}}{2 𝑏_{1}} \\ 𝑎_{2} - 2 𝑏_{2} 𝑞_{2} = 0 \Rightarrow 𝑞_{2}^{*} = \frac{𝑎_{2}}{2 𝑏_{2}} \end{matrix}

Unconstrained Solution:

\begin{matrix} 𝑞_{1}^{*} = \frac{𝑎_{1}}{2 𝑏_{1}} \\ 𝑞_{2}^{*} = \frac{𝑎_{2}}{2 𝑏_{2}} \end{matrix}

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

\begin{matrix} \frac{𝜕^{2} 𝑓}{𝜕 𝑞_{1}^{2}} = - 2 𝑏_{1} < 0 \\ \frac{𝜕^{2} 𝑓}{𝜕 𝑞_{2}^{2}} = - 2 𝑏_{2} < 0 \end{matrix}

Feasible if

\frac{𝑎_{1}}{2 𝑏_{1}} + \frac{𝑎_{2}}{2 𝑏_{2}} \leq 𝐾

Case 2: Binding Constraint ( $𝜆 > 0$ )

We now include the capacity constraint:

𝑞_{1} + 𝑞_{2} = 𝐾

If it binds (active) then

𝑞_{1} + 𝑞_{2} = 𝐾

Lagrangian

ℒ︀ (𝑞_{1}, 𝑞_{2}, 𝜆) = \overset{𝑓 (𝑞_{1}, 𝑞_{2})}{\overset{⏞}{𝑞_{1} (𝑎_{1} - 𝑏_{1} 𝑞_{1}) + 𝑞_{2} (𝑎_{2} - 𝑏_{2} 𝑞_{2})}} + 𝜆 \overset{𝑏 - 𝑔 (𝑞_{1}, 𝑞_{2})}{\overset{⏞}{(𝐾 - 𝑞_{1} - 𝑞_{2})}}

First-Order Condition

\begin{aligned} \frac{𝜕 ℒ︀}{𝜕 𝑞_{1}} & = 𝑎_{1} - 2 𝑏_{1} 𝑞_{1} - 𝜆 \\ \frac{𝜕 ℒ︀}{𝜕 𝑞_{2}} & = 𝑎_{2} - 2 𝑏_{2} 𝑞_{2} - 𝜆 \\ \frac{𝜕 ℒ︀}{𝜕 𝜆} & = 𝐾 - 𝑞_{1} - 𝑞_{2} \end{aligned}

Set derivatives to 0 (stationarity)

\begin{matrix} 𝑎_{1} - 2 𝑏_{1} 𝑞_{1} - 𝜆 = 0 \\ 𝑎_{2} - 2 𝑏_{2} 𝑞_{2} - 𝜆 = 0 \\ 𝐾 - 𝑞_{1} - 𝑞_{2} = 0 \end{matrix}

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

Solve system of equations

{\begin{cases} 𝑎_{1} - 2 𝑏_{1} 𝑞_{1} - 𝜆 = 0 \\ 𝑎_{2} - 2 𝑏_{2} 𝑞_{2} - 𝜆 = 0 \\ 𝑞_{1} + 𝑞_{2} = 𝐾 \end{cases}

Solution:

𝑞_{1} = \frac{2 𝑏_{2} 𝐾 + 𝑎_{1} - 𝑎_{2}}{2 (𝑏_{1} + 𝑏_{2})} 𝑞_{2} = \frac{2 𝑏_{1} 𝐾 + 𝑎_{2} - 𝑎_{1}}{2 (𝑏_{1} + 𝑏_{2})}

Feasible if

\frac{𝑎_{1}}{2 𝑏_{1}} + \frac{𝑎_{2}}{2 𝑏_{2}} > 𝐾

Optimal Solution

(𝑞_{1}^{*}, 𝑞_{2}^{*}) = {\begin{cases} (\frac{𝑎_{1}}{2 𝑏_{1}}, \frac{𝑎_{2}}{2 𝑏_{2}}) & if \frac{𝑎_{1}}{2 𝑏_{1}} + \frac{𝑎_{2}}{2 𝑏_{2}} \leq 𝐾 \\ (\frac{2 𝑏_{2} 𝐾 + 𝑎_{1} - 𝑎_{2}}{2 (𝑏_{1} + 𝑏_{2})}, \frac{2 𝑏_{1} 𝐾 + 𝑎_{2} - 𝑎_{1}}{2 (𝑏_{1} + 𝑏_{2})}) & otherwise \end{cases}

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

\begin{aligned} max & 𝑓 (𝑥) = 𝑥_{1} - 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑔_{1} (𝑥) = 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 4 \\ 𝑔_{2} (𝑥) = - 𝑥_{1}^{2} - {(𝑥_{2} + 2)}^{2} \leq - 4 \end{aligned}

This NLP is nonconvex

1️⃣ Lagrangian

Introduce multipliers $𝜆_{1}, 𝜆_{2} \geq 0$ for the inequalities. The Lagrangian is

ℒ︀ (𝑥_{1}, 𝑥_{2}, 𝜆) = \overset{𝑓}{\overset{⏞}{𝑥_{1} - 𝑥_{2}}} + 𝜆_{1} \overset{𝑔_{1}}{\overset{⏞}{(4 - 𝑥_{1}^{2} - 𝑥_{2}^{2})}} + 𝜆_{2} \overset{𝑔_{2}}{\overset{⏞}{(- 4 + 𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2})}}

The solution $\bar{𝑥}$ is a local maximum only if there exists $𝜆$ such that

2️⃣ KKT Conditions

Primal feasibility

\begin{aligned} 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 4 & (PF-1) \\ - 𝑥_{1}^{2} - {(𝑥_{2} + 2)}^{2} \leq - 4 & (PF-2) \end{aligned}

Dual Feasibility

\begin{aligned} 𝜆_{1} \geq 0 & (DFS-1) \\ 𝜆_{2} \geq 0 & (DFS-2) \end{aligned}

Stationarity

\begin{aligned} \frac{𝜕 ℒ︀}{𝜕 𝑥_{1}} & = 1 - 2 (𝜆_{1} - 𝜆_{2}) 𝑥_{1} = 0 & (DFF-1) \\ \frac{𝜕 ℒ︀}{𝜕 𝑥_{2}} & = - 1 - 2 (𝜆_{1} - 𝜆_{2}) 𝑥_{2} + 4 𝜆_{2} = 0 & (DFF-2) \end{aligned}

Complimentary Slackness

\begin{aligned} 𝜆_{1} (4 - 𝑥_{1}^{2} - 𝑥_{2}^{2}) = 0 & (CS-1) \\ 𝜆_{2} (- 4 + 𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2}) = 0 & (CS-2) \end{aligned}

3️⃣ Examine all 4 cases for $(𝜆_{1}, 𝜆_{2})$

Case 1. ( $𝜆_{1} > 0, 𝜆_{2} > 0$ )

Step 1: Complementary Slackness

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

\begin{aligned} 𝑥_{1}^{2} + 𝑥_{2}^{2} & = 4 & (CS-1) \\ 𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2} & = 4 & (CS-2) \end{aligned}

Solve this system $\to$ two candidate points:

(𝑥_{1}, 𝑥_{2}) = (\sqrt{3}, - 1) and (- \sqrt{3}, - 1)

Step 2: Primal Feasibility

For $(\sqrt{3}, - 1)$

\begin{aligned} 𝑥_{1}^{2} + 𝑥_{2}^{2} & = {\sqrt{3}}^{2} + {(- 1)}^{2} \leq 4 & (PF-1) \\ - 𝑥_{1}^{2} - {(𝑥_{2} + 2)}^{2} & = - {(\sqrt{3})}^{2} - {(- 1 + 2)}^{2} \leq - 4 & (PF-2) \end{aligned}

For $(- \sqrt{3}, - 1)$

\begin{aligned} 𝑥_{1}^{2} + 𝑥_{2}^{2} & = {(- \sqrt{3})}^{2} + {(- 1)}^{2} \leq 4 & (PF-1) \\ - 𝑥_{1}^{2} - {(𝑥_{2} + 2)}^{2} & = - {(- \sqrt{3})}^{2} - {(- 1 + 2)}^{2} \leq - 4 & (PF-2) \end{aligned}

✅ Both satisfy primal feasibility.

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

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

\begin{aligned} 1 - 2 (𝜆_{1} - 𝜆_{2}) 𝑥_{1} & = 0 & (DFF-1) \\ - 1 - 2 (𝜆_{1} - 𝜆_{2}) 𝑥_{2} + 4 𝜆_{2} & = 0 & (DFF-2) \end{aligned}

For $(\sqrt{3}, - 1)$ :

\begin{aligned} 1 - 2 (𝜆_{1} - 𝜆_{2}) (\sqrt{3}) & = 0 \\ - 1 - 2 (𝜆_{1} - 𝜆_{2}) (- 1) + 4 𝜆_{2} & = 0 \end{aligned}

Solving the system we get:

\begin{matrix} 𝜆_{1} = \frac{1}{4} + \frac{1}{4 \sqrt{3}} \\ 𝜆_{2} = \frac{1}{4} - \frac{1}{4 \sqrt{3}} \end{matrix}

✅ Both $𝜆_{1}, 𝜆_{2} \geq 0$ $\to$ dual feasibility satisfied.

For $(- \sqrt{3}, - 1)$ :

\begin{aligned} 1 - 2 (𝜆_{1} - 𝜆_{2}) (- \sqrt{3}) & = 0 ⟹ 𝜆_{1} - 𝜆_{2} = - \frac{1}{2 \sqrt{3}} \\ - 1 - 2 (𝜆_{1} - 𝜆_{2}) (- 1) + 4 𝜆_{2} & = 0 ⟹ 𝜆_{2} = \frac{1}{4} + \frac{1}{4 \sqrt{3}} \end{aligned}

Solving the system we get:

\begin{matrix} 𝜆_{1} = \frac{1}{4} - \frac{1}{4 \sqrt{3}} \\ 𝜆_{2} = \frac{1}{4} + \frac{1}{4 \sqrt{3}} \end{matrix}

✅ Both $𝜆_{1}, 𝜆_{2} \geq 0$ $\to$ dual feasibility satisfied.

✅ Both $(\sqrt{3}, - 1)$ and $(- \sqrt{3}, - 1)$ satisfy dual feasibility $\to$ both are KKT points.

Case 2. ( $𝜆_{1} > 0, 𝜆_{2} = 0$ )

Step 1. Assumptions (Activity / Inactivity)

Constraint 1: Active ( $𝑥_{1}^{2} + 𝑥_{2}^{2} = 4$ )
Constraint 2: Inactive ( $𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2} = 4$ )

Step 2. Stationarity Condition

The Lagragian:

ℒ︀ (𝑥_{1}, 𝑥_{2}, 𝜆_{1}, 𝜆_{2}) = (𝑥_{1} - 𝑥_{2}) + 𝜆_{1} (4 - 𝑥_{1}^{2} - 𝑥_{2}^{2}) + 𝜆_{2} (- 4 + 𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2})

Compute the gradients with respect to $𝑥_{1}$ and $𝑥_{2}$ :

{\begin{cases} \frac{𝜕 ℒ︀}{𝜕 𝑥_{1}} & = 1 - 2 𝜆_{1} 𝑥_{1} + 2 𝜆_{2} 𝑥_{1} = 0 \\ \frac{𝜕 ℒ︀}{𝜕 𝑥_{2}} & = - 1 - 2 𝜆_{1} 𝑥_{2} + 2 𝜆_{2} (𝑥_{2} + 2) = 0 \end{cases}

Since $𝜆_{2} = 0$ , the equations simplify to:

{\begin{cases} 1 - 2 𝜆_{1} 𝑥_{1} = 0 \\ - 1 - 2 𝜆_{1} 𝑥_{2} = 0 \end{cases}

Simplify:

{\begin{cases} 𝑥_{1} = \frac{1}{2 𝜆_{1}} \\ 𝑥_{2} = - \frac{1}{2 𝜆_{1}} \end{cases} \Rightarrow 𝑥_{1} = - 𝑥_{2}

Step 3. Substitute into Active Constraint

Using $𝑥_{1}^{2} + 𝑥_{2}^{2} = 4$ and $𝑥_{2} = - 𝑥_{1}$ :

𝑥_{1}^{2} + {(- 𝑥_{1})}^{2} = 2 𝑥_{1}^{2} = 4 \Rightarrow 𝑥_{1}^{2} = 2 \Rightarrow 𝑥_{1} = \pm \sqrt{2}, 𝑥_{2} = \mp \sqrt{2}

Two candidate solutions $𝑥_{1}$ and $𝑥_{2}$ :

(- \sqrt{2}, \sqrt{2}) and (\sqrt{2}, - \sqrt{2})

Step 4. Solve for $𝜆_{1}$ and enforce $𝜆_{1} > 0$

1 + 2 𝜆_{1} 𝑥_{1} = 0 \Rightarrow 𝜆_{1} = - \frac{1}{2 𝑥_{1}}

Substitute $(𝑥_{1}, 𝑥_{2})$ into the stationarity condition:

1 + 2 𝜆_{1} 𝑥_{1}

For $(𝑥_{1}, 𝑥_{2}) = (\sqrt{2}, - \sqrt{2})$ :

𝜆_{1} = \frac{1}{2 \sqrt{2}} > 0 \to ✅

Valid(𝜆1≥0)

For $(𝑥_{1}, 𝑥_{2}) = (- \sqrt{2}, \sqrt{2})$ :

𝜆_{1} = \frac{1}{2 (- \sqrt{2})} > 0 \to ❌

Reject(violates𝜆1≥0)

So, the surviving candidate is:

(𝑥_{1}, 𝑥_{2}) = (\sqrt{2}, - \sqrt{2}), 𝜆_{1} = \frac{1}{2 \sqrt{2}}, 𝜆_{2} = 0

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

Constraint 2:

𝑔_{2} (𝑥) = - 𝑥_{1}^{2} - {(𝑥_{2} + 2)}^{2} + 4 \leq 0

Plug $𝑥_{1} = \sqrt{2}$ and $𝑥_{2} = - \sqrt{2}$ :

𝑔_{2} (𝑥) = - {(\sqrt{2})}^{2} - {(- \sqrt{2} + 2)}^{2} + 4 > 0

❌ This violates the inequality $𝑔_{2} (𝑥) \leq 0$

❌ $(𝑥_{1}, 𝑥_{2}) = (\sqrt{2}, - \sqrt{2})$ is rejected because it violates the inequality $𝑔_{2} (𝑥) \leq 0$

❌ $(𝑥_{1}, 𝑥_{2}) = (- \sqrt{2}, \sqrt{2})$ is rejected because it gives $𝜆 < 0$

Case 3. ( $𝜆_{1} = 0, 𝜆_{2} > 0$ )

Step 1. Assumptions (Activity / Inactivity)

Constraint 1: Inactive ( $𝑥_{1}^{2} + 𝑥_{2}^{2} = 4$ )
Constraint 2: Active ( $𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2} = 4$ )

Step 2. Stationarity Condition

The Lagragian:

ℒ︀ (𝑥_{1}, 𝑥_{2}, 𝜆_{1}, 𝜆_{2}) = (𝑥_{1} - 𝑥_{2}) + 𝜆_{1} (4 - 𝑥_{1}^{2} - 𝑥_{2}^{2}) + 𝜆_{2} (- 4 + 𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2})

Compute the gradients with respect to $𝑥_{1}$ and $𝑥_{2}$ :

{\begin{cases} \frac{𝜕 ℒ︀}{𝜕 𝑥_{1}} & = 1 - 2 𝜆_{1} 𝑥_{1} + 2 𝜆_{2} 𝑥_{1} = 0 \\ \frac{𝜕 ℒ︀}{𝜕 𝑥_{2}} & = - 1 - 2 𝜆_{1} 𝑥_{2} + 2 𝜆_{2} (𝑥_{2} + 2) = 0 \end{cases}

Since $𝜆_{1} = 0$ , the equations simplify to:

{\begin{cases} 1 + 2 𝜆_{2} 𝑥_{1} = 0 \\ - 1 + 2 𝜆_{2} (𝑥_{2} + 2) = 0 \end{cases}

Simplify:

{\begin{cases} 𝑥_{1} = - \frac{1}{2 𝜆_{2}} \\ 𝑥_{2} = \frac{1}{2 𝜆_{2}} - 2 \end{cases} \Rightarrow 𝑥_{1} = - 𝑥_{2}

Step 3. Substitute into Active Constraint

𝑥_{1}^{2} + {(𝑥_{2} + 2)}^{2} = 4

Substituting $𝑥_{1}$ and $𝑥_{2}$ :

{(- \frac{1}{2 𝜆_{2}})}^{2} + {(\frac{1}{2 𝜆_{2}} - 2 + 2)}^{2} = 4 \Rightarrow 𝜆_{2} = \pm \frac{1}{2 \sqrt{2}}

Two candidate solutions $𝑥_{1}$ and $𝑥_{2}$ :

(- \sqrt{2}, \sqrt{2} - 2) and (\sqrt{2}, - \sqrt{2} - 2)

Substitute $(𝑥_{1}, 𝑥_{2})$ into the stationarity condition:

- 1 + 2 𝜆_{2} (𝑥_{2} + 2)

For $(𝑥_{1}, 𝑥_{2}) = (\sqrt{2}, - \sqrt{2} - 2)$ :

𝜆_{2} = - \frac{1}{2 \sqrt{2}} < 0 \to ❌

Reject(violates𝜆1≥0)

For $(𝑥_{1}, 𝑥_{2}) = (- \sqrt{2}, \sqrt{2} - 2)$ :

𝜆_{2} = \frac{1}{2 \sqrt{2}} > 0 \to ✅

Valid(𝜆1≥0)

So, the surviving candidate is:

(𝑥_{1}, 𝑥_{2}) = (- \sqrt{2}, \sqrt{2} - 2), 𝜆_{1} = 0, 𝜆_{2} = \frac{1}{2 \sqrt{2}}

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

Constraint 1:

𝑔_{1} (𝑥) = 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 4

Plug $𝑥_{1} = - \sqrt{2}$ and $𝑥_{2} = \sqrt{2} - 2$ :

𝑔_{1} (𝑥) = - {(\sqrt{2})}^{2} - {(\sqrt{2} - 2)}^{2} + 4 \leq 0

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

✅ $(𝑥_{1}, 𝑥_{2}) = (- \sqrt{2}, \sqrt{2} - 2)$ is a valid KKT point under this assumption.

❌ $(𝑥_{1}, 𝑥_{2}) = (\sqrt{2}, - \sqrt{2} - 2)$ is rejected because it gives $𝜆 < 0$

Case 4. ( $𝜆_{1} = 0, 𝜆_{2} = 0$ )

Step 1. Assumptions (Activity / Inactivity)

Both multipliers are zero: $𝜆_{1} = 0, 𝜆_{2} = 0$
No constraints are forced to be active by complementary slackness

Step 2. Stationarity Condition

With $𝜆_{1} = 0$ and $𝜆_{2} = 0$ , the stationarity equations simplify to:

{\begin{cases} 1 - 2 (𝜆_{1} - 𝜆_{2}) 𝑥_{1} = 1 = 0 \\ - 1 - 2 (𝜆_{1} - 𝜆_{2}) 𝑥_{2} + 4 𝜆_{2} = - 1 = 0 \end{cases}

Step 3. Stationary Check

Both equations $1 = 0$ and $- 1 = 0$ are impossible

No solution exists under this assumption

❌ No KKT points exist

4️⃣ Summary

$𝜆_{1} > 0$ and $𝜆_{2} > 0$ :
- $(\sqrt{3}, - 1)$
- $(- \sqrt{3}, 1)$
$𝜆_{1} = 0$ and $𝜆_{2} > 0$ :
- $(- \sqrt{2}, \sqrt{2} - 2)$

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

Necessary, but not sufficient for non-convex NLPs

337.0.5. Sensitivity Analysis and Shadow Prices

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

337.0.5.1. Shadow Prices

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

{ShadowPrice}_{𝑖} = 𝜆_{𝑖}^{*}

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

𝑥_{1} + 𝑥_{2} \leq 12 \to 𝑥_{1} + 𝑥_{2} \leq 13

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	$𝑔_{𝑖} (𝑥^{*}) = 0$	$𝜆^{*} > 0$	Relaxing improves objective
Inactive / Slack	$𝑔_{𝑖} (𝑥^{*}) < 0$	$𝜆^{*} = 0$	Relaxing has no effect

Example

Primal NLP

𝑧^{*} = max_{𝑥 \in ℝ^{𝑛}} {𝑓 (𝑥) | 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} \forall 𝑖 = 1, \dots, 𝑚}

Lagrange Dual Program

𝑤^{*} = min_{𝜆 \geq 0} 𝑧^{𝐿} (𝜆) = min_{𝜆 \geq 0} {max_{𝑥 \in ℝ^{𝑛}} 𝑓 (𝑥) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖} [𝑏_{𝑖} - 𝑔_{𝑖} (𝑥)]}

Convexity

The Lagrange Dual Program function $𝑧^{𝐿} (𝜆)$ is always convex over $𝜆 \in {[0, \infty)}^{𝑛}$

Weak Duality

𝑤^{*} \geq 𝑧^{*} \forall 𝜆 \geq 0

Strong Duality

$𝑤^{*} = 𝑧^{*}$ is the primal NLP is a “regular” convex program

Example

\begin{aligned} 𝑧^{*} = max & 𝑥_{1} + & 𝑥_{2} \\ 𝑠 . 𝑡 . & 𝑥_{1}^{2} + & 𝑥_{2}^{2} \leq 8 \\ 𝑥_{2} \leq 6 \end{aligned}

Optimal solution

\begin{aligned} 𝑥^{*} & = (2, 2) \\ 𝑧^{*} & = 4 \end{aligned}

Lagragian relaxation

𝑤^{*} = min_{𝜆_{1} \geq 0, 𝜆_{2} \geq 0} 𝑧^{𝐿} (𝜆) = min_{𝜆_{1} \geq 0, 𝜆_{2} \geq 0} max_{𝑥 \in ℝ^{2}} ℒ︀ (𝑥 | 𝜆)

Where

ℒ︀ (𝑥 | 𝜆) = 𝑥_{1} + 𝑥_{2} + 𝜆_{1} (8 - 𝑥_{1}^{2} + 𝑥_{2}^{2}) + 𝜆_{2} (6 - 𝑥_{2})

To solve the Lagrange dual program:

max_{𝑥 \in ℝ^{2}} ℒ︀ (𝑥 | 𝜆) max_{𝑥 \in ℝ^{2}} {𝑥_{1} + 𝑥_{2} + 𝜆_{1} (8 - 𝑥_{1}^{2} - 𝑥_{2}^{2}) + 𝜆_{2} (6 - 𝑥_{2})}

First-order condition:

𝑥_{1} = \frac{1}{2 𝜆_{1}} and 𝑥_{2} = \frac{1 - 𝜆_{2}}{2 𝜆_{1}}

Plugging into $ℒ︀ (𝑥 | 𝜆)$ :

𝑧^{𝐿} (𝜆) = max_{𝑥 \in ℝ^{2}} ℒ︀ (𝑥 | 𝜆) = \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}} + 8 𝜆_{1} + 6 𝜆_{2}

The Lagrangian dual program is to look for $𝜆_{1} \geq 0$ and $𝜆_{2} \geq 0$ to minimize $𝑧^{𝐿} (𝜆)$

The Lagrange dual program:

min_{𝜆_{1} \geq 0, 𝜆_{2} \geq 0} \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}} + 8 𝜆_{1} + 6 𝜆_{2}

$𝑧^{𝐿} (𝜆)$ is convex over ${(0, \infty)}^{2}$ :

\nabla 𝑧^{𝐿} (𝜆) = [\begin{matrix} - \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}^{2}} + 8 \\ - \frac{1 - 𝜆_{2}}{2 𝜆_{1}} + 6 \end{matrix}], \nabla^{2} 𝑧^{𝐿} (𝜆) = [\begin{matrix} \frac{1 + {(1 - 𝜆_{2})}^{2}}{2 𝜆_{1}^{2}} & \frac{1 - 𝜆_{2}}{2} 𝜆_{1}^{2} \\ \frac{1 - 𝜆_{2}}{2 𝜆_{1}^{2}} & \frac{1}{2 𝜆_{1}} \end{matrix}]

Since:

$\frac{1 + {(1 - 𝜆_{2})}^{2}}{2 𝜆_{1}^{2}} > 0$ and $det (\nabla^{2} 𝑧^{𝐿} (𝜆)) = \frac{1}{2 𝜆_{1}} > 0$ , $𝑧^{𝐿} (𝜆)$ is convex

To solve

min_{𝜆_{1} \geq 0, 𝜆_{2} \geq 0} \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}} + 8 𝜆_{1} + 6 𝜆_{2}

Apply KKT conditions

$𝜆_{1}$ cannot be binding ( $𝜆_{1} = 0$ ), because division by 0, so ignore it

Let $𝜇 \geq 0$ be the Lagrange multiplier for $𝜆_{2} \geq 0$ , the Lagrange is

\frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}} + 8 𝜆_{1} + 6 𝜆_{2} - 𝜇 𝜆_{2}

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

- \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}^{2}} + 8 = 0, - \frac{1 - 𝜆_{2}}{2 𝜆_{1}} + 6 - 𝜇 = 0, 𝜇 𝜆 = 0

Suppose $𝜇 > 0$
- Implies $𝜆_{2} = 0$
- $- \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}^{2}} + 8 = 0$ requires $𝜆_{1} = \frac{1}{4}$
- $- \frac{1 - 𝜆_{2}}{2 𝜆_{1}} + 6 - 𝜇 = 0$ requires $𝜇 = 4$ , which is feasible
Suppose $𝜇 = 0$
- $- \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}^{2}} + 8 = 0$ requires $𝜆_{2} = 1 - 12 𝜆_{1}$
- Plugging into $- \frac{1 + {(1 - 𝜆_{2})}^{2}}{4 𝜆_{1}^{2}} + 8 = 0$ results on $1 + 112 𝜆_{1}^{2}$ which is impossible
The only KKT point is $(𝜆_{1}, 𝜆_{2}) = (\frac{1}{4}, 0)$
Plugging into $𝑧^{𝐿} (𝜆)$ gives us $𝑤^{*} = 4$ which exactly equals $𝑧^{*}$

So strong duality holds, $𝑤^{*} = 𝑧^{*}$

337.0.6. Lagrange Duality and LP Duality

LP duality is a special case of Lagrange Duality

For a general LP

\begin{aligned} max & 𝑐^{𝑇} 𝑥 \\ 𝑠 . 𝑡 . & 𝐴 𝑥 = 𝑏 \\ 𝑥 \geq 0 \end{aligned}

Where $𝐴 \in ℝ^{𝑚 \times 𝑛}$ ( $𝑚$ constraints and $𝑛$ variables)

Let $𝜆 \in ℝ^{𝑚}$ be the Lagrange multipliers, the Lagrange relaxation is

\begin{aligned} 𝑧^{*} (𝜆) & = max_{𝑥 \geq 0} 𝑐^{𝑇} 𝑥 + 𝜆^{𝑇} (𝑏 - 𝐴 𝑥) \\ = 𝐴^{𝑇} 𝑏 + max_{𝑥 \geq 0} (𝑐^{𝑇} - 𝜆^{𝑇} 𝐴) 𝑥 \end{aligned}

Because of equality constraint, $𝜆$ is unrestricted in sign

Lagrange dual program

min_{𝜆} 𝑧^{𝐿} (𝜆) = min_{𝜆} {𝜆^{𝑇} 𝑏 + max_{𝑥 \geq 0} (𝑐^{𝑇} - 𝜆^{𝑇} 𝐴) 𝑥}

Search for $𝜆$ that minimizes $𝑧^{𝐿} (𝜆)$

Dual program is only meaningful if $𝑐^{𝑇} \leq 𝜆^{𝑇} 𝐴$ , because if ${(𝑐^{𝑇})}_{𝑖} > {(𝜆^{𝑇} 𝐴)}_{𝑖}$ for any $𝑖$ , ${max}_{𝑥 \geq 0} (𝑐^{𝑇} - 𝜆^{𝑇} 𝐴) 𝑥$ will be unbounded because we can increase $𝑥_{𝑖}$ to $\infty$

Thus, no choice of $𝜆$ that violates $𝑐^{𝑇} \leq 𝜆^{𝑇} 𝐴$ may be optimal to the Lagrange dual program

The Lagrange dual program

min_{𝜆} 𝑧^{*} (𝜆) = min_{𝜆_{𝑖} 𝑐^{𝑇} \leq 𝜆^{𝑇} 𝐴} {𝜆^{𝑇} 𝑏 + max_{𝑥 \geq 0} (𝑐^{𝑇} - 𝜆^{𝑇} 𝐴) 𝑥}

If $𝜆$ satisfies $𝑐^{𝑇} \leq 𝜆^{𝑇} 𝐴$ thenwe know ${max}_{𝑥 \geq 0} (𝑐^{𝑇} - 𝜆^{𝑇} 𝐴) 𝑥 = 0$

The Lagrange dual program becomes

\begin{aligned} min_{𝜆 urs} & 𝜆^{𝑇} 𝑏 \\ 𝑠 . 𝑡 . & 𝜆^{𝑇} 𝐴 \geq 𝑐^{𝑇} \end{aligned}

Which is exactly the dual LP of

\begin{aligned} max_{𝑥 \geq 0} & 𝑐^{𝑇} 𝑥 \\ 𝑠 . 𝑡 . & 𝐴 𝑥 = 𝑏 \end{aligned}

Example

\begin{aligned} min & {(𝑥_{1} - 4)}^{2} + {(𝑥_{2} - 2)}^{2} \\ 𝑠 . 𝑡 . & 2 𝑥_{1} + 𝑥_{2} \leq 6 \end{aligned}

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

\nabla 𝑓 (𝑥_{1}, 𝑥_{2}) = [\begin{matrix} 2 (𝑥_{1} - 4) \\ 2 (𝑥_{2} - 2) \end{matrix}] \nabla^{2} 𝑓 (𝑥_{1}, 𝑥_{2}) = [\begin{matrix} 2 & 0 \\ 0 & 2 \end{matrix}]

2 and 4 ✅

ℒ︀ (𝑥_{1}, 𝑥_{2} | 𝜆) = {(𝑥_{1} - 4)}^{2} + {(𝑥_{2} - 2)}^{2} + 𝜆 (6 - 2 𝑥_{2} - 2)

$𝜆 \leq 0$ ✅

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

Case 1. $𝜆 > 0$

Constraint active: $2 𝑥_{2} - 2 \leq 6$

FOC (gradient w.r.t. $𝑥_{1}$ and $𝑥_{2}$ ):

\nabla ℒ︀ (𝑥_{1}, 𝑥_{2} | 𝜆) = [\begin{matrix} 2 (𝑥_{1} - 4) \\ 2 (𝑥_{2} - 2) - 2 𝜆 \end{matrix}]

\begin{matrix} 2 (𝑥_{1} - 4) = 0 \\ 𝑥_{1} = 4 \\ 2 (𝑥_{2} - 2) - 2 𝜆 = 0 \\ 2 𝑥_{2} - 4 - 2 𝜆 = 0 \\ 𝑥_{2} = \frac{2 𝜆 + 4}{2} \\ 𝑥_{2} = 𝜆 + 2 \end{matrix}

\begin{matrix} 𝑥_{1} = 4 \\ 𝑥_{2} = 𝜆 + 2 \end{matrix}

Substitute into active constraint

\begin{matrix} 6 - 2 𝑥_{2} - 2 = 0 \\ 4 - 2 𝑥_{2} = 0 \\ 4 - 2 (𝜆 + 2) = 0 \\ 4 - 2 𝜆 + 4 = 0 \\ 2 𝜆 = 0 \\ 𝜆 = \frac{0}{- 2} \\ 𝜆 = 0 \end{matrix}

Find $𝜆$ :

$𝜆 = 0$

Which violates $𝜆 > 0$

Case 2. $𝜆 = 0$

\begin{matrix} 𝑥_{1} = 4 \\ 𝑥_{2} = 𝜆 + 2 \\ 𝑥_{2} = 0 + 2 \end{matrix}

(𝑥_{1}, 𝑥_{2}) = (4, 2)

$𝑥_{1} - 2 𝑥_{2} = 0$ ✅

Case 2. $𝜆 = 0$

What is a local optimal solution to the nonlinear program?

$(𝑥_{1}, 𝑥_{2}) = (\frac{12}{5}, \frac{6}{5})$ ✅

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. ✅