Optimization for Optimal Control

Comprehensive Study Notes: Root Finding, Newton’s Method, Line Search,

Constrained Minimization, and Algorithms for Constrained Optimization

Compiled from Lecture 3, Lecture 4 & Lecture 5

How to use these notes

Every idea below is broken into five parts: what it is, how to see it, what the formula says,
why the formula is built that way, and where students trip up. Read the Intuition box before
the Math box — the geometry is what makes the algebra inevitable rather than arbitrary.

Contents
1 The Big Picture: Two Related Problems 3

2 Notation Conventions 3

3 Root Finding 4
3.1 Fixed-Point Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Newton’s Method (Root Finding) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Unconstrained Minimization 7
4.1 Sufficient Conditions: Reading the Curvature . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Regularization (“Damped Newton”) . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

5 Line Search 10
5.1 The Armijo Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

6 Constrained Minimization: Equality Constraints 11

6.1 First-Order Necessary Conditions — Geometric Derivation . . . . . . . . . . . . . . 12
6.2 The Lagrangian and the KKT System . . . . . . . . . . . . . . . . . . . . . . . . . . 13
6.3 Solving the KKT System with Newton’s Method . . . . . . . . . . . . . . . . . . . . 14
6.4 Gauss–Newton: A Cheaper Approximation . . . . . . . . . . . . . . . . . . . . . . . 14

7 Constrained Minimization: Inequality Constraints 15

7.1 The KKT Conditions for Inequality Constraints . . . . . . . . . . . . . . . . . . . . . 16
7.2 Combining Both Constraint Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

8 Algorithms for Constrained Minimization 18

8.1 Active-Set Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
8.2 Barrier / Interior-Point Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Optimization & Optimal Control — Study Notes 2

8.3 Penalty Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

8.4 Augmented Lagrangian Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

9 Quadratic Programs (QPs) 23

10 Regularization and Duality: The Min-Max View 24

11 Merit Functions: Line Search for Constrained Problems 26

11.1 Merit Functions for Root Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
11.2 Merit Functions for Constrained Minimization . . . . . . . . . . . . . . . . . . . . . . 27

12 Putting It All Together: The Unified Algorithm 28

Optimization & Optimal Control — Study Notes 3

1 The Big Picture: Two Related Problems

Almost everything in this course reduces to one of two problems:

Root Finding Minimization

Find x∗ such that f (x∗ ) = 0 Find x∗ that minimizes f (x)

These are not two separate topics — they are the same topic wearing different clothes. If f (x) is
smooth, the minimum of f occurs where its gradient vanishes: ∇f (x∗ ) = 0. That is a root-finding
problem in disguise (the root of the function ∇f ). Every method in this document ultimately reuses
Newton’s Method for root finding as its engine, whether we are chasing a zero, an unconstrained
minimum, or a constrained minimum with equality/inequality side-conditions.

2 Notation Conventions
The Concept

Before any calculus, we fix bookkeeping rules so that matrix/vector shapes are always con-
sistent and the chain rule “just works” without you having to guess whether something is a
row or a column.

The Intuition (Visual / Geometric)

Think of ∂f /∂x as the machine that converts a small step δx into the resulting small change
δf . Since f is scalar-valued, this machine eats a vector and spits out a single number —
exactly the job of a row vector multiplying a column vector.

The Math
For f (x) : Rn → R:
∂f ∂f
∈ R1×n (a row vector), f (x + δx) ≈ f (x) + δx.
∂x ∂x
For g(y) : Rm → Rn :
∂g ∂g
∈ Rn×m , g(y + δy) ≈ g(y) + δy.
∂y ∂y
This convention makes composition (chain rule) type-check automatically:

∂f ∂g
f (g(y + δy)) ≈ f (g(y)) + δy.
∂x g(y) ∂y y

We separately define the gradient as the column vector

 T
∂f
∇f (x) = ∈ Rn×1 ,
∂x
Optimization & Optimal Control — Study Notes 4

and the Hessian as

∂
∂2f
∇2 f (x) = ∇f (x) = ∈ Rn×n .
∂x ∂x2

The “Why”

Two different objects (∂f /∂x vs. ∇f ) exist because they serve two different jobs. The row
version is a linear operator (it directly multiplies a step to predict a change — Jacobian-style
bookkeeping). The column version, ∇f , is what we actually add/subtract to a point x (also
a column vector) when we take an optimization step, e.g. x ← x − α∇f (x). You cannot add
a row vector to a column vector, so the transpose is not cosmetic — it’s what makes “take
a step in the gradient direction” dimensionally legal.

Common Pitfalls
ˆ Writing ∇f and ∂f /∂x interchangeably. They are transposes of each other; mixing them
up silently breaks matrix dimensions in code (a very common MATLAB bug).
ˆ Forgetting that ∇2 f is defined by differentiating the column gradient, so its rows/columns
are symmetric for smooth f (Hessian symmetry is a feature, not a coincidence — it comes
from equality of mixed partials).

3 Root Finding
The Concept

Given a function f (x), find the point(s) x∗ where f (x∗ ) = 0. A closely related idea is a fixed
point: a point where f (x∗ ) = x∗ (the function maps the point to itself). Root finding shows
up constantly in dynamics: the equilibrium of a continuous-time system ẋ = f (x) is a root
of f ; the equilibrium of a discrete-time system xk+1 = f (xk ) is a fixed point of f .

The Intuition (Visual / Geometric)

Picture the graph of f (x) crossing the x-axis. Root finding is the search for that crossing
point. For fixed points, picture the graph of f (x) against the line y = x: a fixed point is
where the curve intersects that diagonal line.

3.1 Fixed-Point Iteration

The Math

x ← f (x), repeat until x stops changing.

Optimization & Optimal Control — Study Notes 5

The Intuition (Visual / Geometric)

Imagine standing at a guess x0 , plugging it into f , landing at a new point x1 = f (x0 ), then
repeating. If the fixed point is stable (nearby points get pulled toward it, like a ball rolling
into a bowl), this process spirals inward and converges. If it is unstable (like a ball balanced
on a hill), any small error grows and you fly away from the answer.

The “Why”

This is the simplest possible idea: “just run the dynamics forward and see where they settle.”
It requires zero calculus. But convergence is only guaranteed near stable fixed points, and
even then it can be slow because the *rate* at which the error shrinks depends only on how
strongly attracting the fixed point is (governed by |f ′ (x∗ )| < 1) — there’s no mechanism
accelerating convergence.

Common Pitfalls
ˆ Applying fixed-point iteration to an unstable equilibrium and being confused when it
diverges. Physical unstable equilibria (e.g., an inverted pendulum) will not be found this
way.
ˆ Assuming fast convergence — it is typically linear (slow) convergence at best.

