Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 · Constrained Optimization and Lagrange

Penalty and Barrier Methods

Turn constrained problems into unconstrained ones with quadratic penalties and logarithmic barriers. Implement both, watch the solutions approach the constraint and see the trade-offs.

What if you only have an unconstrained solver such as gradient descent or Newton's method, and no easy projection? You can fold the constraints into the objective. Two classic ideas do that. A penalty charges you for violating a constraint. A barrier makes the cost explode as you approach the constraint from inside, so you never leave. Both lead to a sequence of unconstrained problems whose solutions converge to the constrained optimum.

Quadratic penalty method

For minimize f(x) subject to h(x) = 0, minimize instead

Text
Φ_ρ(x) = f(x) + (ρ/2) h(x)²

with a penalty weight ρ > 0. Violating the constraint costs (ρ/2)h². As ρ → ∞, minimizers of Φ_ρ approach the true constrained solution. The iterates are usually slightly infeasible: they approach the constraint from outside.

Example: minimize x² + y² subject to x + y = 2. The known answer is (1, 1). With the penalty, setting the gradient to zero and using symmetry (x = y): 2x + ρ(2x - 2) = 0, so x = y = ρ / (1 + ρ), which tends to 1. Let the computer confirm.

Python Quadratic penalty as ρ grows

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The violation shrinks as ρ grows, and the solution approaches (1, 1). The price: the problem becomes ill-conditioned for large ρ (the Hessian contains a term of size ρ), so gradient methods slow down. This is why the penalty weight is increased gradually, using each solution as the start for the next.

The inequality penalty

For g(x) ≤ 0 penalize only the violation: (ρ/2)·max(0, g(x))². Inside the feasible set the penalty is zero.

Python Penalty for an inequality

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The iterates sit just outside the feasible set (positive g) and move toward (2.5, 1.5) as ρ increases.

The logarithmic barrier

An interior approach keeps iterates strictly feasible. For g_i(x) ≤ 0, add the barrier -(1/s)·Σ ln(-g_i(x)). The logarithm is defined only when g_i(x) < 0 and blows up to +∞ at the boundary, so a minimizer cannot cross a wall. The weight 1/s is reduced step by step (or s increased). Minimize

Text
Ψ_s(x) = f(x) - (1/s) Σ ln(-g_i(x))

The minimizers x*(s) form the central path. As s → ∞ the barrier's influence fades and x*(s) approaches the true optimum from the inside. For m constraints the suboptimality is at most m/s.

Python Log-barrier central path

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every iterate stays strictly inside the triangle (the slack stays positive) and the path slides toward (2.5, 1.5). This idea, together with Newton's method for each subproblem, is the basis of interior-point methods, the standard way solvers handle linear, quadratic and many other convex programs.

Comparing the two

Property Quadratic penalty Log barrier
Iterates are outside (infeasible) strictly inside (feasible)
Needs a feasible start no yes
Handles equalities yes only inequalities (equalities kept separately)
Ill-conditioning grows as ρ → ∞ grows as s → ∞
Exact answer for finite parameter? no (ρ finite gives approximate) no (always interior)

Both suffer from ill-conditioning in the limit, which is why practical code increases the parameter in stages and warm-starts each stage. A third idea, the augmented Lagrangian, adds a multiplier estimate to the penalty so that exactness is reached with a moderate ρ; it is the base of the ADMM algorithm you will meet in the proximal chapter.

flowchart LR
    A["Constrained problem"] --> B["Add penalty or barrier"]
    B --> C["Solve unconstrained problem"]
    C --> D{"Accurate enough?"}
    D -->|no| E["Increase rho or s"]
    E --> C
    D -->|yes| F["Report solution"]

Outer loop of penalty and barrier methods.

Never jump straight to a huge penalty weight. Start moderate, solve, then multiply the weight by about 10 and warm-start from the previous solution.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In the quadratic penalty method for h(x) = 0 you minimize

    The added term charges for constraint violation and grows as ρ increases.
  2. 2. A log-barrier keeps iterates

    ln(-g) is only defined for g < 0 and tends to infinity at the wall.
  3. 3. Large penalty weights cause

    The Hessian contains a term proportional to ρ, making the curvature very uneven.
  4. 4. The path of barrier minimizers x*(s) is called

    Interior-point methods follow this central path toward the optimum.

Summary

  • A quadratic penalty adds (ρ/2)h² (or (ρ/2)max(0, g)²); solutions approach the constraint from outside as ρ grows.
  • A log barrier -(1/s)Σ ln(-g_i) keeps iterates strictly feasible; the minimizers form the central path.
  • Both create ill-conditioned subproblems for extreme parameters, so increase the parameter gradually and warm-start.
  • Barrier methods lead to interior-point solvers, the workhorse for linear and quadratic programs.

Next: The Lagrangian and the Dual Function