Optimization · Module 8 of 10
Quadratic Programming and Penalty Methods
A quadratic objective with linear constraints is solved by one linear system, its KKT equations. When constraints are awkward, penalty and barrier methods fold them into the objective and solve a sequence of easier problems.
Readiness check
This module solves quadratic problems and penalises constraints. Tick only what you can do closed-notes.
- Write the KKT stationarity condition.
- Solve a small linear system.
- Minimise a one-variable quadratic.
- Recall a Lagrange multiplier as a shadow price.
- Take a limit as a parameter grows large.
The core idea
An equality-constrained quadratic program is solved by one linear KKT system. Penalty and barrier methods handle general constraints by adding a term to the objective and solving a sequence of unconstrained problems.
QP: minimise ½xTGx + cTx s.t. Ax = bKKT: ∇f + ATλ = 0, Ax = bpenalty: minimise f + ½μ·(constraint)2A quadratic program (QP) minimises a quadratic objective ½xTGx + cTx subject to linear constraints, the model behind least squares with constraints, portfolio design, and the subproblems of sequential quadratic programming. With equality constraints, the KKT conditions, stationarity of the Lagrangian and feasibility, are themselves linear, so the QP is solved by one linear system in the variables and multipliers together. General constraints, especially inequalities, are harder, and one powerful family avoids them altogether. The quadratic penalty method replaces the constrained problem by an unconstrained one, minimising f(x) + ½μ·c(x)2, where the penalty parameter μ punishes constraint violation; as μ grows the solution is driven onto the constraint. Barrier (interior-point) methods instead add a term that blows up at the boundary, keeping iterates strictly feasible. Both solve a sequence of unconstrained problems, and the augmented Lagrangian improves them by adding a multiplier estimate so μ need not go to infinity.
The skills, taught in order
Five skills build the QP, its KKT system, and the penalty and barrier reformulations.
8.1 The quadratic program
A QP minimises ½xTGx + cTx subject to linear constraints. When G is positive definite the objective is convex and the QP has a unique minimum. QPs are the workhorse subproblem of larger nonlinear solvers.
8.2 The KKT linear system
For an equality-constrained QP the KKT conditions are linear: Gx + c + ATλ = 0 together with Ax = b. Stacking them gives one linear system in x and λ, solved directly, no iteration needed for the convex case.
| Method | Handles | Idea |
|---|---|---|
| KKT system | equality-constrained QP | solve one linear system |
| Quadratic penalty | general constraints | add ½μ·c2 to f |
| Barrier | inequality constraints | add a term that blows up at the boundary |
| Augmented Lagrangian | general constraints | penalty plus a multiplier estimate |
From an exact linear solve for a QP to sequential unconstrained methods for harder constraints.
8.3 The quadratic penalty method
The quadratic penalty method minimises f(x) + ½μ·c(x)2 for increasing μ. Each subproblem is unconstrained; as μ grows, violating the constraint becomes too costly, so the minimiser approaches the constrained optimum. The penalty is exact only in the limit.
8.4 Barrier and interior-point methods
Barrier methods add a term, such as −Σ log(−gi), that grows without bound as an inequality boundary is approached, keeping iterates strictly inside the feasible region. Reducing the barrier parameter traces a path to the optimum, the basis of modern interior-point solvers.
8.5 The augmented Lagrangian
The augmented Lagrangian adds a Lagrange-multiplier term to the penalty, minimising f + λTc + ½μ·c2 and updating λ each round. This lets the constraint be satisfied without driving μ to infinity, curing the ill-conditioning of the pure penalty method.
Engineering connection: penalty and barrier methods are how a solver enforces stress or displacement limits when they cannot be handled directly, and QPs are the inner step of the design optimisers in the next module.
Worked example 1: an equality-constrained QP by KKT
Minimise f(x, y) = x2 + y2 − 2x − 4y subject to x + y = 1. Solve the KKT linear system for the optimum and the multiplier.
- ProblemSolve the equality-constrained QP in Figure 1 by its KKT system.
- Given / findf = x2 + y2 − 2x − 4y, constraint x + y = 1. Find x, y, and λ.
- AssumptionsConvex QP (G = 2I positive definite), so the KKT point is the unique minimum.
- ModelStationarity ∇f + λ∇h = 0 with h = x + y − 1: 2x − 2 + λ = 0, 2y − 4 + λ = 0, x + y = 1.
- Equations2x − 2 + λ = 0, 2y − 4 + λ = 0x + y = 1
- SolveSubtracting the first two: 2x − 2y + 2 = 0, so x − y = −1. With x + y = 1: x = 0, y = 1. Then 2(0) − 2 + λ = 0 gives λ = 2. f = 0 + 1 − 0 − 4 = −3.
- CheckThe unconstrained minimum is (1, 2); the constraint pulls the solution to (0, 1) on the line x + y = 1, and the positive multiplier λ = 2 measures how binding it is.
- ConclusionThe QP optimum is (0, 1), f = −3, with multiplier 2, all from one linear solve. Equality-constrained QPs need no iteration.
Worked example 2: the quadratic penalty method
Solve the constrained problem minimise f(x) = x2 subject to x = 1 by the quadratic penalty method. Minimise P(x, μ) = x2 + ½μ(x − 1)2 and show the solution approaches x = 1 as μ grows, at μ = 8 and μ = 98.
- ProblemSolve the constrained problem in Figure 2 by the quadratic penalty method.
- Given / findMinimise x2 subject to x = 1. Find the penalty minimiser at μ = 8 and μ = 98.
- AssumptionsThe penalty subproblem is minimised exactly for each fixed μ.
- ModelP(x, μ) = x2 + ½μ(x − 1)2; set dP/dx = 0.
- EquationsdP/dx = 2x + μ(x − 1) = 0x(μ) = μ/(2 + μ)
- Solvex(μ) = μ/(2 + μ). At μ = 8: x = 8/10 = 0.8. At μ = 98: x = 98/100 = 0.98. As μ → ∞, x → 1, the constrained answer.
- CheckEach subproblem is unconstrained yet the sequence approaches x = 1, so the constraint is satisfied only in the limit. The pure penalty needs a large μ, which eventually ill-conditions the subproblem, the reason for the augmented Lagrangian.
- ConclusionThe penalty method converts a constrained problem into a sequence of unconstrained ones, whose solutions march onto the constraint as μ increases.
Misconceptions and diagnostics
| Mistake | Symptom | Diagnostic question | Correction |
|---|---|---|---|
| Iterating an equality QP | Slow solve of a linear system | "Are the KKT conditions linear?" | Solve the KKT system directly. |
| Penalty exact at finite μ | Constraint slightly violated | "Is the constraint met only in the limit?" | The quadratic penalty is exact only as μ → ∞. |
| Pushing μ too high | Subproblem ill-conditioned | "Is the Hessian blowing up?" | Use an augmented Lagrangian to bound μ. |
| Barrier iterate on the boundary | Log term undefined | "Am I strictly feasible?" | Barrier methods must stay inside the region. |
Practice ladder
For the penalty P(x, μ) = x2 + ½μ(x − 1)2, find x at μ = 2.
Show answer
x = μ/(2 + μ) = 2/4 = 0.5.
What μ gives x = 0.9 for that penalty?
Show answer
0.9 = μ/(2 + μ) ⇒ 0.9(2 + μ) = μ ⇒ 1.8 = 0.1μ ⇒ μ = 18.
Minimise x2 + y2 subject to x + y = 2 by the KKT system.
Show answer
2x + λ = 0, 2y + λ = 0, x + y = 2 ⇒ x = y = 1, λ = −2, f = 2.
A solver enforces a stress limit by penalising violation. Explain why the answer is slightly infeasible and how an augmented Lagrangian fixes it.
What good work looks like
A quadratic penalty satisfies the constraint only as μ → ∞, so at finite μ the stress limit is slightly exceeded. The augmented Lagrangian adds a multiplier estimate, letting the constraint be met exactly at a moderate μ without ill-conditioning.
Working with AI, and proving it yourself
Use AI as an examiner, not a solver
Portfolio task
Solve a small constrained problem two ways, by the KKT system and by a penalty sequence, and show both give the same optimum as the penalty grows.
Retrieval and spaced review
Closed notes. Answer out loud, then reveal.
1. What is a quadratic program?
Minimising a quadratic objective subject to linear constraints.
2. How is an equality-constrained QP solved?
By solving its linear KKT system for the variables and multipliers.
3. What does the quadratic penalty method minimise?
f(x) + ½μ·c(x)2, for increasing μ.
4. How do barrier methods keep feasibility?
They add a term that grows without bound at the constraint boundary.
5. What does the augmented Lagrangian add?
A multiplier estimate, so the constraint is met without μ → ∞.
Textbook mapping
This module follows Nocedal and Wright, Numerical Optimization, 2nd edition. Use these references to read further.
| Topic in this module | Where to read more |
|---|---|
| Quadratic programming and the KKT system | Nocedal & Wright, Chapter 16 |
| Penalty and barrier methods | Nocedal & Wright, Chapter 17 |
| The augmented Lagrangian | Nocedal & Wright, Chapter 17 |
Chapter numbers refer to the 2nd edition. The QP and penalty methods are standard, so any recent edition will align closely.