3.2 Newton’s Method (Root Finding)

The Concept

A far faster way to find a root: instead of blindly iterating f , use local slope information to
aim directly at the axis crossing.

The Intuition (Visual / Geometric)

Stand on the curve f (x) at your current guess x. Draw the tangent line at that point. That
tangent line is a much simpler object than the true curve — and you can solve, in one step,
exactly where the tangent line crosses zero. Walk to that crossing point, redraw the tangent,
and repeat. Each step, you are replacing a hard curved problem with an easy straight-line
problem.
Optimization & Optimal Control — Study Notes 6

f (x)

x
x + δx
x
tangent line f (x)

The Math
Linearize f at the current point x:

∂f
f (x + δx) ≈ f (x) + δx.
∂x x

Set this linear approximation to zero and solve for δx:

 −1
∂f ∂f
f (x) + δx = 0 =⇒ δx = − f (x).
∂x ∂x

Apply the correction and repeat until convergence:

x ← x + δx.

The “Why”

Why linearize? Because a straight line is the only function whose root you can compute
in closed form without further iteration. Newton’s method is therefore an infinite loop of
“pretend the function is linear right here, solve that easy problem exactly, then re-linearize
at the new point.” Because the tangent line hugs the true curve extremely well close to the
root, the errors shrink quadratically once you’re near x∗ — informally, the number of correct
digits roughly doubles every iteration. This is dramatically faster than fixed-point iteration’s
linear convergence.

Common Pitfalls
ˆ Newton is a local method. It converges to whichever root/fixed point is closest to your
initial guess — not necessarily the one you wanted. Different starting points can converge
to entirely different solutions (or diverge).
ˆ Forgetting that ∂f /∂x must be invertible (nonsingular) at each step, or the update is
undefined.
ˆ In practice (e.g., Backward Euler), Newton converges extremely fast — but this speed is
Optimization & Optimal Control — Study Notes 7

a local property near the root, not a global guarantee.

4 Unconstrained Minimization
The Concept

Given f (x) : Rn → R, find x that minimizes f . The key trick: convert this into a root-finding
problem by recognizing that at a smooth local minimum, the gradient must vanish.

The Intuition (Visual / Geometric)

Imagine f (x) as the elevation of a landscape and you are standing on it. At the very bottom
of a valley, the ground is momentarily flat in every direction — if you took a tiny step any
direction, your elevation wouldn’t change to first order. That flatness is ∇f (x∗ ) = 0. (The
same flatness happens at the top of a hill or at a mountain pass/saddle — which is exactly
why this condition is necessary but not sufficient, see below.)

The Math
If f is smooth, at a local minimum x∗ :

∂f
= 0.
∂x x∗

This is a root-finding problem in ∇f (x) = 0, so we apply Newton’s method to the gradient

rather than to f itself:
∂
∇f (x) δx = ∇f (x) + ∇2 f (x) δx = 0


∇f (x + δx) ≈ ∇f (x) +
∂x | {z }
Hessian

−1
=⇒ δx = − ∇2 f (x) ∇f (x), x ← x + δx, repeat.

Intuition: Fitting a Bowl

Rather than thinking of this as “root-finding on the gradient,” picture it directly: at each
iterate, fit a quadratic (paraboloid / bowl) approximation to f (x) using its value, slope, and
curvature at that point. Then jump straight to the exact bottom of that bowl. Since a
quadratic bowl has one obvious minimum you can compute in closed form, each Newton step
is “approximate the landscape locally as a bowl, teleport to the bottom of the bowl, repeat.”

The “Why”

Why does this work? A quadratic function is the simplest function that actually has a well-
defined minimum (a line has none). By matching both the slope (∇f ) and curvature (∇2 f ) of
Optimization & Optimal Control — Study Notes 8

the true function, the fitted bowl is the best possible local quadratic model, so jumping to its
minimum is the best available guess for where the true minimum lies. As with root-finding,
this converges quadratically near a true local min.

Common Pitfalls
ˆ ∇f (x∗ ) = 0 is necessary, NOT sufficient. Newton’s method run on the gradient will
happily converge to a maximum or a saddle point too, since those are also flat points. In
the lecture example f (x) = x4 + x3 − x2 − x, starting at x0 = −1.5 actually converges to
a maximizer, not a minimizer! Always check second-order conditions (sign of curvature)
afterward.
ˆ Confusing “Newton converged” with “Newton found a minimum.”

4.1 Sufficient Conditions: Reading the Curvature

The Concept

The sign of the second derivative (in 1D) or the definiteness of the Hessian (in Rn ) tells you
whether a flat point is a minimum, maximum, or saddle — and it also tells you whether the
Newton step will move toward or away from a minimum.

The Intuition (Visual / Geometric)

The Newton step is
−1

δx = − ∇2 f ∇f .
| {z } |{z}
“descent” direction if positive gradient

The gradient always points uphill (direction of steepest increase). So −∇f always points
downhill. The Hessian term then rescales that downhill direction: if curvature is positive
(bowl-shaped, like the bottom of a valley), the rescaling keeps you moving downhill (descent)
— good, you’re minimizing. If curvature is negative (dome-shaped, like the top of a hill), the
same formula flips the direction into an ascent step — you’d actually be maximizing without
realizing it, because the algebra doesn’t know which one you wanted; it just marches toward
the nearest flat point.

The Math
In Rn :
∇2 f ≻ 0 (positive definite) =⇒ descent (minimization),
∇2 f ≺ 0 =⇒ ascent (maximization).
If ∇2 f (x) ≻ 0 for all x (i.e., f is strongly convex), Newton’s method is guaranteed to
converge reliably — but this global positive-definiteness is a strong assumption, rarely true
for hard/nonlinear problems.
Optimization & Optimal Control — Study Notes 9

Common Pitfalls
ˆ Assuming most real (nonlinear, engineering) problems are globally convex. They usually
are not — positive definiteness of the Hessian typically only holds locally, near a minimum.

4.2 Regularization (“Damped Newton”)

The Concept

A practical fix so that Newton’s method always takes a descent step (moves toward lower
f ), even when the true Hessian is not positive definite at the current point.

The Intuition (Visual / Geometric)

If the landscape is curved like a saddle (bowl in one direction, dome in another) at your cur-
rent location, the raw Newton step might march you uphill in some direction. Regularization
artificially “inflates” the curvature in every direction — imagine reshaping the local land-
scape by adding a generic upward-curving bowl on top of it — until the combined shape is
bowl-like everywhere. This guarantees your next step goes downhill, even if it means taking
a smaller, more cautious step.

