Subgradient Optimization, Generalized Programming, and Nonconvex Duality

Subgradient Optimization, Generalized Programming, and Nonconvex Duality 1 1 1.1 Subgradient Optimization Review of Subgradients Recall the following facts about subgradients of convex functions. Let S ⊂ IRn be a given nonempty convex set, and let f (·) : S → IR be a convex function. Then then ξ ∈ IRn is a subgradient of f (·) at x̄ ∈ S if ¯ for all x ∈ S . f (x) ≥ f (¯ x) + ξ T (x − x) If x ¯ ∈ intS, then there exists a subgradient of f (·) at x. ¯ The collection of subgradients of f (·) at x is denoted by ∂f (x), and the operator ∂f (·) is called the subdifferential of f (·). Recall that if x ∈ intS, then ∂f (x) is a nonempty closed convex set. If f (·) is differentiable at x = x ¯ and ∇f (¯ x) = 0 , then −∇f (¯ x) is a descent direction of f (·) at x. ¯ However, if f (·) is not differentiable at x = x ¯ and ξ is a subgradient, then −ξ is not necessarily a descent direction of f (·) at x̄. 1.2 Computing a Subgradient Subgradients play a very important role in algorithms for non-differentiable optimization. In these algorithms, we typically have a subroutine that receives as input a value x, and has output ξ where ξ is some subgradient of f (x). 1.3 The Subgradient Method for Minimizing a Convex Function Suppose that f (·) is a convex function, and that we seek to solve: P : z ∗ = minimizex f (x) x ∈ IRn . s.t. 2 The following algorithm generalizes the steepest descent algorithm and can be used to minimize a nondifferentiable convex function f (x). Subgradient Method Step 0: Initialization. Start with any point x1 ∈ IRn . Choose an infinite sequence of positive step-size values {αk }∞ k=1 . Set k = 1. Step 1: Compute a subgradient. Compute ξ ∈ ∂f (xk ). If ξ = 0, STOP. xk solves P . Step 2: Compute step-size. Compute step-size αk from the stepsize series. ξ . Set k ← k + 1 Step 3: Update Iterate. Set xk+1 ← xk − αk ξ and go to Step 1. Note in this algorithm that the step-size αk at each iteration is determined without a line-search, and in fact is predetermined in Step 0. One reason for this is that a line-search might not be worthwhile, since −ξ is not necessarily a descent direction. As it turns out, the viability of the subgradient method depends critically on the sequence of step-sizes: Theorem 1 Suppose that f (·) is a convex function whose domain D ⊂ IRn satisfies intD =  ∅. Suppose that {αk }∞ k=1 satisfies: lim αk = 0 k→∞ and ∞
αk = ∞ . k=1 Let x1 , x2 , . . . , be the iterates generated by the subgradient method. Then inf f (xk ) = z ∗ . k Proof: Suppose that the result is not true. Then there exists  > 0 such that f (xk ) ≥ z ∗ +  for all k = 1, . . .. Let T = {x ∈ IRn | f (x) ≤ z ∗ + }. Then there exists x ˆ and ρ > 0 for which B(ˆ x, ρ) ⊂ T , where B(ˆ x, ρ) := {x ∈ 3 IRn | x − x̂ ≤ ρ}. Let ξ k be the subgradient chosen by the subgradient method for the iterate xk . By the subgradient inequality we have for all k = 1, . . .:  ξk f (xk ) ≥ z ∗ +  ≥ f x ˆ+ρ k ξ   ≥ f (xk ) + (ξ k )T ξk x ˆ + ρ k ) − xk ξ  , which upon rearranging yields: (ξ k )T (x̂ − xk ) ≤ −ρ (ξ k )T ξ k = −ρ ξ k . ξk We also have for each k: xk+1 − x ˆ 2 k = xk − αk ξξk  − x̂ = xk − x ˆ 2 + αk2 − 2αk (ξ ≤ xk − x ˆ 2 + αk2 − 2αk ρ = xk − x̂ 2 + αk (αk − 2ρ) . 2 k )T (xk −ˆ x) ξ k  For k sufficiently large, say for all k ≥ K, we have αk ≤ ρ, whereby: ˆ xk+1 − x 2 ≤ xk − x ˆ 2 − ραk . However, this implies by induction that for all j ≥ 1 we have: ˆ xK+j − x 2 ≤ xK − x ˆ 2 −ρ K+j
αk . k=K+1 Now for j sufficiently large the right-hand side expression is negative, since ∞  k=1 αk = ∞, which yields a contradiction since the left-hand side must be nonnegative. 4 1.4 The Subgradient Method with Projections Problem P posed at the start of Subsection 1.3 generalizes to the following problem: PS : z ∗ = minimizex f (x) x∈S , s.t. where S is a given closed convex set. We suppose that S is a simple enough set that we can easily compute projections onto S. This means that for any point c ∈ IRn , we can easily compute: ΠS (c) := arg min c − x . x∈S The following algorithm is a simple extension of the subgradient method presented in Subsection 1.3, but includes a projection computation so that all iterate values xk satisfy xk ∈ S. Projected Subgradient Method Step 0: Initialization. Start with any point x1 ∈ S. Choose an infinite sequence of positive step-size values {αk }∞ k=1 . Set k = 1. Step 1: Compute a subgradient. Compute ξ ∈ ∂f (xk ). If ξ = 0, STOP. xk solves P . Step 2: Compute step-size. Compute step-size αk from the stepsize series.   ξ . Set k ← Step 3: Update Iterate. Set xk+1 ← ΠS xk − αk ξ k + 1 and go to Step 1. Similar to Theorem 1, we have: Theorem 2 Suppose that f (·) is a convex function whose domain D ⊂ IRn satisfies intD ∩ S = ∅. Suppose that {αk }∞ k=1 satisfies: lim αk = 0 k→∞ and ∞
k=1 5 αk = ∞ . Let x1 , x2 , . . . , be the iterates generated by the projected subgradient method. Then inf f (xk ) = z ∗ . k The proof of Theorem 2 relies on the following “non-expansive” property of the projection operator ΠS (·): Lemma 3 Let S be a closed convex set and let ΠS (·) be the projection operator onto S. Then for any two vectors c1 , c2 ∈ IRn , ΠS (c1 ) − ΠS (c1 ) ≤ c1 − c2 . Proof: Let c¯1 = ΠS (c1 ) and let c¯2 = ΠS (c1 ). Then from Theorem 4 of the Constrained Optimization notes (the basic separating hyperplane theorem) we have: (c1 − c̄1 )T (x − c̄1 ) ≤ 0 for all x ∈ S , and (c2 − c̄2 )T (x − c̄2 ) ≤ 0 for all x ∈ S . In particular, because c¯2 ∈ S and c¯1 ∈ S it follows that: (c1 − c̄1 )T (¯ c2 − c̄1 ) ≤ 0 and (c2 − c̄2 )T (¯ c1 − c̄2 ) ≤ 0 . Then note that c1 − c 2 2 = c̄1 − c̄2 + (c1 − c̄1 − c2 + c̄2 ) 2 = c̄1 − c̄2 2 + c1 − c̄1 − c2 + c¯2 ≥ c̄1 − c̄2 2 + 2(¯ c1 − c̄2 )T (c1 − c̄1 ) + 2(¯ c1 − c̄2 )T (−c2 + c¯2 ) ≥ c̄1 − c̄2 2 , 2 + 2(¯ c1 − c̄2 )T (c1 − c̄1 − c2 + c¯2 ) from which it follows that c1 − c2 ≥ c̄1 − c̄2 . The proof of Theorem 2 can easily be constructed by using Lemma 3 and by following the logic used in the proof of Theorem 1, and is left as an Exercise. 6 1.5 Solving the Lagrange Dual via the Subgradient Method We start with the primal problem: OP : z ∗ = minimumx f (x) gi (x) s.t. ≤ 0, i = 1, . . . , m x∈X . We create the Lagrangian L(x, u) := f (x) + uT g(x) . The dual function is given by: L∗ (u) := minimumx f (x) + uT g(x) x∈X . s.t. The dual problem is: D : v ∗ = maximumu s.t. L∗ (u) u≥0. Recall that L∗ (u) is a concave function. For concave functions we work with supergradients. If f (·) is a concave function whose domain is the convex set S, then g ∈ IRn is a supergradient of f (·) at x̄ ∈ S if ¯ f (x) ≤ f (¯ x) + g T (x − x) for all x ∈ S . The premise of Lagrangian duality is that it is “easy” to compute L∗ (ū) for any given u. ¯ That is, it is easy to compute an optimal solution x ¯ ∈ X of L∗ (¯ u) := minimumx∈X f (x) + u ¯T g(x) = f (¯ x) , x) + u ¯T g(¯ 7 for any given ū. It turns out that computing supergradients of L∗ (·) is then also easy. We have: Proposition 4 Suppose that u ¯ is given and that x ¯ ∈ X is an optimal solution of L∗ (¯ u) = min f (x) + u ¯T g(x). Then g := g(¯ x) is a supergradient of L∗ (·) at u = ū. x∈X Proof: For any u ≥ 0 we have L∗ (u) = min f (x) + uT g(x) x∈X ≤ f (¯ x) + uT g(¯ x) = f (¯ x) + u ¯T g(¯ x) + (u − u) ¯ T g(¯ x) = min f (x) + u x)T (u − u) ¯ ¯T g(x) + g(¯ = L (¯ u) + g T (u − u) ¯ . x∈X ∗ Therefore g is a supergradient of L∗ (·) at ū. q.e.d. The Lagrange dual problem D is in the same format as problem PS of Subsection 1.4, with S = IRm + . In order to apply the projected subgradient method to this problem, we need to be able to conveniently compute the projection of any vector v ∈ IRm onto S = IRm + . This indeed is easy. Let u ∈ IRn be given, and define u+ to be the vector each of whose components is the positive part of the respective component of v. For example, if u = (2, −3, 0, 1, −5), then u+ = (2, 0, 0, 1, 0). Then it is easy to see that ΠS (u) = u+ . We can now state the subgradient method for solving the Lagrange dual problem: Subgradient Method for Solving the Lagrange Dual Problem Step 0: Initialization. Start with any point u1 ∈ IRn+ . Choose an infinite sequence of positive step-size values {αk }∞ k=1 . Set k = 1. 8 Step 1: Compute a supergradient. Solve for an optimal solution x ¯ of L∗ (uk ) = min f (x) + (uk )T g(x). Set g := g(¯ x). If g = 0, STOP. xk solves D. x∈X Step 2: Compute step-size. Compute step-size αk from step-size series.  g Step 3: Update Iterate. Set uk+1 ← uk + αk g and go to Step 1. + . Set k ← k +1 Notice in Step 3 that the “(u)+ ” operation is simply the projection of u onto the nonnegative orthant IRn+ . 2 Generalized Programming and Nonconvex Duality 2.1 Geometry of nonconvex duality and the equivalence of convexification and dualization We start with the primal problem: OP : z ∗ = minimumx f (x) gi (x) s.t. ≤ 0, i = 1, . . . , m x∈X . We create the Lagrangian L(x, u) := f (x) + uT g(x) . The dual function is given by: L∗ (u) := minimumx f (x) + uT g(x) x∈X . s.t. 9 The dual problem is: D : v ∗ = maximumu s.t. L∗ (u) u≥0. Herein we will assume that f (·) and g1 (·), . . . , gm (·) are continuous and X is a compact set. We will not assume any convexity. Recall the definition of I:   I := (s, z) ∈ IRm+1 | there exists x ∈ X for which s ≥ g(x) and z ≥ f (x) . Let C be the convex hull of I. That is, C is the smallest convex set containing I. From the assumption that X is compact and that f (·) and g1 (·), . . . , gm (·) are continuous, it follows that C is a closed convex set. Let ẑ := min{z : (0, z) ∈ C} , i.e., ẑ is the optimal value of the convexified primal problem, which has been s of resources and costs. convexified in the column geometry z Let H(u) := {(s, z) ∈ IRm+1 : uT s + z = L∗ (u)} . Then we say that H(u) supports I (or C) if uT s + z ≥ L∗ (u) for every (s, z) ∈ I (or C), and uT s + z = L∗ (u) for some (s, z) ∈ I (or C). Lemma 5 If u ≥ 0, then H(u) supports I and C. Proof: Let (s, z) ∈ I. Then uT s + z ≥ uT g(x) + f (x) for some x ∈ X. Thus uT s + z ≥ inf x∈X uT g(x) + f (x) = L∗ (u). Furthermore, setting x̄ = arg minx∈X {f (x) + uT g(x)} and (s, z) = (g(¯ x), f (¯ x)), we have uT s + z = L∗ (u). Thus H(u) supports I. But then H(u) also supports C, since C is the convex hull of I. Lemma 6 (Weak Duality) ẑ ≥ v ∗ . 10 I,C z* v* H(u) = {(s,z)|uTs + z = L*(u)} -u Figure 1: I, C, and H(u). Proof: If ẑ = +∞, then we are done. Otherwise, let (0, z) ∈ C. For any u ≥ 0, H(u) supports I from Lemma 5. Therefore L∗ (u) ≤ uT 0 + z = z. Thus v ∗ = sup L∗ (u) ≤ inf z = ẑ. (0,z)∈C u≥0 Lemma 7 (Strong Duality) ẑ = v ∗ . Proof: In view of Lemma 6, it suffices to show that zˆ ≤ v ∗ . If zˆ = −∞, we are done. If not, let r < ẑ be given. Then (0, r) ∈ C, and so there u, α) = (0, 0) is a hyperplane separating (0, r) from C. Thus there exists (¯ ¯T 0 + αr < θ and u and θ such that u ¯T s + αz ≥ θ for all (s, z) ∈ C. This 11 immediately implies u ¯ ≥ 0, α ≥ 0. If α = 0, we can re-scale so that α = 1. Then ūT s + z ≥ θ > r for all (s, z) ∈ C. In particular, ūT g(x) + f (x) ≥ θ > r  for all x ∈ X,  ¯T g(x) + f (x) u) = inf x∈X u which implies that L∗ (¯ arbitrary value with r < ẑ, we have v ∗ ≥ L∗ (ū) ≥ ẑ. > r. Since r is an It remains to analyze the case when α = 0. In this case we have θ > 0 and ūT s ≥ θ > 0 for all (s, z) ∈ C. With (s, z) = (g(x), f (x)) for a given x ∈ X, we have for all λ ≥ 0: u)T g(x) . uT g(x) = f (x) + (u + λ¯ L∗ (u) + λθ ≤ f (x) + uT g(x) + λ¯ Then u)T g(x)} = L∗ (u + λ¯ u) . L∗ (u) + λθ ≤ inf {f (x) + (u + λ¯ x∈X Since θ > 0 and λ was any nonnegative scalar, L∗ (u+ λū) → +∞ as λ → ∞, and so v ∗ ≥ L∗ (u + λū) implies v ∗ = +∞. Thus, v ∗ ≥ ẑ. 2.2 The Generalized Programming Algorithm Consider the following algorithm: Generalized Programming Algorithm for Solving the Lagrange Dual Problem Step 0 E k = {x1 , . . . , xk }, LB = −∞, UB = +∞. Step 1 Solve the following linear program (values in brackets are the dual variables): k i (LPk ): minλ i=1 λi f (x ) s.t. k λ g(xi ) ≤ 0 (u) ik=1 i i=1 λi λ≥0, 12 =1 (θ) for λk , uk , θk , and also define: x̃k := k
λki xi , s̃k := i=1 k
λki g(xi ), z̃ k := i=1 k
λki f (xi ) = θk . i=1 Step 2 (Dual function evaluation.) Solve: (Dk ): L∗ (uk ) = min{f (x) + (uk )T g(x)} x∈X for xk+1 . Step 3 UB := min{UB, z̃ k = θk }, LB := max{LB, L∗ (uk )}. If UB − LB ≤ , stop. Otherwise, go to Step 4. Step 4 E k+1 := E k ∪ {xk+1 }, k := k + 1, go to Step 1. Notice that the linear programming dual of (LPk ) is: (DPk ): maxu,θ θ s.t. −uT g(xi ) + θ ≤ f (xi ) i = 1, . . . , k u≥0, which equivalently is: (DPk ): maxu,θ θ s.t. θ ≤ f (xi ) + uT g(xi ) i = 1, . . . , k u≥0. This can be re-written as: (DPk ): max min {f (x) + uT g(x)} . u≥0 x∈E k Note that (uk+1 , θk+1 ) is always feasible in (DPk ) and (u, θ) = (u, L∗ (u)) is always feasible for (DPk ) for u ≥ 0. Geometrically, the generalized programming algorithm can be viewed as an “inner convexification” process for the primal (see Figure 2), and as an “outer convexification” process via supporting hyperplanes for the dual problem (see Figure 2). 13 z C (g(x4), f(x4)) (g(x1), f(x1)) (g(x3), f(x3)) (g(x2), f(x2)) (g(x5), f(x5)) y Figure 2: The primal geometry of the generalized programming algorithm. Proposition 8 (i) θk are decreasing in k (ii) (˜ sk , z̃ k ) ∈ C (iii) uk is feasible for (D) (iv) L∗ (uk ) ≤ v ∗ = zˆ ≤ z̃ k = θk . (v) If f (·) and g1 (·), . . . , gm (·) are convex functions and X is a convex set, xk ) ≤ θk , where z ∗ is the then x ˜k is feasible for (P) and ẑ = z ∗ ≤ f (˜ optimal value of (P). Proof: 14 V f(x1)+uTg(x1) f(x3)+uTg(x3) f(x2)+uTg(x2) θ4 f(x4)+uTg(x4) f(x5)+uTg(x5) u4 Figure 3: The dual geometry of the generalized programming algorithm. (i) follows since (DPk+1 ) has one extra constraint compared to (DPk ), so θk+1 ≤ θk . (ii) follows since (˜ sk , z̃ k ) is in the convex hull of I, which is C. (iii) follows since by definition, uk ≥ 0. sk , z̃ k ) ∈ (iv) L∗ (uk ) ≤ v ∗ by definition of v ∗ , and v ∗ = zˆ by Lemma 7. Since (˜ k k k k k C, and s˜ ≤ 0, (0, z̃ ) ∈ C, and so zˆ ≤ z̃ . Furthermore, z = θ follows from linear programming duality.  ˜k ∈ X, and f (˜ xk ) ≤ ki=1 λki f (xi ) ≤ (v) Since each xi ∈ X, i = 1, . . . , k, then x  k k i θk , and g(˜ xk ) ≤ ˜k is feasible for P and so i=1 λi g(x ) ≤ 0. Thus, x ∗ k z ≤ f (x̃ ). Theorem 9 (Convergence of the generalized programming algorithm) Suppose u1 , u2 , . . . , are the iterate values of u computed by the generalized programming algorithm, and suppose that there is a convergent subsequence 15 of u1 , u2 , . . . , converging to u∗ . Then 1. u∗ solves (D), and 2. limk→∞ θk = zˆ = v ∗ . Proof: For any j ≤ k we have f (xj ) + (uk )T g(xj ) ≥ θk ≥ v ∗ . Taking limits as k → ∞, we obtain: f (xj ) + (u∗ )T g(xj ) ≥ θ¯ ≥ v ∗ , where θ¯ := limk→∞ θk . (This limit exists since θk are a monotone decreasing sequence bounded below by v ∗ .) Since gi (·) is continuous and X is compact, there exists B > 0 for which |gi (x)| ≤ B for all x ∈ X, i = 1, . . . , m. Thus k+1 |L(x k k+1 , u ) − L(x ∗ k ∗ T k+1 , u )| = |(u − u ) g(x )| ≤ B m
|uki − u∗i | . i=1 For any  > 0 and for k sufficiently large, the RHS is bounded above by . Thus ¯ . L∗ (uk ) = L(xk+1 , uk ) ≥ L(xk+1 , u∗ )− = f (xk+1 )+(u∗ )T g(xk+1 )− ≥ θ− ˆ Therefore since L∗ (u∗ ) ≤ v ∗ , Thus in the limit L∗ (u∗ ) ≥ θ¯ ≥ v ∗ = z. ∗ ∗ ∗ L (u ) = θ¯ = v = z. ˆ Corollary 10 If OP has a known Slater point x0 and x0 ∈ E k for some k, then the sequence of uk are bounded and so have a convergent subsequence. Proof: Without loss of generality we can assume that x0 ∈ E k for the initial set E k . Then for all k we have: −(uk )T g(x0 ) + θk ≤ f (x0 ) , 16 and g(x0 ) < 0, from which it follows that 0 ≤ (uk )i ≤ −v ∗ + f (x0 ) −θk + f (x0 ) ≤ , −gi (x0 ) −gi (x0 ) i = 1, . . . , m . Therefore u1 , u2 , . . . , lies in a bounded set, whereby there must be a convergent subsequence of u1 , u2 , . . .. 3 Exercises based on Generalized Programming and Subgradient Optimization 1. Consider the primal problem: cT x OP : minimumx Ax − b ≤ 0 s.t. x ∈ {0, 1}n . Here g(x) = Ax − b and P = {0, 1}n = {x | xj = 0 or 1, j = 1, . . . , n}. We create the Lagrangian: L(x, u) := cT x + uT (Ax − b) and the dual function: L∗ (u) := minimumx∈{0,1}n cT x + uT (Ax − b) The dual problem then is: D : maximumu L∗ (u) s.t. 17 u≥0 Now let us choose u ¯ ≥ 0. Notice that an optimal solution x ¯ of L∗ (¯ u) is: 0 if (c − AT ū)j ≥ 0 1 if (c − AT ū)j ≤ 0 x ¯j = for j = 1, . . . , n. Also, ¯T (A¯ x − b) = −¯ u) = cT x ¯+u uT b − L∗ (¯ n
(c − AT u) ¯j − . j=1 Also g := g(¯ x−b x) = A¯ is a subgradient of L∗ (ū). Now consider the following data instance of this problem: ⎛ ⎞ ⎛ ⎞ 7 −8 12 ⎜ −2 −2 ⎟ ⎜ −1 ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ 5 ⎟ , b = ⎜ 45 ⎟ A=⎜ 6 ⎜ ⎟ ⎜ ⎟ ⎝ −5 ⎝ 20 ⎠ 6 ⎠ 3 12 42 and cT = ( −4 1 ) . Solve the Lagrange dual problem of this instance using the subgradient algorithm starting at u1 = (1, 1, 1, 1, 1)T , with the following step-size choices: • αk = • αk = • αk = 1 k for k = 1, . . .. √1 for k = 1, . . .. k 0.2 × (0.75)k for k = 1, . . .. • a step-size rule of your own. 2. Prove Theorem 2 of the notes by using Lemma 3 and by following the logic used in the proof of Theorem 1. 18 3. The generalized programming algorithm assumes that the user is given start vectors x1 , . . . , xk ∈ X for which k
λi g(xi ) ≤ 0 i=1 has a solution for some λ1 ≥ 0, . . . , λk ≥ 0 satisfying k
λi = 1 . i=1 Here we describe an algorithm for finding such a set of start vectors. Step 0 Choose any k vectors x1 , . . . , xk ∈ X. Step 1 Solve the following linear program, where the values in brackets are the dual variables: (LPk ) minλ,σ σ s.t. k  i=1 k  i=1 λi g(xi ) − eσ ≤ 0 (u) λi = 1 (ω) λ ≥ 0, σ ≥ 0 for λk , σk , uk , ω k . The dual of (LPk ) is (DPk ): (DPk ) maxu,ω ω s.t. ω ≤ uT g(xi ), i = 1, . . . , k eT u ≤ 1 u≥0 19 Step 2 If σ k = 0, STOP. Otherwise, solve the optimization problem:  min uk T x∈X g(x) , and let xk+1 be an optimal solution of this problem. Step 3 k ← k + 1. Go to Step 1. Prove the following: a. LP k and DP k are always feasible. b. If the algorithm stops, then it provides a feasible start for the regular generalized programming problem. c. The sequence of σ k values is nonincreasing. d. The uk vectors all lie in a closed and bounded convex set. What is this set? e. There exists a convergent subsequence of the uk vectors. f. Define D∗ (u) = minx∈X {uT g(x)}. Show that D∗ (uk ) ≤ σ k . 20