Lagrange Relaxation

335. Lagrange Relaxation

2 types of points:

For constrained single variate:

Check convexity: Verify whether the objective function is convex by inspecting the second derivative. Convexity ensures that any stationary point is a global minimum
Find unconstrained minimizer: Solve the first-order condition (FOC), $𝑓^{'} (𝑥) = 0$ , to identify the unconstrained optimal solution $𝑥^{*}$ .
Apply feasibility:
- If $𝑥^{*}$ lies within the feasible region, it is the constrained optimum.
- If $𝑥^{*}$ is infeasible, the constrained optimum is attained at the feasible boundary point closest to $𝑥^{*}$ (since convexity guarantees the function grows monotonically away from the minimizer).

Example

min_{𝑥 \geq 0} 𝑓 (𝑥) = 𝑥^{2} + 2 𝑥 - 3

Derivatives:

\begin{matrix} 𝑓^{'} (𝑥) = 2 𝑥 + 2 \\ 𝑓^{″} (𝑥) = 2 \end{matrix}

Thus, $𝑓$ is convex.

FOC solution:

𝑓^{'} (𝑥) = 0 \Rightarrow 𝑥^{*} = - 1

This is the unconstrained minimizer, but it violates $𝑥 \geq 0$ :

Since $𝑥^{*} = - 1$ lies outside the feasible set, the closest feasible point is the boundary $𝑥 = 0$ .

Evaluation:

𝑓 (0) = - 3

So the constrained optimum is at $𝑥 = 0$ with objective value $- 3$ .

Example

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

For this CP, the FOC solution $𝑥 = (2, 1)$ is infeasible

The closest feasible solution is not optimal

\begin{aligned} 𝑧^{*} = max_{𝑥 \in ℝ^{𝑛}} & 𝑓 (𝑥) \\ 𝑠 . 𝑡 . & 𝑔_{𝑖 (𝑥)} \leq 𝑏_{𝑖} \forall 𝑖 = 1, \dots, 𝑚 \end{aligned}

Replace hard constraints with soft constraints

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

Lagrangian

ℒ︀ (𝑥 | 𝜆) = 𝑓 (𝑥) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖} [𝑏_{𝑖} - 𝑔_{𝑖 (𝑥)}]

$𝜆_{𝑖}$ is the Lagrangian multiplier

For a minimization problem

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

\begin{matrix} 𝑧^{𝐿} (𝜆) = max_{𝑥 \in ℝ^{𝑛}} 𝑓 (𝑥) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖} [𝑏_{𝑖} - 𝑔_{𝑖 (𝑥)}] \\ 𝜆_{𝑖} \leq 0 \end{matrix}

Example

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

Original NLP

𝑧^{*} = max_{𝑥 \in ℝ^{2}} {𝑥_{1} + 𝑥_{2} | 𝑥_{1}^{2} + 𝑥_{2}^{2} \leq 8, 𝑥_{2} \leq 6}

Given the Lagrangian multipliers $𝜆 = {𝜆_{1}, 𝜆_{2}} \geq 0$ , the Lagrangian is:

ℒ︀ (𝑥 | 𝜆) = \underset{𝑓}{\underset{⏟}{𝑥_{1} + 𝑥_{2}}} + 𝜆_{1} \underset{𝑏_{1} - 𝑔_{1}}{\underset{⏟}{(8 - 𝑥_{1}^{2} - 𝑥_{2}^{2})}} + 𝜆_{2} \underset{𝑏_{2} - 𝑔_{2}}{\underset{⏟}{(6 - 𝑥_{2})}}

We may then solve

𝑧^{𝐿} (𝜆) = max_{𝑥 \in ℝ^{2}} ℒ︀ (𝑥 | 𝜆)

given any $𝜆 \geq 0$ .

E.g.:

Lagrance relaxation provides bounds for the original NLP

Weak Duality of Lagrangian Relaxation

𝑧^{𝐿} (𝜆) \geq 𝑧^{*} \forall 𝜆 \geq 0

Proof

\begin{aligned} 𝑧^{*} & = max_{𝑥 \in ℝ^{𝑛}} = {𝑓 (𝑥) | 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} \forall 𝑖 = 1, \dots, 𝑚} \\ \leq max_{𝑥 \in ℝ^{𝑛}} = {𝑓 (𝑥) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖} [𝑏_{𝑖} - 𝑔_{𝑖} (𝑥)] | 𝑔_{𝑖} (𝑥) \leq 𝑏_{𝑖} \forall 𝑖 = 1, \dots, 𝑚} \\ \leq max_{𝑥 \in ℝ^{𝑛}} = {𝑓 (𝑥) + \sum_{𝑖 = 1}^{𝑚} 𝜆_{𝑖} [𝑏_{𝑖} - 𝑔_{𝑖} (𝑥)]} = 𝑧^{𝐿} (𝜆) \end{aligned}

Given that $𝑥^{𝐿} (𝜆) \geq 𝑧^{*}$ for all $𝜆 \geq 0$ , the Lagrange dual program is defined as:

min_{𝜆 \geq 0} 𝑧^{𝐿} (𝜆)

The lagrange multipliers are the dual variables in NLP