The Math

H ← ∇2 f
while H ̸≻ 0 :
H ← H + βI (β > 0 a scalar hyperparameter)
end
δx = −H −1 ∇f, x ← x + δx.

The “Why”

Adding βI shifts every eigenvalue of H up by β (since eigenvalues of H + βI are λi (H) + β).

Enough of this shift eventually forces all eigenvalues positive, i.e., H ≻ 0, i.e., a legitimate
bowl shape. This is called “damped” Newton because as β → ∞, the step direction ap-
proaches plain gradient descent (small, cautious, guaranteed-downhill steps) rather than the
aggressive full Newton jump — trading speed for guaranteed safety.

Common Pitfalls
ˆ Regularization guarantees a descent direction, but not that the step size is good — an
overly large step can still overshoot the minimum. That’s exactly the motivation for Line
Search (next section).
ˆ Choosing β too large makes convergence painfully slow (you lose Newton’s quadratic speed
and approach plain gradient descent); too small may not fix indefiniteness.
Optimization & Optimal Control — Study Notes 10

5 Line Search
The Concept

Even after regularization guarantees the Newton step points downhill, the full step length
(α = 1) can be too aggressive and overshoot the minimum, actually increasing f . Line search
shrinks the step length along that same direction until we get a “good enough” reduction.

The Intuition (Visual / Geometric)

Think of the Newton step direction δx as a compass bearing — it correctly points downhill
— but the raw step length is like taking one giant leap in that direction without looking at
your feet. You might leap clean over the valley floor and land higher up the opposite wall
than where you started. Line search says: take a step in that correct direction, check whether
you actually landed lower; if not, take a smaller step (“backtrack”); keep shrinking until you
land somewhere satisfactorily lower.

true f (x + αδx)
f (x) + b α ∇f T δx (Armijo line)
f (x + α δx)

α = 1 overshoots

accepted α

0 1
step length α

5.1 The Armijo Rule

The Math

α←1 (“step length,” start full-size)

while f (x + α δx) > f (x) + b α ∇f (x)T δx :
α ← cα (c < 1 a scalar shrink factor)
end

Typical values: c = 12 , b = 10−4 to 0.1 (the tolerance).

Intuition: What the Armijo Condition Actually Compares

The right-hand side, f (x) + b α ∇f T δx, is the linearized prediction of how much f should
drop, based on the gradient, scaled down by a tolerance factor b ≪ 1. The Armijo test says:
Optimization & Optimal Control — Study Notes 11

“accept this step length only if the actual drop in f is at least a modest fraction (b) of what
the linear (first-order) prediction promised.” If α = 1 overshoots so badly that the actual f
value is higher than even this lenient target, we haven’t earned the right to trust that step
— shrink α and try again.

The “Why”

Why not just require f (x + αδx) < f (x) (any decrease at all)? Because that criterion is too
weak — it can accept absurdly tiny steps that make negligible progress, stalling convergence.
Why not require matching the full linear prediction exactly? Because near a curved region the
true function will always eventually deviate from any straight-line prediction — demanding
exact agreement would reject every step. The Armijo rule threads the needle: by discounting
the linear prediction with a small tolerance b, it demands “real, non-trivial progress” without
demanding perfection matching an approximation that was never meant to be exact.

Why This Combination Is Powerful

This is a cheap, simple modification (“globalization strategy”) layered on top of Newton’s

method. It doesn’t change the direction of the step at all (which Newton/regularization
already computed correctly) — it only tunes the step’s size. This combination (regularized
Hessian for a good direction + Armijo backtracking for a good length) is extremely effective at
reliably finding local optima in practice, even for genuinely nonlinear, non-convex problems.

Common Pitfalls
ˆ Thinking line search picks a new direction. It doesn’t — it only rescales the same δx
direction that Newton computed.
ˆ Choosing b too close to 1 makes the condition almost impossible to satisfy (over-cautious,
tiny steps); choosing b too close to 0 makes it nearly always satisfied (defeats the purpose).

6 Constrained Minimization: Equality Constraints

The Concept

Now we minimize f (x) but restrict x to lie exactly on some surface defined by c(x) = 0. This
is the mathematical model for problems like “minimize fuel use subject to landing exactly at
a target waypoint.”

The Math

min f (x), f (x) : Rn → R, s.t. c(x) = 0, c(x) : Rn → Rm .

x
Optimization & Optimal Control — Study Notes 12

6.1 First-Order Necessary Conditions — Geometric Derivation

The Intuition (Visual / Geometric)

This is the single most important picture in constrained optimization, so build it carefully.
Draw the level curves (contours) of f (x) in 2D — concentric rings, like a topographic map,
centered on the unconstrained minimum. Now draw the constraint curve c(x) = 0 as some
curved path snaking through this landscape (think of it as a fence you are not allowed to
leave). You are only allowed to stand on the fence, and you want the lowest point on the
fence.
c(x) = 0
∇f
level
∇ccurves of f (x)

x∗

Walk along the fence. At almost every point on the fence, the level curves cross it at an
angle — meaning that if you take a small step along the fence in one direction, f decreases,
and in the other direction, f increases. As long as that’s true, you can always improve by
shuffling further along the fence. The walk only stops paying off at the exact spot where the
fence is tangent to a level curve — where the fence, for an instant, runs perfectly parallel
to a contour line. At that tangent point, moving either way along the fence keeps f (to first
order) unchanged; you’ve found a local optimum on the constraint.

The “Why”

Tangency between the constraint curve and a level curve is the geometric heart of constrained
optimization. Two curves are tangent exactly when their normal vectors are parallel (point
along the same line, possibly opposite directions). The gradient ∇f is always normal (per-
pendicular) to f ’s level curves, and ∇c is always normal to the constraint curve c(x) = 0.
So “tangency” translates directly into the algebraic statement: ∇f and ∇c must be parallel
vectors at x∗ .

The Math
First-order necessary conditions:
1. ∇f (x) = 0 in the free directions (directions tangent to the constraint surface).
2. c(x) = 0 (feasibility — you must actually be standing on the fence).
Condition 1 formalized: any non-zero component of ∇f must be normal to the constraint
surface/manifold (any component tangent to the surface would let you improve by sliding
along it), so
∇f + λ ∇c = 0 for some λ ∈ R (scalar case),
Optimization & Optimal Control — Study Notes 13

called the Lagrange multiplier (or dual variable). In general, for c(x) ∈ Rm :

∂f ∂c
+ λT = 0, λ ∈ Rm .
∂x ∂x

