17  Constrained Optimization

Real problems come with rules. Probabilities must sum to one, variances cannot be negative, a portfolio has a budget, a regularization path has a norm ceiling.

Chapter 16 assumed you could step anywhere. This chapter is about what changes when you cannot — and the answer is elegant: at a constrained optimum, the gradient does not vanish, it becomes parallel to the constraint.

17.1 Constrained problems

The standard form:

\[ \begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{subject to} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1,\dots,m \\ & h_j(\mathbf{x}) = 0, \quad j = 1,\dots,p \end{aligned} \tag{17.1}\]

with inequality constraints \(g_i\) and equality constraints \(h_j\). Any constraint can be written this way: \(x \geq 1\) becomes \(1 - x \leq 0\), and \(x + y = 2\) becomes \(x + y - 2 = 0\).

A point satisfying every constraint is feasible. The whole difficulty is that the unconstrained minimum is usually infeasible, so the answer sits somewhere on the boundary of what is allowed.

17.2 Feasible sets

The feasible set is the intersection of everything the constraints permit. Since an intersection of convex sets is convex (Section 15.2), a set carved out by linear constraints is a convex polygon — or in higher dimensions a polytope.

poly <- rbind(
  c(0, 0), c(3, 0), c(1, 2), c(0, 2), c(0, 0)
)
draw_plane(
  curves = list(feasible = poly),
  curve_color = amds_colors[1],
  points = rbind(c(0, 0), c(3, 0), c(1, 2), c(0, 2)),
  notes = list(feasible = c(0.75, 0.7)),
  xlab = "x", ylab = "y"
)
Figure 17.1: The feasible set for \(x \geq 0\), \(y \geq 0\), \(x + y \leq 3\), \(y \leq 2\). Each constraint cuts away a halfplane, and what survives is their intersection — convex, because intersection always is.

A useful fact follows immediately: if the objective is linear, its optimum over a polytope is always attained at a vertex. That is the entire basis of the simplex method for linear programming — instead of searching a continuous region, walk from corner to corner.

17.3 Equality constraints and Lagrange multipliers

Minimize \(f\) subject to \(h(\mathbf{x}) = 0\). The constraint confines you to a curve or surface, and you want the lowest point on it.

The key observation is geometric. Walking along the constraint, you can keep descending as long as \(f\) changes — so at the optimum, moving along the constraint must leave \(f\) unchanged to first order. That means \(\nabla f\) has no component along the constraint, so it is perpendicular to it. But \(\nabla h\) is also perpendicular to the constraint (Section 12.4). Two vectors perpendicular to the same curve must be parallel:

\[ \nabla f(\mathbf{x}^*) = \lambda\,\nabla h(\mathbf{x}^*) \tag{17.2}\]

The scalar \(\lambda\) is the Lagrange multiplier. Together with \(h(\mathbf{x}) = 0\) this gives as many equations as unknowns.

The bookkeeping device is the Lagrangian:

\[ \mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda\,h(\mathbf{x}) \]

Setting all its partial derivatives to zero reproduces Equation 17.2 and the constraint — so a constrained problem in \(\mathbf{x}\) becomes an unconstrained one in \((\mathbf{x}, \lambda)\).

Worked example. Minimize \(x^2 + y^2\) subject to \(x + y = 2\).

\[ \nabla f = \begin{bmatrix}2x\\2y\end{bmatrix}, \qquad \nabla h = \begin{bmatrix}1\\1\end{bmatrix} \]

Equation 17.2 gives \(2x = \lambda\) and \(2y = \lambda\), so \(x = y\). The constraint then forces \(x = y = 1\), with \(\lambda = 2\) and \(f = 2\).

f_bowl <- function(x, y) x^2 + y^2
sol <- c(1, 1)
grad_f <- 2 * sol # gradient of x^2 + y^2
grad_h <- c(1, 1) # gradient of x + y - 2
# lambda solves grad_f = lambda * grad_h, so the ratio
# must be the same in every coordinate
c(
  ratios = grad_f / grad_h,
  feasible = sum(sol) - 2,
  f_at_solution = f_bowl(sol[1], sol[2])
)
      ratios1       ratios2      feasible f_at_solution 
            2             2             0             2 
