Constrained Optimization

Feasible points and projected steps

Often the minimizer may not be anywhere. A weight vector may have to stay small, or a probability must lie between 0 and 1. In constrained optimization we look for the smallest value of only among the points in a set . A point in is a feasible point. Points outside are infeasible and never count as answers.

A common wish is a solution that is small in some sense. The usual way to ask for it is a norm constraint, for example : the feasible set is the unit ball, a disk in two dimensions.

The simplest method is gradient descent with a projection: take an ordinary step, and if it lands outside , move the result back to the nearest feasible point. For the unit ball this divides a point longer than 1 by its own length. Early steps stay inside the disk. Once a step leaves the disk, the path slides along the circle to the feasible point of lowest , which is not the lowest point of the bowl.

Changing variables

A second approach designs a different problem without constraints, whose solution converts into a solution of the constrained one. The book’s example minimizes over when must have exactly unit length. Every such point is for one angle , so minimize over the angle:

Then return for the best . The new function has one free variable and no constraint.

Every dip in the right curve is a candidate answer. With the default center the curve has two dips, and the deeper one is the true minimum while the other is only local. This is the same trap as in unconstrained gradient descent. Because the variable is an angle, the curve repeats after 2π, so the angles 0 and 2π describe the same point. Move the center to (0, 0): the two dips become equally deep.

The book is frank about the price: this takes creativity, and the transformation has to be designed again for each kind of constraint.

Describing the set and the Lagrangian

The two methods above are tailored to one set. The Karush–Kuhn–Tucker (KKT) approach works for a very general class of sets and uses one new function, the generalized Lagrangian. It needs written with equations and inequalities. Take functions and functions and write

The equations are the equality constraints. The inequalities are the inequality constraints. For example the unit disk is . A ≥ constraint is rewritten in this form by flipping its sign; that step is added here and is not printed in the book.

Each constraint gets its own new variable, called a KKT multiplier: for each equality and for each inequality. The generalized Lagrangian adds every constraint to , weighted by its multiplier:

Read it as the original objective plus a penalty term for each constraint. At a feasible point every equality term is zero, because , and every inequality term is zero or negative, because and . A multiplier is a price: it says how much the objective is charged for each unit of violation. The book notes that this generalizes the older method of Lagrange multipliers, which allows equality constraints only.

With both multipliers at 0, equals , and its lowest point is the target: the constraints are ignored. Raise and the lowest point moves towards the origin, because the term grows with the distance from the origin. Change and the lowest point is pushed sideways, across the line. For one particular pair the gold cross lands on the teal dot. At those values an unconstrained search for the lowest point of solves the constrained problem. Finding such multipliers is the whole difficulty. Section 4 explains the maximizations over them in Equation 4.15.

The minimax form and why it is exact

The book states that, as long as at least one feasible point exists and never takes the value infinity, the problem

has the same optimal value and the same optimal points as the original

Read Equation 4.15 from the inside out. For each fixed , an adversary picks (any real numbers) and (non-negative numbers) to make as large as possible. Then we pick to make that worst case as small as possible. Two facts explain why this works.

The first fact, Equation 4.17, holds whenever all constraints are satisfied. Every equality term is 0 whatever is, and every inequality term is at most 0, so the adversary’s best choice is and the whole thing collapses to . The second fact, Equation 4.18, says that a violated constraint lets the adversary reach infinity.

The demo uses the smallest possible case: with the single inequality . Here is a single number and the true answer is with value 1. A computer cannot take an infinite multiplier, so the demo caps at a finite value .

On the first tab the dashed curve is . The orange curve is the adversary’s best reply: equal to on the feasible side, and climbing with slope equal to the cap beyond . With a cap of 2 or more its lowest point is , the correct answer. Lower the cap below 2 and the lowest point slips into the infeasible region.

The step from the infeasible side to infinity is added here and is not printed in the book. If a constraint is violated, the adversary drives its multiplier to infinity, so the wall it builds becomes vertical as the cap grows. That explanation is added here.