6.2 The Lagrangian and the KKT System

The Concept

Rather than juggling the objective and constraint separately, we fold them into a single scalar
function, the Lagrangian, whose unconstrained stationary points automatically encode both
optimality conditions above.

The Intuition (Visual / Geometric)

The multiplier λ can be thought of as a “price” or “exchange rate”: it measures how much
the optimal value of f would change if we relaxed the constraint c(x) = 0 by a tiny amount.
Building λT c(x) into a combined objective is like saying: “I will let you violate the constraint
slightly, but I will charge/credit you λ per unit violation” — and at the true optimum, this
pricing exactly balances the pull of ∇f against the fence.

The Math

L(x, λ) = f (x) + λT c(x) (the Lagrangian).

The first-order conditions above are exactly the conditions for L to be stationary with respect
to both x and λ:
 T
∂c
∇x L(x, λ) = ∇f + λ = 0, ∇λ L(x, λ) = c(x) = 0.
∂x

These two vector equations together are the KKT conditions for the equality-constrained
problem.

The “Why”

Why does differentiating L with respect to λ reproduce the constraint c(x) = 0? Because
L depends on λ only through the linear term λT c(x), so ∂L/∂λ = c(x) exactly — setting
this to zero is just restating feasibility. This is the elegant payoff of the Lagrangian trick:
a single unconstrained stationarity condition on the augmented function L(x, λ) automati-
cally reproduces both pieces of the constrained optimality condition, letting us reuse all our
unconstrained machinery (including Newton’s method!) on L instead of inventing new tools
for constraints.
Optimization & Optimal Control — Study Notes 14

6.3 Solving the KKT System with Newton’s Method

The Intuition (Visual / Geometric)

We now do to L(x, λ) exactly what we did to f (x) in Section 4: treat ∇x L = 0 as a root-

finding problem and linearize. The only new subtlety is that we’re now solving simultaneously
for the step in x and the step in λ, since they’re coupled.

The Math
Linearizing both stationarity and feasibility conditions around the current (x, λ):
T
∂2L

∂c
∇x L(x + δx, λ + δλ) ≈ ∇x L(x, λ) + δx + δλ = 0,
∂x2 ∂x

∂c
∇λ L(x + δx, λ + δλ) ≈ c(x) + δx = 0.
∂x
Stacked into one linear system, the KKT system:
 2  T 
∂ L ∂c    
 δx = −∇x L(x, λ) .
 ∂x2 ∂x 


∂c
 δλ −c(x)
0
∂x

The “Why”

The zero block in the bottom-right is not an oversight — L is exactly linear in λ (there’s no
λ2 term anywhere), so its second derivative with respect to λ is identically zero. Solving this
single linear system per iteration simultaneously updates both the “where am I” variable x
and the “how much am I paying for the constraint” variable λ, moving both toward mutual
consistency.

6.4 Gauss–Newton: A Cheaper Approximation

The Concept

Computing the full Hessian of the Lagrangian, ∂ 2 L/∂x2 , requires a term describing the
curvature of the constraint itself, which is often expensive. Gauss–Newton simply throws
that term away.

The Math
" T #
∂2L ∂ ∂c
= ∇2 f + λ .
∂x2 ∂x ∂x
| {z }
expensive “constraint curvature” term — dropped

Dropping the second term gives the Gauss–Newton method: approximate ∂ 2 L/∂x2 ≈
∇2 f only.
Optimization & Optimal Control — Study Notes 15

The Intuition (Visual / Geometric)

Geometrically, this means we still respect the curvature of the objective f (the shape of the
“bowl” we’re trying to minimize) but we pretend the constraint fence c(x) = 0 is perfectly
straight (flat) at every step, even if it’s actually curved. This is a slightly worse local model,
so it can take more iterations, but each iteration is cheaper to compute since we skip a costly
derivative.

The “Why”

Gauss–Newton trades iteration quality for iteration cost: slightly slower convergence (more
iterations needed) but each iteration is computationally cheaper. In practice this trade
usually wins in wall-clock time, which is why Gauss–Newton is used so heavily in real systems.
There’s also a robustness bonus: dropping the constraint-curvature term can sometimes
prevent the Hessian approximation from becoming indefinite, which is one reason the lecture’s
example shows full Newton getting stuck at a bad starting point while Gauss–Newton escapes
successfully.

Common Pitfalls
ˆ Assuming Gauss–Newton is strictly worse. It is worse per iteration in convergence rate,
but frequently better in total wall-clock time, and sometimes more robust to bad starting
points.
ˆ Forgetting that even with ∇2 f ≻ 0, you may still need to regularize ∂ 2 L/∂x2 (or its
Gauss–Newton approximation) if it isn’t positive definite in the free directions — the
same damped-Newton idea from Section 4.3 still applies here.

7 Constrained Minimization: Inequality Constraints

The Concept

Now the constraint only forbids x from crossing a boundary, rather than pinning it to an
exact surface: c(x) ≤ 0. This is the general form seen everywhere in practice — actuator
limits, safety margins, obstacle avoidance.

The Math

min f (x) s.t. c(x) ≤ 0.

x

The Intuition (Visual / Geometric)

Now, instead of a fence you must stand exactly on, imagine a region you must stay inside
— the “feasible region” — with c(x) = 0 as its boundary wall. There are exactly two
qualitatively different situations for where the true unconstrained minimum of f sits relative
to this wall:
Optimization & Optimal Control — Study Notes 16

ˆ The wall doesn’t matter. If the unconstrained minimum of f already happens to sit
safely inside the feasible region, the wall is irrelevant — you solve the problem exactly as
if there were no constraint at all.
ˆ The wall matters. If the unconstrained minimum lies outside the feasible region, the
best you can do is get pushed up against the wall, and the solution behaves exactly like the
equality-constrained problem from Section 5 — you’re standing on the boundary c(x) = 0,
tangent condition and all.

The “Why”

This dichotomy is exactly what the KKT conditions below are designed to detect and switch
between automatically, using a single unified set of equations rather than two separate cases
you’d have to check manually.

7.1 The KKT Conditions for Inequality Constraints

The Math
 T
∂c
∇f + λ=0 “stationarity”
∂x
c(x) ≤ 0 “primal feasibility”
λ≥0 “dual feasibility”
λ ⊙ c(x) = λT c(x) = 0 “complementarity”

Intuition: Complementarity as an On/Off Switch