xs <- c(-0.5, 2.5)
draw_contour(
  f_bowl, c(-0.6, 2.6), c(-0.6, 2.6),
  curves = list(`x + y = 2` = cbind(xs, 2 - xs)),
  vectors = list(`grad f` = c(0.6, 0.6)),
  origin = list(sol),
  points = rbind(sol),
  xlab = "x", ylab = "y"
)
Figure 17.2: The constraint line \(x+y=2\) against the level sets of \(x^2+y^2\). The optimum is where the line is tangent to a contour — any contour it crosses, it can follow to a lower one. The gradient arrow points straight out of the constraint.

Tangency is the whole picture. Where the constraint line crosses a contour it enters a region of lower \(f\), so it cannot be optimal. Only where it touches without crossing has the descent run out.

NoteIn machine learning

\(\lambda\) is not just bookkeeping — it is a sensitivity. It measures how much the optimal value would change if the constraint were relaxed by one unit, which is why economists call it a shadow price. In a regularized model it is exactly the regularization strength, and Section 17.5 explains why the constrained and penalized forms of ridge and Lasso are two views of one problem.

17.4 Inequality constraints and the KKT conditions

Inequalities add a wrinkle: a constraint may or may not be doing anything. A constraint is active at the optimum if it holds with equality, and inactive if there is slack.

  • If inactive, the optimum is the unconstrained one and the constraint is irrelevant.
  • If active, it behaves exactly like an equality constraint.

You do not know which in advance, and the Karush–Kuhn–Tucker conditions handle both at once. For \(\min f\) subject to \(g(\mathbf{x}) \leq 0\):

\[ \begin{aligned} \nabla f + \lambda\nabla g &= \mathbf{0} &&\text{stationarity} \\ g(\mathbf{x}) &\leq 0 &&\text{primal feasibility} \\ \lambda &\geq 0 &&\text{dual feasibility} \\ \lambda\, g(\mathbf{x}) &= 0 &&\text{complementary slackness} \end{aligned} \tag{17.3}\]

The last one is the clever part. Complementary slackness says at least one of \(\lambda\) and \(g\) must be zero: either the constraint is tight (\(g = 0\)) or its multiplier is (\(\lambda = 0\)). Inactive constraints price themselves out automatically.

The sign condition \(\lambda \geq 0\) also matters, and unlike the equality case it is not optional. It encodes direction: \(\nabla f\) must point into the forbidden region, so that the constraint is genuinely holding you back rather than pushing you somewhere you wanted to go anyway.

Worked example. Minimize \(x^2 + y^2\) subject to \(x + y \geq 2\), i.e. \(g = 2 - x - y \leq 0\).

The unconstrained minimum \((0,0)\) has \(g = 2 > 0\): infeasible. So the constraint is active, the problem reduces to the equality case, and the answer is \((1,1)\) with \(\lambda = 2 > 0\).

Change the constraint to \(x + y \geq -2\) and \((0,0)\) becomes feasible with slack. Now the constraint is inactive and \(\lambda = 0\).

kkt_check <- function(a) {
  # min x^2+y^2 s.t. x+y >= a
  if (a <= 0) {
    list(x = c(0, 0), lambda = 0, active = FALSE)
  } else {
    list(x = c(a / 2, a / 2), lambda = a, active = TRUE)
  }
}
str(kkt_check(2))
List of 3
 $ x     : num [1:2] 1 1
 $ lambda: num 2
 $ active: logi TRUE
str(kkt_check(-2))
List of 3
 $ x     : num [1:2] 0 0
 $ lambda: num 0
 $ active: logi FALSE

In both cases \(\lambda \cdot g = 0\), as Equation 17.3 requires.

17.5 Duality

Every constrained problem has a shadow. Starting from the Lagrangian

\[ \mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) + \lambda g(\mathbf{x}) \]

define the dual function by minimizing out \(\mathbf{x}\):

\[ q(\lambda) = \min_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \lambda) \]

For any \(\lambda \geq 0\), \(q(\lambda)\) is a lower bound on the constrained optimum — a minimum over a larger set can only be smaller. The dual problem asks for the best such bound, \(\max_{\lambda \geq 0} q(\lambda)\).