The second tab swaps the order, as Equation 4.20 does for maximization. For each it shows the lowest value of over , which is . That never exceeds the true answer 1 and touches it at . For this convex problem the two orders give the same value.

Maximizing, and the sign of the equality term

To maximize under constraints, the book builds the Lagrangian of . That gives the minimax problem

The same problem can be written with the maximization on the outside:

The inner adversary is a minimizer, and the inequality term flips to a minus, because a maximizer needs the penalty to lower the value.

The book also states that the sign of the equality term does not matter, because each may take either sign. The inequality term has no such freedom, since must be non-negative.

On the first tab the problem is subject to . Slide and the lowest point of the violet curve moves. It reaches the constraint only for one value of : with the plus sign that value is 2, and with the minus sign it is −2, but the point is the same. On the second tab the problem is to maximize subject to . The multiplier now plays the role of , and the highest point of reaches when .

At a feasible point the best choice leaves every constraint term at 0, which gives . At an infeasible point it drives to minus infinity.

Active constraints and zero multipliers

Inequality constraints are the interesting ones. At a solution an inequality is active if it equals 0, so the solution sits on the boundary. If it is inactive it is strictly negative. The book’s observation is that removing an inactive constraint leaves at least a local solution.

With the target inside the disk, the solution is the target itself, the arrows vanish, and the multiplier is exactly 0: an inactive constraint. As soon as the target leaves the disk, the solution jumps onto the boundary and the multiplier switches on. It grows as the target gets further away, because the constraint has to resist a stronger pull. The two arrows always cancel, which is the first KKT condition of the next section.

The book adds a caution. An inactive constraint can still have excluded other solutions. A convex problem with a wide flat region of equally good points may lose part of that region to the constraint. A non-convex problem may lose better local points. What survives is that the point found at convergence is a stationary point whether or not the inactive constraints are included.

Now the key fact about multipliers. Where is negative, the adversary gains nothing from a positive , since that would only lower . So the maximizing choice is . Over all constraints this says that at the solution

This is called complementary slackness. Each product is non-positive, so their sum is 0 only if every product is 0. In words, for each at least one of and must be tight. Either the solution lies on the boundary and the multiplier holds it there, or the constraint has no influence and the multiplier is zero.

The KKT conditions

A short list of properties describes the optimal points. They are the Karush–Kuhn–Tucker conditions (Karush, 1939; Kuhn and Tucker, 1951). For a point with multipliers and :

1. Stationarity. The gradient of the generalized Lagrangian is zero: .
2. Feasibility. All constraints on both and the multipliers hold: , and .
3. Complementary slackness. .

The book stresses that they are necessary conditions, but not always sufficient. Drag the candidate point and set the multipliers, or let the buttons do it.

Drag the point onto the line and into the disk, then press the first button. It chooses the multipliers that make the gradient of as small as possible with . Unless the point is the solution, condition 1 still fails. Only at the solution do all three conditions read met, and there the multipliers have the values you saw in the earlier demos.

The last demo shows why the conditions are not enough. Minimize subject to . The best feasible points are plainly , where equals −1. Now test .

At with the gradient of is zero, the point is feasible, and . All three conditions hold. Yet is the largest value of on the whole feasible interval, not the smallest. The points with also satisfy the conditions and are the true minima.

For problems where the objective and the constraints are convex, the conditions are also sufficient. That result is added here and is not printed in the book. To compare candidates you still have to look at the values of . For more on the KKT approach, the book points to Nocedal and Wright (2006).

What to take away

• The goal is the best feasible point, a point in .
• Projection or a change of variables handles simple sets.
• The generalized Lagrangian covers equalities and inequalities.
• Equation 4.15 has the same optimum as the constrained problem.
• Maximizing uses the Lagrangian of .
• Inactive inequalities get multiplier 0.
• KKT conditions are necessary, not always sufficient.

Check yourself

Questions that mix the whole module. Each one is scored, and the score feeds your mastery of this module.

Source: Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning, MIT Press, 2016, Section 4.4 (pages 93–96), free to read at deeplearningbook.org. Where the book prints equation numbers, the numbers here follow the book. The order of ideas follows the book. The explanations and all demos were written for this page.