This is the single new idea beyond the equality-constrained case, and it deserves careful
attention. Complementarity (λT c(x) = 0) says: for every constraint, at least one of λ or
c(x) must be exactly zero. Since we also need c(x) ≤ 0 and λ ≥ 0 (both one-sided), this
splits into exactly the two cases from above:
ˆ Constraint “active”: c(x) = 0 (sitting exactly on the wall) ⇒ λ is free to be > 0. This
reduces to precisely the equality-constrained case: the gradient of f must be balanced
by a “push back” from the wall, exactly like Section 5’s tangency condition. The sign
restriction λ ≥ 0 has a clean meaning here too: the wall can only push you back into the
feasible region, never pull you out of it — a one-directional force, like a real physical wall.
ˆ Constraint “inactive”: c(x) < 0 (strictly inside the region, away from the wall) ⇒ λ is
forced to 0. With no force from a wall you’re not touching, this collapses exactly to the
unconstrained case from Section 3: ∇f = 0 alone.
Complementarity is therefore a compact algebraic “switch”: depending on where x∗ ends up,
the system automatically turns the wall’s influence on or off, without you needing to decide
in advance which case you’re in.
Optimization & Optimal Control — Study Notes 17

c(x) = 0
feasible: c(x) ≤ 0 infeasible: c(x) > 0

∇f
λ∇c
x∗ (active, λ > 0)
level curves of f

The “Why”

Why must λ ≥ 0 (and not just λ ̸= 0 as in the equality case)? At an active constraint, ∇f
must point directly into the infeasible region (otherwise you could still improve by moving
slightly further into the feasible region — it wouldn’t really be optimal). Since ∇c also points
into the infeasible region (the direction of constraint violation, by definition of c(x) ≤ 0),
stationarity ∇f = −λ∇c requires ∇f and −∇c to point the same way, i.e., λ > 0. A negative
λ would mean the “wall” is somehow pulling you further into infeasibility, which contradicts
the wall being a barrier at all.

Common Pitfalls
ˆ Sign errors on λ. The correct sign convention depends entirely on how the constraint is
written (c(x) ≤ 0 vs. c(x) ≥ 0 vs. c(x) = 0). Always re-derive the sign from the geometric
picture (which way does ∇c point relative to feasibility?) rather than memorizing λ ≥ 0
blindly.
ˆ Forgetting to check complementarity numerically after solving — a candidate solution
satisfying stationarity and feasibility alone is not sufficient; λT c(x) = 0 must also hold
(approximately, in numerical practice).
ˆ The edge case: it’s possible for the unconstrained minimum to land exactly on the
boundary, giving c(x∗ ) = λ∗ = 0 simultaneously. This is a degenerate but valid solu-
tion of the KKT system, and can cause numerical solvers to behave unpredictably (the
complementarity condition becomes uninformative about which ”regime” you’re in).
ˆ Mixing up which combination of “active/λ > 0” vs. “inactive/λ = 0” applies without
re-deriving it — always sanity-check against the geometric picture: is x∗ pinned against
the wall, or floating freely inside?

7.2 Combining Both Constraint Types

The Concept

Real problems often have both equality and inequality constraints simultaneously (e.g., “land
exactly at this point” and “never exceed this thrust limit”). The good news: nothing new is
required.
Optimization & Optimal Control — Study Notes 18

The “Why”

Simply stack both sets of KKT conditions — the equality block (∂ceq /∂x, feasibility ceq = 0)
and the inequality block (stationarity contribution, cineq ≤ 0, λineq ≥ 0, complementarity) —
into one combined system and solve with the same damped/Gauss–Newton machinery from
Section 5. Each constraint type contributes its own row/column to the same linear system
per iteration; they don’t interact in any more complicated way than that.

8 Algorithms for Constrained Minimization

The Concept

The KKT conditions from Sections 6–7 tell us what a solution must satisfy, but not how
to get there algorithmically. This section covers four different strategies for actually solving
minx f (x) s.t. c(x) ≤ 0 — each one reduces the hard constrained problem to a sequence of
easier problems we already know how to solve.

8.1 Active-Set Methods

The Concept

Guess which inequality constraints are active (touching their boundary, ci (x) = 0) and which
are inactive (irrelevant, ci (x) < 0); then solve the resulting equality-constrained problem
from Section 6 using only the guessed-active constraints; update the guess; repeat.

The Intuition (Visual / Geometric)

Recall from Section 7 that at the true solution, every constraint is in exactly one of two states
— pinned to the wall or floating free — and complementarity is just the algebraic switch that
decides which. Active-set methods make that same decision up front, as a guess, turning a
hard mixed problem back into the pure equality-constrained problem you already know how
to Newton-solve. If the guess turns out wrong (e.g., you assumed a constraint was inactive
but the solution actually wants to push against it, or you assumed active but the resulting
multiplier came out negative), you correct the guess and resolve.

The “Why”

This is attractive precisely because it re-uses all of the equality-constrained KKT machinery
from Section 6 without modification. It is most effective when you have a good heuristic
for which constraints will be active (e.g., from the previous time-step’s solution in a real-
time control loop, where the active set rarely changes drastically frame to frame) — in that
setting, the guess is usually right or nearly right, so few corrective iterations are needed.
Optimization & Optimal Control — Study Notes 19

Common Pitfalls
ˆ The number of possible active sets grows combinatorially with the number of constraints,
so blind guessing (with no heuristic) scales poorly.
ˆ A wrong guess doesn’t just slow convergence — it can send you toward the wrong candidate
stationary point entirely, requiring a genuine restart of the combinatorial search.

8.2 Barrier / Interior-Point Methods

The Concept

Replace the hard inequality constraint with a smooth penalty term baked directly into the
objective — one that explodes to +∞ as x approaches the constraint boundary from inside
the feasible region. This converts a constrained problem into a sequence of unconstrained
problems.

The Intuition (Visual / Geometric)

Picture an electric fence just inside the true wall c(x) = 0: as long as you’re comfortably
inside the feasible region, you feel nothing. But the closer you creep toward the boundary,
the more strongly you’re repelled — and exactly at the boundary, the repulsion is infinite.
This guarantees that an unconstrained minimizer of the new, augmented objective can never
actually cross into infeasibility; it will always settle somewhere strictly inside, hugging the
boundary from the safe side if that’s where the true constrained optimum lives.

−wall
log(−x)

The Math
m
X 1

min f (x) s.t. c(x) ≤ 0 =⇒ min f (x) − log − ci (x) .
x x ρ
i=1

Solve this unconstrained problem (with Newton + regularization + line search from Sections
4–5) for a fixed ρ, then increase ρ and re-solve, tracing a path of solutions that converges to
the true constrained optimum as ρ → ∞.

The “Why”

