Recipe

Solve a constrained problem with a penalty function

Use when: you have inequality (or equality) constraints and want to reuse an ordinary unconstrained solver rather than build a constrained one from scratch

Goal: a sequence of unconstrained minimizers that converges to the constrained optimum as the penalty weight grows

Taught in Penalty methods

1. 1

   For each inequality constraint g_i(x)\le0, add \rho\,[\max(0,g_i(x))]^2 to the objective. For an equality constraint h_j(x)=0, add \rho\,h_j(x)^2 instead, since any nonzero h_j is already a violation.

   Example

   For \min x^2+y^2 s.t. x+y\ge4: P(x,y;\rho)=x^2+y^2+\rho\,[\max(0,4-x-y)]^2.

   Why: squaring keeps the penalty differentiable at the constraint boundary, so any unconstrained solver applies without modification.

2. 2

   Choose a starting penalty weight \rho_0 (often 1) and any starting point x_0, feasible or not.

   Why: a penalty method never requires a feasible start, unlike the barrier method in Section 4.

3. 3

   Run an unconstrained method (gradient descent, Newton, or a quasi-Newton method from Chapter 4) on P(x;\rho_k), starting from the previous solution x(\rho_{k-1}).

   Why: warm-starting keeps each subproblem's solve fast, since the minimizer moves only a little as ρ grows.

4. 4

   Compute \max(0,g(x_k)), the amount by which the current point still breaks the constraint.

   • the violation is still larger than your tolerance — increase \rho (commonly \rho_{k+1}=10\rho_k) and repeat the previous step.
   • the violation is acceptably small — stop; x_k is your answer.

   ⚡ Shortcut

   When f is quadratic and every constraint is linear, as in this chapter's running example, the penalized subproblem's stationarity condition is itself linear. Solve it directly in closed form for each \rho instead of running an iterative solver at all.

   Why: checking how far outside the fence the current point sits is the one thing that actually tells you whether to stop or push \rho higher.