15.097 Lecture 11: Convex Optimization Overview

Convex Optimization Overview MIT 15.097 Course Notes Cynthia Rudin Credit: Boyd, Ng and Knowles Thanks: Ashia Wilson We want to solve differentiable convex optimization problems of this form, which we call OPT: minimize n x∈R f (x) subject to gi (x) ≤ 0, i = 1, . . . , m, hi (x) = 0, i = 1 . . . , p, where x ∈ Rn is the optimization variable, f : Rn → R, gi : Rn → R are differ­ entiable convex functions, and hi : Rn → R are affine functions. Recall that a function g : G → R is convex if G is a convex set, and for any x, z ∈ G and θ ∈ [0, 1], we have g(θx+(1−θ)z) ≤ θg(x)+(1−θ)g(z). A function g is concave if −g is convex. An affine function has the form h(x) = aT x + b for some a ∈ Rn , b ∈ R. (Affine functions are both convex and concave.) We could rewrite the OPT with the constraints in the objective: min ΘP (x) x ΘP (x) :=f (x) + ∞ where m m 1[gi(x)>0] + ∞ i=1 p m 1[hi(x)=0]. (1) i=1 But this is hard to optimize because it is non-differentiable and not even contin­ uous. Why don’t we replace ∞ × 1[u≥0] with something nicer? A line αu seems like a dumb choice... 1 but for α ≥ 0 the penalty is in the right direction (we are penalized for con­ straints being dissatisfied, and αu is a lower bound on 1[gi (x)>0] ). Similarly, βu is a lower bound for ∞ × 1[u6=0] no matter what the sign of β is. For each constraint i, replacing ∞ × 1[u≥0] by αu, where α ≥ 0 in the objective, and similarly replacing the ∞ × 1[u6=0] term by βu, gives the Lagrangian L(x, α, β) = f (x) + m m i=1 αi gi (x) + p m βi hi (x). (2) i=1 We refer to x ∈ Rn as the primal variables of the Lagrangian. The second ar­ gument of the Lagrangian is a vector α ∈ Rm . The third is a vector β ∈ Rp . Elements of α and β are collectively known as the dual variables of the La­ grangian, or Lagrange multipliers. If we take the maximum of L with respect to α and β, where αi ≥ 0, we recover OPT. Let’s show this. For a particular x, let’s say the constraints are satisfied. So gi (x) ≤ 0, and to make the term αi gi (x) as high as it can be, we set αi = 0 ∀i. Also, since hi (x) = 0 ∀i, the βi ’s can be anything and it won’t change L. To summarize, if the constraints are satisfied, the value of maxα,β L is just f (x), which is the same as the value of ΘP . 2 If any constraint is not satisfied, then we can make L(x, α, β) infinite by fiddling with αi or βi , and then again the value of maxα,β L is the same as the value of ΘP . How? So we have formally: ΘP (x) = max L(x, α, β). α,β;αi ≥0,∀i Remember that we want to minimize ΘP (x). This problem is the primal problem. Specifically, the primal problem is: � � min max L(x, α, β) = min ΘP (x). x x α,β:αi ≥0,∀i (3) In the equation above, the function ΘP : Rn → R is called the primal objective. We say that a point x ∈ Rn is primal feasible if gi (x) ≤ 0, i = 1, . . . , m and hi (x) = 0, i = 1, . . . , p. The vector x∗ ∈ Rn denotes the solution of (3), and p∗ = ΘP (x∗ ) denotes the optimal value of the primal objective. It turns out that ΘP (x) is a convex function of x. Why is that? First, f (x) is convex. Each of the gi (x)’s are convex functions in x, and since the αi ’s are constrained to be nonnegative, then αi gi (x) is convex in x for each i. Similarly, each βi hi (x) is convex in x (regardless of the sign of βi ) since hi (x) is linear. Since the sum of convex functions is always convex, L is convex for each α and β. Finally, the maximum of a collection of convex functions is again a convex function, so we can conclude that ΘP (x) = maxα,β L(α, β, x) is a convex function of x. By switching the order of the minimization and maximization above, we obtain an entirely different optimization problem. 3 The dual problem is: max α,β:αi ≥0,∀i min L(x, α, β) = x max α,β:αi ≥0,∀i ΘD (α, β). (4) Function ΘD : Rm × Rp → R is called the dual objective. We say that (α, β) are dual feasible if αi ≥ 0, i = 1 . . . , m. Denote (α∗ , β ∗ ) ∈ Rm × Rp as the solution of (4), and d∗ = ΘD (α∗ , β ∗ ) denote the optimal value of the dual objective. The dual objective ΘD (α, β), is a concave function of α and β. The dual objec­ tive is: p m m m ΘD (α, β) = min L(x, α, β) = min f (x) + αi gi (x) + βi hi (x) . x x i=1 i=1 For any fixed value of x, the quantity inside the brackets is an affine function of α and β, and hence, concave. The f (x) is just a constant as far as α and β are concerned. Since the minimum of a collection of concave functions is also concave, we can conclude that ΘD (α, β) is a concave function of α and β. Interpreting the Dual Problem We make the following observation: Lemma 1. If (α, β) are dual feasible, then ΘD (α, β) ≤ p∗ Proof. Because of the lower bounds we made, namely αi gi (x) ≤ ∞ × 1[gi (x)≥0] βi hi (x) ≤ ∞ × 1[hi (x)6=0] we have, when α and β are dual feasible, L(x, α, β) ≤ ΘP (x) for all x. Taking the minx of both sides: 4 min L(x, α, β) ≤ min ΘP (x) . "x "x p∗ ΘD (α, β) • The lemma shows that given any dual feasible (α, β), the dual objective ΘD (α, β) provides a lower bound on the optimal value p∗ of the primal problem. Since the dual problem is maxα,β ΘD (α, β), the dual problem can be seen as a search for the tightest possible lower bound on p∗ . This gives rise to a property of any primal and dual optimization problem pairs known as weak duality: Lemma 2. For any pair of primal and dual problems, d∗ ≤ p∗ . Rewritten, max min L(x, α, β) ≤ min max L(x, α, β). α,β:αi ≥0,∀i x x α,β:αi ≥0,∀i Intuitively, this makes sense: on the left, whatever the α, β player does, the x player gets to react to bring the value down. On the right, whatever the x player does, the α, β player reacts to bring the value up. And of course the player who plays last has the advantage. Prove it? (Hint: place your hand over the leftmost max to see it.) α,β For some primal/dual optimization problems, an even stronger result holds, known as strong duality. Lemma 3 (Strong Duality). For any pair of primal and dual problems which satisfy certain technical conditions called constraint qualifications, then d∗ = p∗ . A number of different constraint qualifications exist, of which the most com­ monly invoked is Slater’s condition: a primal/dual problem pair satisfy Slater’s condition if there exists some feasible primal solution x for which all inequality constraints are strictly satisfied (i.e. gi (x) < 0, i = 1 . . . , m). In practice, nearly all convex problems satisfy some type of constraint qualification, and hence the primal and dual problem have the same optimal value. 5 KKT Conditions For an unconstrained convex optimization problem, we know we are at the global minimum if the gradient is zero. The KKT conditions are the equivalent condi­ tions for the global minimum of a constrained convex optimization problem. If strong duality holds and (x∗ , α∗ , β ∗ ) is optimal, then x∗ minimizes L(x, α∗ , β ∗ ) giving us the first KKT condition, Lagrangian stationarity: m m αi∗ �x gi (x)|x∗ + βi∗ �x hi (x)|x∗ = 0 �x L(x, α∗ , β ∗ )|x∗ = �x f (x)|x∗ + i i We can interpret this condition by saying that the gradient of the objective function and constraint function must be parallel (and opposite). This concept is illustrated for a simple 2D optimization problem with one inequality constraint below. The curves are contours of f , and the line is the constraint boundary. At x∗ , the gradient of f and gradient of the constraint must be parallel and opposing so that we couldn’t move along the constraint boundary in order to get an improved objective value. 6 One interesting consequence of strong duality is next: Lemma 3 (Complementary Slackness). If strong duality holds, then αi∗ gi (x∗ ) = 0 for each i = 1 . . . , m. Proof. Suppose that strong duality holds. p∗ = d∗ = ΘD (α∗ , β ∗ ) = min L(x, α∗ , β ∗ ) x ≤ L(x∗ , α∗ , β ∗ ) ≤ max L(x∗ , α, β) = α,β;αi ≥0,∀i ΘP (x∗ ) = f (x∗ ) = p∗ . The second last inequality is just from (1). This means that all the inequalities are actually equalities. In particular, L(x∗ , α∗ , β ∗ ) = f (x∗ ) + m m αi∗ gi (x∗ ) + i i αi∗ gi (x∗ ) βi∗ hi (x∗ ) = f (x∗ ). i So, m m p m + p m βi∗ hi (x∗ ) = 0. i • Since x∗ is primal feasible, each hi (x∗ ) = 0, so the second terms are all 0. • Since αi∗ ’s are dual feasible, αi∗ ≥ 0, and since x∗ is primal feasible, gi (x∗ ) ≤ 0. So each αi∗ gi (x∗ ) ≤ 0, which means they are all 0. αi∗ gi (x∗ ) = 0 ∀i = 1, . . . , m. We can rewrite complementary slackness this way: αi∗ > 0 =⇒ gi (x∗ ) = 0 (active constraints) gi (x∗ ) < 0 =⇒ αi∗ = 0. In the case of support vector machines (SVMs), active constraints are known as support vectors. 7 We can now characterize the optimal conditions for a primal dual optimization pair: Theorem 1 Suppose that x∗ ∈ Rn , α∗ ∈ Rm , and β ∗ ∈ Rp satisfy the following conditions: • (Primal feasibility) gi (x∗ ) ≤ 0, i = 1, ..., m and hi (x∗ ) = 0, i = 1, ..., p. • (Dual feasibility) αi∗ ≥ 0, i = 1, . . . , m. • (Complementary Slackness) αi∗ gi (x∗ ) = 0, i = 1, . . . , m. • (Lagrangian stationary) ∇x L(x∗ , α∗ , β ∗ ) = 0. Then x∗ is primal optimal and (α∗ , β ∗ ) are dual optimal. Furthermore, if strong duality holds, then any primal optimal x∗ and dual optimal (α∗ , β ∗ ) must satisfy all these conditions. These conditions are known as the Karush-Kuhn-Tucker (KKT) conditions.1 1 Incidentally, the KKT theorem has an interesting history. The result was originally derived by Karush in his 1939 master’s thesis but did not catch any attention until it was rediscovered in 1950 by two mathematicians Kuhn and Tucker. A variant of essentially the same result was also derived by John in 1948. 8