Penalty and Barrier Methods

Many optimization problems come with constraints: minimize a cost function, but only over inputs satisfying certain limits (a budget, a capacity, a non-negativity rule). Solvers built for unconstrained problems don't understand constraints directly, so penalty and barrier methods convert a constrained problem into a series of unconstrained ones that a standard solver can handle, gradually enforcing the constraint as the series progresses.

A penalty method adds a term to the objective that costs nothing while the constraint is satisfied but grows large the moment it's violated, so the solver is discouraged from crossing the boundary rather than forbidden from it — early iterations may briefly stray outside the feasible region before being pushed back in as the penalty is made harsher. A barrier method does the opposite: it adds a term that blows up to infinity as the solution approaches the constraint boundary from the feasible side, so the solver, if it starts inside the feasible region, can never cross out — the boundary looks like an impassable wall rather than a costly one.

Worked example. To minimize $f(x)$ subject to $x \geq 0$, a barrier method instead minimizes $f(x) - \mu \ln(x)$ for a small positive $\mu$: as $x$ shrinks toward zero, $-\ln(x)$ grows without bound, repelling the solver away from the boundary. Solving this unconstrained problem repeatedly while shrinking $\mu$ toward zero drives the solution toward the true constrained optimum.