Weak duality always holds: dual optimum \(\leq\) primal optimum. The gap between them is the duality gap, and for a convex problem satisfying mild conditions it is zero — strong duality. Solving either problem solves both.

Worked example. Minimize \(x^2\) subject to \(x \geq 1\). Here \(\mathcal{L} = x^2 - \lambda(x-1)\), minimized at \(x = \lambda/2\), giving

\[ q(\lambda) = -\frac{\lambda^2}{4} + \lambda \]

q <- function(lambda) -lambda^2 / 4 + lambda
lams <- c(0, 1, 2, 3, 4)
rbind(lambda = lams, dual = q(lams))
       [,1] [,2] [,3] [,4] [,5]
lambda    0 1.00    2 3.00    4
dual      0 0.75    1 0.75    0

The dual peaks at \(\lambda = 2\) with value \(1\) — exactly the primal optimum \(x = 1\), \(f = 1\). No gap.

NoteIn machine learning

Duality is why support vector machines are usually solved in their dual form: the dual involves only inner products between observations, which is what lets you replace them with a kernel and fit a non-linear boundary without ever computing coordinates in the high-dimensional space.

It is also the link between the two ways of writing regularization. Minimizing \(\|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|^2\) subject to \(\|\boldsymbol{\beta}\|_1 \leq t\) and minimizing \(\|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|^2 + \lambda\|\boldsymbol{\beta}\|_1\) are the same problem, with \(\lambda\) the multiplier for the budget \(t\). Every \(t\) corresponds to some \(\lambda\) and back (Section 6.11).

17.6 Projected gradient descent

The simplest algorithm for a constrained problem. Take an ordinary gradient step; if it lands outside the feasible set, project back to the nearest feasible point:

\[ \mathbf{x}_{k+1} = \Pi_C\bigl(\mathbf{x}_k - \eta\nabla f(\mathbf{x}_k)\bigr) \tag{17.4}\]

where \(\Pi_C\) is projection onto \(C\) — the closest point, in the sense of Section 7.13.

This is practical only when projection is cheap, which for common sets it is:

Feasible set Projection
box \(\ell \leq x \leq u\) clip each coordinate
non-negative orthant pmax(x, 0)
\(L_2\) ball \(\|\mathbf{x}\| \leq r\) rescale if outside
a subspace Equation 7.4 
project_ball <- function(x, r = 1) {
  nx <- sqrt(sum(x^2))
  if (nx > r) x * r / nx else x
}
target <- c(3, 1)
x <- c(-0.9, 0.2)
path <- matrix(x, nrow = 1)
for (k in 1:12) {
  x <- project_ball(x - 0.1 * (2 * (x - target)))
  path <- rbind(path, x)
}
round(head(path, 5), 4)
     [,1]   [,2]
  -0.9000 0.2000
x -0.1200 0.3600
x  0.5040 0.4880
x  0.8618 0.5072
x  0.9051 0.4252
th <- seq(0, 2 * pi, length.out = 300)
draw_plane(
  curves = list(
    ball = cbind(cos(th), sin(th)),
    path = path
  ),
  curve_color = c(amds_gray, amds_colors[1]),
  points = path,
  xlab = "x", ylab = "y"
)
Figure 17.3: Minimizing distance to \((3,1)\) subject to \(\|\mathbf{x}\| \leq 1\). The iterates move freely until a step would leave the ball, then get projected back onto it and slide along the boundary to the closest feasible point.

The path converges to \((3,1)/\|(3,1)\| \approx (0.949, 0.316)\) — the point of the ball closest to the unconstrained target, which is where the gradient becomes parallel to the boundary’s normal, exactly as Equation 17.2 predicts.

17.7 Penalty and barrier methods

The other approach: stop constraining, and make violations expensive instead. Then any unconstrained method applies.

Penalty methods add a cost for violating, and let violation remain possible:

\[ \min_{\mathbf{x}} \; f(\mathbf{x}) + \mu\max(0, g(\mathbf{x}))^2 \]

As \(\mu \to \infty\) the solution approaches the constrained one from outside the feasible set.