Why − log(−x)? For x < 0 (feasible), −x > 0 so the log is well-defined and finite; as x → 0−
(approaching the wall), −x → 0+ and − log(−x) → +∞ — exactly the infinite repulsion
we wanted, with a smooth (infinitely differentiable) transition, unlike a hard wall. The 1/ρ
scaling controls how “strong” the fence feels: small ρ means a very cautious barrier that keeps
Optimization & Optimal Control — Study Notes 20

you far from the boundary (easy to solve, but not very accurate); as ρ grows, the barrier’s
influence shrinks everywhere except in a razor-thin region near the boundary, letting the
unconstrained minimizer approach the true constrained solution arbitrarily closely.

Why It’s the “Gold Standard” for Convex Problems

Because the barrier-augmented objective remains smooth everywhere in the feasible region for
any fixed ρ, we can bring the full power of Newton’s method to bear at every stage, retaining
fast (quadratic) local convergence at each fixed-ρ subproblem. For convex problems, this
combination of smoothness and Newton’s speed makes interior-point methods extremely
reliable and fast, which is why they’re considered the gold standard there.

Common Pitfalls
ˆ The barrier is only defined for strictly feasible points (ci (x) < 0); you must start from a
strictly interior point, which itself sometimes requires a preliminary “phase 1” solve just
to find one.
ˆ As ρ → ∞, the barrier-augmented Hessian becomes increasingly ill-conditioned near the
boundary — the algorithm must be paired with careful numerical safeguards.

8.3 Penalty Methods

The Concept

Rather than forbidding constraint violation entirely (as the barrier does), simply allow it —
but add a cost term that penalizes the size of any violation, again reducing the problem to
an unconstrained one.

The Intuition (Visual / Geometric)

Instead of an infinitely strong electric fence exactly at the wall, imagine a soft, stretchy
rubber wall: you’re allowed to push through it, but the further you push, the harder it
pushes back (quadratically harder, in fact). Unlike the barrier method, you’re permitted to be
momentarily infeasible during the search — the penalty just makes infeasibility increasingly
unattractive rather than impossible.

[max(0, x)]2

x
Optimization & Optimal Control — Study Notes 21

The Math
ρ 2
min f (x) s.t. c(x) ≤ 0 =⇒ min f (x) + max(0, c(x)) .
x x 2

The “Why”

The max(0, c(x)) term is exactly zero whenever x is feasible (c(x) ≤ 0), so feasible points
pay no penalty at all — the penalty activates only upon violation, and grows quadratically
(increasingly severely) the further you push through the “rubber wall.” As ρ → ∞, violat-
ing the constraint becomes prohibitively expensive, forcing the unconstrained minimizer to
converge to the true feasible optimum.

Why It Falls Short in Practice

Penalty methods are the easiest of all these methods to implement — just add one smooth-
ish term to f and minimize as usual. But driving ρ → ∞ to force high accuracy causes the
Hessian of the penalized objective to become severely ill-conditioned (its eigenvalues span
an enormous range), which cripples Newton’s method’s numerical reliability. In practice,
plain penalty methods therefore struggle to achieve high-accuracy solutions — you’re stuck
choosing between “somewhat inaccurate” (small ρ) or “numerically unstable” (large ρ).

Common Pitfalls
ˆ Believing you can just crank ρ up indefinitely to get an exact answer. In floating-point
arithmetic, ill-conditioning eventually breaks the linear solves entirely, long before you
reach machine precision.
ˆ Forgetting that [max(0, c(x))]2 is continuously differentiable but its second derivative is
discontinuous exactly at c(x) = 0 — a subtlety that can bite naive Hessian-based codes.

8.4 Augmented Lagrangian Method

The Concept

The method that fixes the penalty method’s ill-conditioning problem: keep the same
quadratic penalty term, but also carry an explicit running estimate of the Lagrange multi-
plier, updating it each iteration to “absorb” most of what the penalty term would otherwise
have to do alone. This means you no longer need ρ → ∞ to get an accurate answer — a
finite ρ suffices.

The Intuition (Visual / Geometric)

In the plain penalty method, the multiplier is implicitly zero and never updated — all the
work of enforcing the constraint falls on an ever-growing ρ, which is what wrecks conditioning.
The augmented Lagrangian instead keeps an explicit, evolving guess λ̃ of the true multiplier
and, after each minimization, “offloads” the current constraint violation into that guess
— nudging λ̃ toward its true KKT value. As λ̃ converges to the correct multiplier, the
residual penalty needed shrinks toward zero, so ρ can stay modest (even fixed) throughout,
Optimization & Optimal Control — Study Notes 22

sidestepping the ill-conditioning that plagued pure penalty methods.

The Math
The augmented Lagrangian (shown here for one active inequality constraint c(x) ≤ 0; the
same idea covers equalities directly with λT c(x)):
ρ 2
Lρ (x, λ̃) = f (x) + λ̃T c(x) + max(0, c(x)) .
2
Setting ∇x Lρ = 0 and comparing to the true stationarity condition reveals the multiplier
update:
∂f ∂c ∂c ∂f  T ∂c
+ λ̃T + ρ c(x)T = + λ̃ + ρ c(x) =0
∂x ∂x ∂x ∂x ∂x
=⇒ λ̃ ← λ̃ + ρ c(x) (for active constraints).
Full iteration loop:
1. Minimize: min Lρ (x, λ̃) (unconstrained; Newton + regularization + line search).
x

2. Update multiplier estimate with clamping to guarantee λ̃ ≥ 0: λ̃ ← max 0, λ̃+ρ c(x) .
3. Grow the penalty weight: ρ ← αρ (typically α ≈ 10).
Repeat until convergence.

The “Why”

The clamp max(0, ·) in step 2 is not optional — it’s what enforces dual feasibility (λ ≥ 0) from
the KKT conditions directly on the running estimate, rather than hoping the unconstrained
minimization discovers it on its own. Because λ̃ is doing most of the work of matching the
true multiplier, this method fixes the ill-conditioning of plain penalty methods, converges
reliably with only a finite ρ (no need to send it to infinity), and — because it never assumed
convexity anywhere in its derivation — works well on genuinely non-convex problems too.

Common Pitfalls

ˆ Forgetting the clamp on λ̃ for inequality constraints — without it, the multiplier estimate
can go negative, corresponding to a “wall” that pulls you inward instead of pushing you
out, which is nonsensical.
ˆ Growing ρ too aggressively (large α) reintroduces the same ill-conditioning issues that
motivated this method in the first place; growing it too slowly wastes iterations.
Optimization & Optimal Control — Study Notes 23

9 Quadratic Programs (QPs)

The Concept

