Optimization: Penalties and Lagrange Multipliers
Claude prompt
This page was generated by Claude Code from the following prompt (with additional prompting):
Let's create a demo to show interior penalty, exterior penalty, and lagrange multipliers on a scalar optimization problem. Use notation consistent with this chapter https://mdobook.github.io/html/constrained/#constrained-problem-formulation
Let's just use inequality constraints and minimize x^2 s.t. x >= 1
The problem is one-dimensional so that everything can be drawn:
\[ \begin{aligned} \underset{x}{\text{minimize}} &\quad f(x) = x^2 \\ \text{subject to} &\quad g(x) = 1 - x \le 0 . \end{aligned} \]The constraint \(x \ge 1\) is written as \(g(x) \le 0\), the convention in the MDO book. The unconstrained minimum \(x = 0\) is infeasible (shaded), so the constrained optimum sits on the boundary, \(x^* = 1\), where the constraint is active. Every method below turns this into an unconstrained problem whose minimizer is marked with a dot; the goal is to see how that dot approaches \(x^*\) as the parameter changes.
Exterior Penalty
Add a quadratic penalty that is zero when the constraint is satisfied and grows with the violation,
\[ \hat f(x;\mu) = f(x) + \frac{\mu}{2}\,\max\!\big(0,\, g(x)\big)^2 , \]and minimize \(\hat f\) instead. Since the penalty only turns on outside the feasible region, the minimizer is always slightly infeasible: here \(2x - \mu(1-x) = 0\) gives \(x = \mu/(2+\mu) < 1\). The penalty parameter is increased between solves, \(\mu_{k+1} = \rho\,\mu_k\) with \(\rho > 1\), and the minimizer approaches \(x^*\) only as \(\mu \to \infty\), at which point \(\hat f\) has a sharp kink and is badly conditioned.
Interior Penalty (Logarithmic Barrier)
Instead, add a penalty that is finite inside the feasible region and blows up at the boundary,
\[ \hat f(x;\mu) = f(x) - \mu \ln\!\big(-g(x)\big) , \]which is only defined for \(g(x) < 0\), so the iterates can never leave the feasible region (hence barrier). The minimizer is always strictly feasible: \(2x - \mu/(x-1) = 0\) gives \(x = \tfrac{1}{2}\big(1 + \sqrt{1 + 2\mu}\big) > 1\). Here \(\mu\) is decreased between solves, \(\mu_{k+1} = \rho\,\mu_k\) with \(\rho < 1\), and the minimizer approaches \(x^*\) as \(\mu \to 0\). The starting point must be feasible.
Lagrange Multipliers
Rather than approximating the constraint with a penalty, form the Lagrangian with a multiplier \(\sigma\) for the inequality constraint,
\[ \mathcal{L}(x, \sigma) = f(x) + \sigma\, g(x) = x^2 + \sigma (1 - x) . \]For a fixed \(\sigma\), \(\mathcal{L}\) is an unconstrained function of \(x\) whose stationary point is where \(\nabla f + \sigma \nabla g = 0\), i.e. \(2x - \sigma = 0\), so \(x = \sigma/2\). The Karush–Kuhn–Tucker (KKT) conditions say the right \(\sigma\) is the one that makes this stationary point feasible with the constraint either inactive (\(\sigma = 0\)) or active (\(g = 0\)):
\[ \nabla f + \sigma \nabla g = 0, \qquad g \le 0, \qquad \sigma\, g = 0, \qquad \sigma \ge 0 . \]Drag \(\sigma\) and watch the stationary point of \(\mathcal{L}\) slide along the parabola. Only at \(\sigma^* = 2\) does it land on the boundary \(g = 0\); for smaller \(\sigma\) it is infeasible and for larger it is feasible but \(\sigma g \neq 0\). The multiplier is the sensitivity of the optimum to the constraint: relaxing it to \(x \ge 1 - \delta\) would reduce \(f^*\) by about \(\sigma^* \delta\).
Unlike the penalty methods, the Lagrangian gives the exact optimum with no limit to take, but it trades the problem of finding \(x\) for the problem of finding \(\sigma\) (and, with several constraints, deciding which are active). Methods such as sequential quadratic programming solve the KKT conditions for \(x\) and \(\sigma\) together.