# min x^2 s.t. x >= 1  ->  penalized solution mu/(1+mu)
mus <- c(1, 10, 100, 1000)
rbind(mu = mus, x = round(mus / (1 + mus), 6))
   [,1]      [,2]       [,3]        [,4]
mu  1.0 10.000000 100.000000 1000.000000
x   0.5  0.909091   0.990099    0.999001

Barrier methods instead make the boundary infinitely expensive, so iterates can never leave:

\[ \min_{\mathbf{x}} \; f(\mathbf{x}) - t\log(-g(\mathbf{x})) \]

As \(t \to 0\) the solution approaches the constrained one from inside.

# min x^2 - t*log(x-1)  ->  x = (1 + sqrt(1 + 2t))/2
ts <- c(1, 0.1, 0.01, 0.001)
rbind(t = ts, x = round((1 + sqrt(1 + 2 * ts)) / 2, 6))
      [,1]     [,2]     [,3]   [,4]
t 1.000000 0.100000 0.010000 0.0010
x 1.366025 1.047723 1.004975 1.0005
mgrid <- 10^seq(-1, 3, length.out = 40)
tgrid <- 10^seq(0, -3, length.out = 40)
draw_line(
  x = seq_along(mgrid),
  y = list(
    penalty = mgrid / (1 + mgrid),
    barrier = (1 + sqrt(1 + 2 * tgrid)) / 2
  ),
  points = FALSE,
  xlab = "tightening ->",
  ylab = "x"
)
Figure 17.4: Both families approach the constrained optimum \(x = 1\), from opposite sides: penalty methods from below, where the constraint is violated, and barrier methods from above, where it is strictly satisfied.
WarningWatch out

Both families become ill-conditioned as they tighten. A large \(\mu\) makes the penalized objective enormously steeper across the constraint than along it, which is precisely the narrow valley of Figure 12.2 — so the very limit you want is the one your optimizer struggles with.

The standard remedy is to solve a sequence of moderately tightened problems, each started from the previous solution, rather than jumping straight to an extreme value. Interior-point methods do exactly this and are what modern solvers use.

17.8 Constraints you meet in machine learning

Constraint Where Handled by
\(\|\boldsymbol{\beta}\|_1 \leq t\) Lasso dual form: an \(L_1\) penalty
\(\|\boldsymbol{\beta}\|_2 \leq t\) ridge dual form: an \(L_2\) penalty
\(\sum_k p_k = 1\), \(p_k \geq 0\) probabilities softmax parameterization
\(\mathbf{W} \geq 0\) non-negative matrix factorization projection
margin \(\geq 1\) support vector machines dual + KKT
\(\|\delta\|_\infty \leq \epsilon\) adversarial examples projected gradient

Two patterns recur. Sometimes you reparameterize so the constraint cannot be violated — a softmax always produces a valid probability vector, so no constraint is needed. Otherwise you dualize and turn the constraint into a penalty, which is what makes ridge and Lasso ordinary unconstrained problems.

Reparameterizing is preferable when available, because it removes the constraint rather than managing it.

17.9 Summary

Idea Statement
Feasible set intersection of constraints; convex if each is
Lagrange condition \(\nabla f = \lambda\nabla h\) at the optimum
Lagrangian \(\mathcal{L} = f - \lambda h\); unconstrained in \((\mathbf{x},\lambda)\)
KKT stationarity, feasibility, \(\lambda \geq 0\), \(\lambda g = 0\)
Complementary slackness inactive constraints get \(\lambda = 0\)
Duality dual is a lower bound; gap is zero when convex
Projected gradient step, then project back
Penalty / barrier approach from outside / from inside

17.10 Exercises

1. Maximize \(xy\) subject to \(x + y = 10\) using Lagrange multipliers.

\(\nabla f = (y, x)\) and \(\nabla h = (1,1)\), so \(y = \lambda\) and \(x = \lambda\), giving \(x = y\). The constraint forces \(x = y = 5\), with \(\lambda = 5\) and \(f = 25\).