A Quadratic Program is the special case where the objective is exactly quadratic and every
constraint is exactly linear. It is the single most important special case in all of optimization
for control, because it can be solved extremely fast and reliably.

The Math
1 T
min 2 x Qx + q T x, Q ≻ 0,
x

s.t. Ax ≤ b, Cx = d.

The Intuition (Visual / Geometric)

Because Q ≻ 0, the objective is a single, perfectly-shaped bowl (no complicated non-convex

terrain to worry about), and the constraints are flat hyperplanes and half-spaces rather than
curved surfaces. Every one of the messy geometric subtleties from Sections 6–7 — curved
constraint tangency, non-convex Hessians needing regularization, multiple competing local
minima — simply disappears. There’s exactly one bowl and a polyhedral (many-flat-faced)
feasible region cut out of it, and the answer is either at the very bottom of the bowl (if that
point happens to be feasible) or pressed against one flat face or corner of the polyhedron.

The “Why”

Because the problem is convex and finite-dimensional with linear constraints, the full KKT
system (stationarity, feasibility, dual feasibility, complementarity from Section 7) becomes
a system that is solvable to high accuracy in a small, predictable number of iterations —
no linearization/re-linearization loop is even needed, since the objective and constraints are
already exactly linear/quadratic (the “linearized” model is the true model). This predictabil-
ity is exactly why QPs are so useful in control: solvers can run at kilohertz rates (thousands
of solves per second), fast enough to sit inside a real-time feedback control loop — this is the
mathematical engine underneath Model Predictive Control (MPC).

Common Pitfalls
ˆ Assuming any quadratic-looking problem is automatically a “nice” QP — if Q is not posi-
tive definite (or positive semidefinite), the problem may be non-convex or even unbounded
below, and none of the speed/reliability guarantees apply.
ˆ Forgetting that real nonlinear control problems are usually only locally well-approximated
by a QP (this is exactly what Sequential Quadratic Programming / Gauss–Newton-style
methods exploit — solve a QP at each outer iteration as the “easy inner problem,” echoing
the theme from Section 8).
Optimization & Optimal Control — Study Notes 24

10 Regularization and Duality: The Min-Max View

The Concept

A completely different, but equivalent, way of deriving the KKT conditions: rewrite the
constrained problem as an unconstrained min-max (saddle-point) game between x and the
multipliers, where the multiplier player’s job is to act as a referee that punishes any constraint
violation infinitely severely.

The Intuition (Visual / Geometric)

Start with the equality-constrained problem minx f (x) s.t. c(x) = 0. Imagine literally adding
an indicator penalty P0 (c(x)) that costs 0 if c(x) = 0 and costs +∞ for any nonzero c(x) (even
a tiny violation). Minimizing f (x)+P0 (c(x)) unconstrained would then be exactly equivalent
to the original constrained problem — the infinite penalty makes infeasible points never worth
visiting. This indicator function is practically terrible to use directly (it’s discontinuous, not
differentiable, impossible to feed into Newton’s method) — but we can get the exact same
effect by instead introducing an adversarial “inner” player λ that tries to maximize λT c(x):
whenever c(x) ̸= 0, the adversary can always drive λT c(x) → +∞ by choosing λ with the
right sign and enormous magnitude, exactly recreating the infinite penalty — but smoothly,
using only linear algebra.

The Math

