� � � � 2.098/6.255/15.093 - Recitation 10 Michael Frankovich and Shubham Gupta December 4, 2009 1 Karush Kuhn Tucker Necessary Conditions P: min f(x) s.t. gj(x) ≤ 0, j = 1, . . . , p hi(x) = 0, i = 1, . . . , m Theorem. (KKT Necessary Conditions for Optimality) If ˆx is local minimum of P and the following Constraint Qualification Condition (CQC) holds: • The vectors ∇gj(ˆx), j ∈ I(ˆx) and ∇hi(ˆx), i = 1, . . . , m, are linearly indepen-dent, where I(ˆx) = {j : gj(ˆx) = 0} is the set of indices corresponding to active constraints at ˆx. Then, there exist vectors (u, v) s.t.: p m 1. ∇f(ˆx) + uj∇gj(ˆx) + vi∇hi(ˆx) = 0 j=1 i=1 2. uj ≥ 0, j = 1, . . . , p 3. ujgj(ˆx) = 0, j = 1, . . . , p (or equivalently gj(ˆx) < 0 ⇒ uj = 0, j = 1, . . . , p) Theorem. (KKT + Slater) If ˆx is local minimum of P and the following Slater Condition holds: • There exists some feasible solution ¯x such that gj(¯x) < 0, ∀j ∈ I(ˆx), where I(ˆx) = {j : gj(ˆx) = 0} is the set of indices corresponding to active constraints at xˆ. Then, there exist vectors (u, v) s.t.: p m 1. ∇f(ˆx) + uj∇gj(ˆx) + vi∇hi(ˆx) = 0 j=1 i=1 2. uj ≥ 0, j = 1, . . . , p 13. ujgj(ˆx) = 0, j = 1, . . . , p (or equivalently gj(ˆx) < 0 ⇒ uj = 0, j = 1, . . . , p) Example. Solve min x21 + x22 + x23 s.t. x1 + x2 + x3 ≤ −18 Solution. For some x to be a local minimum, condition (1) requires that ∃u s.t. 2xi + u = 0, i = 1, 2, 3. Now, the constraint can either be active or inactive: • If it is inactive, then u < 0 by condition (3). This would imply x1 = x2 = x3 = 0, but x = (0, 0, 0)⊤ is infeasible, so this cannot be true of a local minimum. • If it is active, then x1 + x2 + x3 = −18 and 2xi + u = 0, i = 1, 2, 3. This is a system of four linear equations in four unknowns. We solve and obtain u = 12, x = (−6, −6, −6)⊤ . Since u = 12 ≥ 0, th ere exists a u as desired. To check the regularity requirement, we simply confirm that ∇x = (1, 1, 1)⊤ � 0. Also, we could = have checked that the Slater condition is satisfied (eg use x¯ = (−10, −10, −10)⊤). Hence (−6, −6, −6)⊤ is the only candidate for a local minimum. Now, the question is: is it a local minimum? (Note that since this is the unique candidate, this is the same as asking if the function has a local minimum over the set.) Observe that the objective function is convex. Why? Because it is a positive combina-tion of convex functions. Now, is the feasible set convex? Answer: yes, since it is of the form {x ∈ Rn : f(x) ≤ 0}, where f is a convex function. So we may apply a stronger version of the KKT condtions, the KKT sufficient condi-tions, which imply that any x which satisfies the KKT necessary conditions and also meets these two convexity requirements is in fact a global minimum. So the point x = (−6, −6, −6)⊤ is the unique global minimum (unique since it was the only candidate). Example.1 Solve min −log (x1 + 1) − x2 s.t. g(x) � 2x1 + x2 − 3 ≤ 0 x1, x2 ≥ 0 1Thanks to Andy Sun. 2� � � � � � � � � � Solution. Firstly, observe that this is a convex optimization problem, since f(x) is convex (a pos-itive combination of the convex functions −x2 and −log (x1 + 1)), and the constraint functions g(x), −x1 and −x2 are convex (again, this is required for the feasible space to be convex, since we have ≤ constraints). Alternatively, in this case we can see that the feasible space is a polyhedron, which we know to be convex. Now, in order to use KKT, we need to assume which inequalities are active. Let’s start by assuming th at at a local minimum x, only g(x) ≤ 0 is active. This leads to the −1 2 system: x1+1 + u = 0, which gives u = 1 and x1 = −0.5, which is not feasible, so −11 our assumption cannot be correct. −1 2 Now try assuming g(x) ≤ 0 and −x1 ≤ 0 are active, giving the system x1+1 + u1 + −11 −1 u2 = 0, which gives u1 = 1, u2 = 1 and x2 = 3 (recall we assumed x1 = 0). 0 Now since it’s a convex optimization problem, and the Slater condition is trivially satis-fied, this is a global minimum by the KKT sufficient conditions. Example. The following example shows that the KKT theorem may not hold if the regularity condition is violated: Consider min x1 + x2 s.t. (x1 − 1)2 + x22 − 1 = 0 (x1 − 3)2 + x22 − 9 = 0 The feasible region is the intersection of two circles, one centered at the point (1, 0) with radius 1, the other at the point (3, 0) with radius 3. The intersection occurs at the origin, which is the optimal solution by inspection. We have ∇f (ˆx) = (1, 1)⊤ , ∇h1(ˆx) = (2x1 − 2, 2x2)⊤ = (−2, 0)⊤, and ∇h1(ˆx) = (2x1 − 6, 2x2)⊤ = (−6, 0)⊤ . So condition (1) cannot hold. 2 Conjugate Gradient Method2 Consider minimizing the quadratic function f(x) = 12 x⊤Qx + c⊤x. 1. d1, d2, . . . , dm are Q-conjugate if d⊤ i Qdj = 0, ∀i � j= 2Thanks to Allison Chang for notes 32. Let x0 be our initial point. 3. Direction d1 = −∇f(x0). 4. Direction dk+1 = −∇f(xk+1) + λkdk, where λk = ∇f(xk+1)⊤dk in the quadratic d⊤ k Qdk ||∇f(xk+1)||2 case (and λk = ||∇f(xk)||2 in the general case). It turns out that with each dk constructed in this way, d1, d2, . . . , dk are Q-conjugate. 5. By Expanding Subspace Theorem, xk+1 minimizes f(x) over the affine subspace S = x0 + span{d1, d2 . . . , dk}. 6. Hence finite convergence (n steps). 3 Barrier Methods A barrier function G(x), is a continuous function with the propertiy that it approaches ∞ as one of the gj(x) approaches 0 from below. Examples: p � p � 1 − log[−gj(x)] and − gj(x)j=1 j=1 Consider the primal/dual pair of linear optimization problems P: min c⊤x D: max b⊤p s.t. Ax = b s.t. A⊤p + s = c s.t. x ≥ 0 s.t. s ≥ 0 To solve P, we define the