advertisement

LECTURE 21 LECTURE OUTLINE • Generalized forms of the proximal point algo- rithm • Interior point methods • Constrained optimization case - Barrier method • Conic programming cases All figures are courtesy of Athena Scientific, and are used with permission. 1 GENERALIZED PROXIMAL ALGORITHM • Replace quadratic regularization by more gen- eral proximal term. • Minimize possibly nonconvex f :⌘⌦ (−∞, ∞]. f (x) k k+1 k Dk (x, xk ) k+1 xk xk+1 Dk+1 (x, xk+1 ) x xk+2 x • Introduce a general regularization term Dk : ◆2n ⌘⌦ (−∞, ∞]: ⇤ ⌅ xk+1 ✏ arg minn f (x) + Dk (x, xk ) x⌥ • Assume attainment of min (but this is not au- tomatically guaranteed) • Complex/unreliable behavior when f is noncon- vex 2 SOME GUARANTEES ON GOOD BEHAVIOR • Assume Dk (x, xk ) ⌥ Dk (xk , xk ), ✓ x ✏ ◆n , k (1) Then we have a cost improvement property: f (xk+1 ) ⌃ f (xk+1 ) + Dk (xk+1 , xk ) − Dk (xk , xk ) ⌃ f (xk ) + Dk (xk , xk ) − Dk (xk , xk ) = f (xk ) • Assume algorithm stops only when xk in optimal solution set X ⇥ , i.e., ⇤ xk ✏ arg minn f (x) + Dk (x, xk )} x⌥ ⇒ xk ✏ X ⇥ / X⇥ • Then strict cost improvement for xk ✏ • Guaranteed if f is convex and (a) Dk (·, xk ) satisfies (1), and is convex and differentiable at xk (b) We have � ⇥ � ⇥ ri dom(f ) ri dom(Dk (·, xk )) = ⇣ Ø 3 EXAMPLE METHODS • Bregman distance function ⇥ 1� ⇧ Dk (x, y) = (x) − (y) − ⇢ (y) (x − y) , ck where : ◆n ⌘⌦ (−∞, ∞] is a convex function, differentiable within an open set containing dom(f ), and ck is a positive penalty parameter. • Majorization-Minimization algorithm: Dk (x, y) = Mk (x, y) − Mk (y, y), where M satisfies ✓ y ✏ ◆n , k = 0, 1, Mk (y, y) = f (y), ✓ x ✏ ◆n , k = 0, 1, . . . Mk (x, xk ) ⌥ f (xk ), • Example for case f (x) = R(x) + ⇠Ax − b⇠2 , where R is a convex regularization function M (x, y) = R(x) + ⇠Ax − b⇠2 − ⇠Ax − Ay⇠2 + ⇠x − y⇠2 • Expectation-Maximization (EM) algorithm (special context in inference, f nonconvex) 4 INTERIOR POINT METHODS • Consider min f (x) s. t. gj (x) ⌃ 0, j = 1, . . . , r A barrier function, that is continuous and goes to ∞ as any one of the constraints gj (x) approaches 0 from negative values; e.g., • B(x) = − r ⌧ ⇤ j=1 ⌅ ln −gj (x) , B(x) = − • Barrier method: Let ⇤ ⌅ xk = arg min f (x) + ⇧k B(x) , x⌥S r ⌧ j=1 1 . gj (x) k = 0, 1, . . . , where S = {x | gj (x) < 0, j = 1, . . . , r} and the parameter sequence {⇧k } satisfies 0 < ⇧k+1 < ⇧k for all k and ⇧k ⌦ 0. B(x) , "-./ Boundary of S ,0 B(x) "-./ ,0*1*, < "#$%&'()*#+*! Boundary of S "#$%&'()*#+*! S ! 5 BARRIER METHOD - EXAMPLE 1 1 0.5 0.5 0 0 -0.5 -0.5 -1 -1 2.05 2.1 2.15 2.2 2.25 minimize f (x) = 1 2 subject to 2 ⌃ x1 , � 2.05 2.1 2.15 2.2 2.25 1 2 2 2 (x ) + (x ) ⇥ with optimal solution x⇥ = (2, 0). • Logarithmic barrier: B(x) = − ln (x1 − 2) � ⇥ ⇡ • We have xk = 1 + 1 + ⇧k , 0 from xk ✏ arg min x1 >2 ⇤ � 1 2 1 2 2 2 (x ) + (x ) ⇥ 1 ⌅ − ⇧k ln (x − 2) • As ⇧k is decreased, the unconstrained minimum xk approaches the constrained minimum x⇥ = (2, 0). • As ⇧k ⌦ 0, computing xk becomes more di⌅cult because of ill-conditioning (a Newton-like method is essential for solving the approximate problems). 6 CONVERGENCE • Every limit point of a sequence {xk } generated by a barrier method is a minimum of the original constrained problem. Proof: Let {x} be the limit of a subsequence {xk }k⌥K . Since xk ✏ S and X is closed, x is feasible for the original problem. If x is not a minimum, there exists a feasible x⇥ such that f (x⇥ ) < f (x) and therefore also an interior point x̃ ✏ S such that f (x̃) < f (x). By the definition of xk , f (xk ) + ⇧k B(xk ) ⌃ f (x̃) + ⇧k B(x̃), ✓ k, so by taking limit f (x) + lim inf ⇧k B(xk ) ⌃ f (x̃) < f (x) k⌅⌃, k⌥K Hence lim inf k⌅⌃, k⌥K ⇧k B(xk ) < 0. If x ✏ S , we have limk⌅⌃, k⌥K ⇧k B(xk ) = 0, while if x lies on the boundary of S , we have by assumption limk⌅⌃, k⌥K B(xk ) = ∞. Thus lim inf ⇧k B(xk ) ⌥ 0, k⌅⌃ – a contradiction. 7 SECOND ORDER CONE PROGRAMMING • Consider the SOCP minimize c⇧ x subject to Ai x − bi ✏ Ci , i = 1, . . . , m, where x ✏ ◆n , c is a vector in ◆n , and for i = 1, . . . , m, Ai is an ni ⇤ n matrix, bi is a vector in ◆ni , and Ci is the second order cone of ◆ni . • We approximate this problem with minimize c⇧ x + ⇧k m ⌧ i=1 Bi (Ai x − bi ) subject to x ✏ ◆n , Ai x − bi ✏ int(Ci ), i = 1, . . . , m, where Bi is the logarithmic barrier function: Bi (y) = − ln � yn2 i − (y12 ⇥ + · · · + yn2 i −1 ) , y ✏ int(Ci ), and {⇧k } is a positive sequence with ⇧k ⌦ 0. • Essential to use Newton’s method to solve the approximating problems. • Interesting complexity analysis 8 SEMIDEFINITE PROGRAMMING • Consider the dual SDP maximize b⇧ ⌥ subject to D − (⌥1 A1 + · · · + ⌥m Am ) ✏ C, where b ✏ ◆m , D, A1 , . . . , Am are symmetric matrices, and C is the cone of positive semidefinite matrices. • The logarithmic barrier method uses approxi- mating problems of the form maximize � ⇥ b ⌥ + ⇧k ln det(D − ⌥1 A1 − · · · − ⌥m Am ) ⇧ over all ⌥ ✏ ◆m such that D − (⌥1 A1 + · · · + ⌥m Am ) is positive definite. • Here ⇧k > 0 and ⇧k ⌦ 0. Furthermore, we should use a starting point such that D − ⌥1 A1 − · · · − ⌥m Am is positive definite, and Newton’s method should ensure that the iterates keep D − ⌥1 A1 − · · · − ⌥m Am within the positive definite cone. • 9 MIT OpenCourseWare http://ocw.mit.edu 6.253 Convex Analysis and Optimization Spring 2012 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.