(
0 z=0
min f (x) + P0 (c(x)), P0 (z) = ⇐⇒ min max f (x) + λT c(x).
x +∞ z ̸= 0 x λ

Whenever c(x) ̸= 0, the inner maximization over λ “blows up” to +∞, exactly reproducing
P0 ; whenever c(x) = 0, the λT c(x) term vanishes for every λ, so the inner max contributes
nothing extra — reproducing P0 (0) = 0.
For inequality constraints, the same trick uses a one-sided indicator P∞+ (z) = 0 for z ≤ 0,

+∞ for z > 0, reproduced by restricting the adversary to λ ≥ 0:

min f (x) s.t. c(x) ≤ 0 ⇐⇒ min max f (x) + λT c(x) .

x x λ≥0 | {z }
L(x,λ)

Why Restrict λ ≥ 0?

If λ were unrestricted in sign, the adversary could also drive the penalty to +∞ whenever
c(x) < 0 — i.e., even at perfectly feasible points — which would incorrectly forbid the entire
interior of the feasible region. Restricting λ ≥ 0 means the adversary can only exploit a
positive c(x) (an actual violation) to blow up the penalty; at any feasible point (c(x) ≤ 0),
the best the adversary can do is set λ = 0 and contribute nothing. This sign restriction
is exactly the dual feasibility condition from the KKT conditions in Section 7 — it isn’t a
separate rule, it falls straight out of the min-max construction.
Optimization & Optimal Control — Study Notes 25

Interpretation: KKT as a Saddle Point

The KKT conditions from Section 7 are precisely the conditions for (x∗ , λ∗ ) to be a saddle
point of L(x, λ): a minimum with respect to x (curving upward in the x directions, like the
bottom of a valley) but simultaneously a maximum with respect to λ (curving downward
in the λ directions, like the top of a ridge) — the classic saddle/pass shape from mountain
topology, just now in the joint (x, λ) space rather than physical space. Correspondingly,
at an optimum, the full KKT linear system should have dim(x) positive eigenvalues and
dim(λ) negative eigenvalues — a structure called quasi-definite (neither purely positive
nor negative definite, but a controlled, predictable mix of both).

The Math
Regularizing the saddle-point KKT system to make this quasi-definite structure numerically
robust (extending the plain regularization of Section 4.3 to the coupled system of Section
6.3):
H + βI C T
    
δx −∇x L
= , β > 0.
C −βI δλ −c(x)

The “Why”

Just as Section 4.3 added +βI to force the primal Hessian block positive definite, here we
also subtract βI from the (previously zero) dual block. This pushes the top-left block’s
eigenvalues up and the bottom-right block’s eigenvalues down, actively steering the whole
system toward its correct quasi-definite signature (n positive, m negative eigenvalues) rather
than letting it sit at the fragile boundary case of a zero block, which is prone to numerical
singularity.

Common Pitfalls
ˆ Thinking of the min-max reformulation as a computational trick you’d actually use directly
— you would never numerically implement the literal indicator function P0 . Its value here
is entirely conceptual : it reveals why the Lagrangian and its sign conventions on λ are
constructed the way they are, unifying Sections 6 and 7 into one derivation.
ˆ Confusing “quasi-definite” with “indefinite-and-therefore-bad.” A quasi-definite KKT sys-
tem, with the correct signature, is exactly what a well-posed constrained optimum should
look like — it’s a different (but still healthy) structure than the pure positive-definiteness
we wanted in the unconstrained case, not a warning sign by itself.
Optimization & Optimal Control — Study Notes 26

11 Merit Functions: Line Search for Constrained Problems

The Concept

Line search (Section 5) shrank a Newton step by checking whether f (x) actually decreased.
But in a root-finding or constrained-minimization problem, there may be no single “f ” to
check against — instead we need one scalar number that captures overall progress toward
both optimality and feasibility, so backtracking has something concrete to test.

11.1 Merit Functions for Root Finding

The Intuition (Visual / Geometric)

Consider plain root finding: find x∗ with c(x∗ ) = 0. Newton’s method (Section 3.2) can
still overshoot a root just like it overshoots a minimum, but there’s no “objective value”
to check for decrease — a root-finding problem doesn’t naturally come with one. The fix:
manufacture a scalar merit function P (x) that is minimized (at value 0) exactly at the
root, and is otherwise a running scorecard of “how far from solved am I right now?” Then
simply run the exact same Armijo backtracking from Section 5, but checking decrease in
P (x) instead of f (x).

The Math
Standard choices of merit function for c(x) = 0:

P (x) = 21 c(x)T c(x) = 12 ∥c(x)∥22 , or P (x) = ∥c(x)∥1 (any norm works).

Armijo backtracking on the merit function:

α = 1; while P (x + α δx) > P (x) + b α ∇P (x)T δx : α ← θα (0 ≤ θ < 1); end

x ← x + α δx.

The “Why”
1 2
2 ∥c(x)∥2 is the natural choice because it is smooth (differentiable everywhere, so Newton-
friendly) and is manifestly zero exactly at, and only at, the root — any nonzero c(x) con-
tributes a strictly positive penalty. It converts “find where c(x) = 0” into “minimize this
always-non-negative scalar,” turning root finding back into a minimization problem we al-
ready have complete machinery for (Sections 3–5) — this is a direct callback to the very first
idea in these notes, that root finding and minimization are two views of the same coin.
Optimization & Optimal Control — Study Notes 27

11.2 Merit Functions for Constrained Minimization

The Intuition (Visual / Geometric)

For the fully constrained problem, progress means two different things at once: getting closer
to optimal (stationarity) and getting closer to feasible. A good merit function has to blend
both signals into one number, otherwise a line search might accept a step that improves one
at the expense of badly damaging the other.

The Math
For minx f (x) s.t. c(x) ≤ 0, d(x) = 0, with L(x, λ, µ) = f (x) + λT c(x) + µT d(x), options
include:
 
∇x L
P (x, λ, µ) = 21 ∥rKKT (x, λ, µ)∥22 , rKKT = min(0, c(x)) (KKT residual),
d(x)
 
min(0, c(x))
P (x, λ, µ) = f (x) + ρ (ρ > 0 a scalar weight, any norm works),
d(x) 1
P (x, λ, µ) = Lρ (x, λ, µ) (the augmented Lagrangian itself, from Section 8.4).

The “Why”

The KKT-residual merit function directly measures “how far are we from satisfying every
KKT condition simultaneously” — it is zero exactly at a true KKT point and positive
elsewhere, mirroring the root-finding merit function but now over the full stacked system.
The ℓ1 -penalized version instead measures “objective value, plus a surcharge proportional to
how infeasible we currently are” — cheap to compute and interpretable, but requires tuning
ρ large enough to actually discourage infeasibility (echoing the penalty-method trade-offs
from Section 8.3). Perhaps most elegantly, the augmented Lagrangian Lρ from Section 8.4 is
already a perfectly good merit function — if you’re using the augmented Lagrangian method
to solve the problem in the first place, you get a compatible merit function for its own line
search essentially for free, with no extra derivation needed.

Common Pitfalls
ˆ Using f (x) alone as the merit function for a constrained problem — a step that decreases
f (x) while charging further into infeasibility can look like “progress” by that measure
alone, even though it’s moving away from a valid solution.
ˆ Forgetting that excessively large constraint-violation penalties inside a merit function (just
like excessively large ρ in Section 8.3) can themselves cause numerical ill-conditioning —
the merit function needs the same care in scaling as the algorithm it’s monitoring.
ˆ Assuming any merit function will do — it must be compatible with the search direction δx
actually being used (i.e., δx should be a genuine descent direction for P ), or the Armijo
test may never succeed no matter how far you backtrack.
Optimization & Optimal Control — Study Notes 28

12 Putting It All Together: The Unified Algorithm

Start at guess x0 (and λ0 if constrained)

Form Hessian / KKT system

(or Gauss–Newton approximation)

Positive definite no Regularize:

in free directions? H ← H + βI

yes

Solve linear system for δx (, δλ)

Line search (Armijo): shrink α until

sufficient decrease

Update: x ← x + αδx

no Converged?

yes

Done: local optimum x∗

(check sufficient conditions!)

The Unifying Theme

Every method in this document is the same loop: linearize (or otherwise simplify) locally,
solve an easy problem exactly, take a (possibly shrunk) step, repeat. Root finding linearizes
f . Unconstrained minimization linearizes ∇f (fits a quadratic to f ). Equality-constrained
minimization linearizes the Lagrangian’s stationarity and feasibility conditions together. In-
equality constraints add a combinatorial on/off switch (complementarity) to decide, at each
candidate solution, which constraints behave like equalities and which are simply irrelevant.
Active-set, barrier, penalty, and augmented Lagrangian methods (Section 8) are four differ-
ent ways of packaging that same inequality-constrained problem so the core Newton loop can
chew on it; QPs (Section 9) are the special case where no packaging or linearization is even
needed because the problem is already exactly the right shape. Regularization and line search
are two orthogonal safety nets bolted onto this same core loop: one fixes the direction (make
sure it’s downhill), the other fixes the length (make sure you don’t overshoot) — and merit
functions (Section 11) are simply what makes “downhill” a well-defined idea once feasibility,
not just optimality, is part of the picture.
Optimization & Optimal Control — Study Notes 29

Method Core idea Best suited for

Active-Set Guess active constraints, solve equality Good heuristic for active set
problem, correct guess available (e.g. warm-started
real-time control)
Barrier / Smooth − log repulsion near the Convex problems; gold standard
Interior-Point boundary for accuracy
Penalty Quadratic cost for constraint violation Quick, simple prototypes; low
accuracy needs
Augmented Penalty + running multiplier estimate General purpose,
Lagrangian non-convex-friendly, finite ρ
QP solvers Exact solve exploiting convex Real-time control (MPC),
quadratic/linear structure kHz-rate loops