332. Lagrange Relaxation
2 types of points:
- Interior point
- Boundary point
332.0.1. Single Variate
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), , 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
Derivatives:
Thus, is convex.
FOC solution:
This is the unconstrained minimizer, but it violates :
- Since lies outside the feasible set, the closest feasible point is the boundary .
Evaluation:
So the constrained optimum is at with objective value .
332.0.2. Multi Variate
Example
For this CP, the FOC solution is infeasible
The closest feasible solution is not optimal
Replace hard constraints with soft constraints
Lagrangian
is the Lagrangian multiplier
For a minimization problem
Example
Original NLP
Given the Lagrangian multipliers , the Lagrangian is:
We may then solve
given any .
E.g.:
332.0.3. Bounds
Lagrance relaxation provides bounds for the original NLP
Weak Duality of Lagrangian Relaxation
Proof
Given that for all , the Lagrange dual program is defined as:
The lagrange multipliers are the dual variables in NLP