Optimization

Penalty Methods

Convert constraints into a penalty term added to the objective, then solve a sequence of unconstrained problems with growing penalty.

The idea

Penalty methods turn a constrained problem into unconstrained ones by adding a term that grows when constraints are violated. For equality constraints h(x) = 0, the quadratic penalty is P(x) = f(x) + (mu/2) sum h_j(x)^2. As the penalty weight mu increases, minimizers of P are driven toward feasibility.

Exterior penalties

The quadratic penalty is an exterior method: intermediate iterates are typically infeasible and approach the feasible set from outside as mu grows. One solves a sequence of subproblems with increasing mu, warm-starting each from the previous solution. In the limit mu -> infinity the solution satisfies the constraints.

The ill-conditioning problem

As mu grows large, the penalized objective becomes badly conditioned, and its Hessian has eigenvalues that scale with mu.
This makes the unconstrained subproblems progressively harder to solve accurately.
Exact convergence requires mu -> infinity, which is numerically problematic.

Exact penalties

The nonsmooth L1 penalty f(x) + mu * sum |h_j(x)| is an exact penalty: for a finite mu above a threshold, its minimizer coincides with the constrained optimum. The price is non-differentiability at the constraint boundary, requiring specialized nonsmooth solvers.

Inequality constraints

For g_i(x) <= 0, a common penalty is (mu/2) sum max(0, g_i(x))^2, which activates only when a constraint is violated. Penalty methods are simple to implement and robust, but the augmented Lagrangian method avoids their ill-conditioning by adding explicit multiplier estimates, which is usually preferred in practice.

python

def penalized(x, mu):
    return f(x) + 0.5*mu*sum(hj(x)**2 for hj in H) \
           + 0.5*mu*sum(max(0.0, gi(x))**2 for gi in G)

Penalty formulations offer a simple first approach to constrained design, later refined by augmented-Lagrangian or interior-point solvers for accuracy.