xy <- c(5, 5)
# grad(xy) = (y, x) must be parallel to grad(x+y) = (1,1)
c(
  ratios = c(xy[2], xy[1]) / c(1, 1),
  feasible = sum(xy) - 10,
  product = prod(xy)
)
 ratios1  ratios2 feasible  product 
       5        5        0       25 
# no nearby feasible point does better
alt <- seq(3, 7, by = 1)
rbind(x = alt, product = alt * (10 - alt))
        [,1] [,2] [,3] [,4] [,5]
x          3    4    5    6    7
product   21   24   25   24   21

This is the isoperimetric result in miniature: for a fixed perimeter the rectangle of largest area is a square. The symmetry of the answer is forced by the symmetry of the problem.

2. For \(\min x^2 + y^2\) subject to \(x + y \geq 5\), is the constraint active? Find the solution and \(\lambda\).

The unconstrained minimum \((0,0)\) gives \(x + y = 0 < 5\), which is infeasible. So the constraint is active and behaves as an equality.

str(kkt_check(5))
List of 3
 $ x     : num [1:2] 2.5 2.5
 $ lambda: num 5
 $ active: logi TRUE

The solution is \((2.5, 2.5)\) with \(\lambda = 5 > 0\), and \(\lambda g = 0\) because \(g = 0\).

3. Project the point \((4, 3)\) onto the unit ball, and onto the box \([-1,1] \times [-1,1]\).

p <- c(4, 3)
rbind(
  ball = round(project_ball(p), 4),
  box = pmax(pmin(p, 1), -1)
)
     [,1] [,2]
ball  0.8  0.6
box   1.0  1.0

The ball projection rescales to length 1, giving \((0.8, 0.6)\) — the direction is kept. The box projection clips each coordinate independently to \((1, 1)\), which changes the direction. Different feasible sets give genuinely different nearest points, which is why the shape of the constraint matters as much as its tightness.

4. Verify weak duality for \(\min x^2\) subject to \(x \geq 1\) by evaluating the dual at several \(\lambda\).

lam <- seq(0, 4, by = 0.5)
rbind(lambda = lam, dual = q(lam), primal = 1)
       [,1]   [,2] [,3]   [,4] [,5]   [,6] [,7]   [,8] [,9]
lambda    0 0.5000 1.00 1.5000    2 2.5000 3.00 3.5000    4
dual      0 0.4375 0.75 0.9375    1 0.9375 0.75 0.4375    0
primal    1 1.0000 1.00 1.0000    1 1.0000 1.00 1.0000    1

Every dual value is at or below the primal optimum of 1, which is weak duality. The bound is achieved at \(\lambda = 2\), so the gap is zero and strong duality holds — as it must for a convex problem with a strictly feasible point.

5. Show that the penalty solution \(\mu/(1+\mu)\) never reaches 1, and find the \(\mu\) needed to get within \(10^{-4}\).

\(\mu/(1+\mu) < 1\) for every finite \(\mu\) — the penalized solution always sits slightly outside the feasible region. Solving \(1 - \mu/(1+\mu) = 1/(1+\mu) < 10^{-4}\) gives \(\mu > 9999\).

mu_needed <- 1 / 1e-4 - 1
c(
  mu = mu_needed,
  x = mu_needed / (1 + mu_needed),
  violation = 1 - mu_needed / (1 + mu_needed)
)
       mu         x violation 
9999.0000    0.9999    0.0001

This is the characteristic weakness of penalty methods: the answer is always slightly infeasible, and buying another digit costs a tenfold increase in \(\mu\) — with the conditioning penalty that brings.

6. Run projected gradient descent on the same problem from a starting point outside the ball. Where does the first step land?

x <- c(-2.5, 2)
first <- project_ball(x - 0.1 * (2 * (x - target)))
c(
  start_norm = round(sqrt(sum(x^2)), 4),
  after = round(first, 4),
  after_norm = round(sqrt(sum(first^2)), 4)
)
start_norm     after1     after2 after_norm 
    3.2016    -0.6139     0.7894     1.0000

The very first projection puts the iterate on the boundary, and it stays feasible from then on. Projected gradient descent needs no feasible starting point — the projection supplies one — which is a practical advantage over methods like barriers that require an interior point to begin.