advertisement

LECTURE 24 LECTURE OUTLINE • Gradient proximal minimization method • Nonquadratic proximal algorithms • Entropy minimization algorithm • Exponential augmented Lagrangian mehod • Entropic descent algorithm ************************************** References: • Beck, A., and Teboulle, M., 2010. “Gradient- Based Algorithms with Applications to Signal Recovery Problems, in Convex Optimization in Signal Processing and Communications (Y. Eldar and D. Palomar, eds.), Cambridge University Press, pp. 42-88. • Beck, A., and Teboulle, M., 2003. “Mirror De- scent and Nonlinear Projected Subgradient Methods for Convex Optimization,” Operations Research Letters, Vol. 31, pp. 167-175. • Bertsekas, D. P., 1999. Nonlinear Programming, Athena Scientific, Belmont, MA. All figures are courtesy of Athena Scientific, and are used with permission. 1 PROXIMAL AND GRADIENT PROJECTION • Proximal algorithm to minimize convex f over closed convex X � xk+1 ✏ arg min f (x) + x⌥X 1 ⇠x − xk ⇠2 2ck f (xk ) f (x) k k − 1 ⇥x − xk ⇥2 2ck xk xk+1 x x • Let f be diﬀerentiable and assume ⌃ ⌃ ⌃⇢f (x) − ⇢f (y)⌃ ⌃ L ⇠x − y⇠, ✓ x, y ✏ X • Define the linear approximation function at x !(y; x) = f (x) + ⇢f (x)⇧ (y − x), y ✏ ◆n • Connection of proximal with gradient projection � 1 y = arg min !(z; x) + ⇠z − x⇠2 z⌥X 2α 2 � ⇥ = PX x−α⇢f (x) GRADIENT-PROXIMAL METHOD I • Minimize f (x)+g(x) over x ✏ X , where X : closed convex, f , g : convex, f is differentiable . • Gradient-proximal method: � xk+1 ✏ arg min !(x; xk ) + g(x) + x⌥X 1 ⇠x − xk ⇠2 2α • Recall key inequality: For all x, y ✏ X L ⇠y − x⇠2 2 • Cost reduction for α ⌃ 1/L: f (y) ⌃ !(y; x) + L ⇠xk+1 − xk ⇠2 + g(xk+1 ) 2 1 ⇠xk+1 − xk ⇠2 ⌃ !(xk+1 ; xk ) + g(xk+1 ) + 2α ⌃ !(xk ; xk ) + g(xk ) f (xk+1 ) + g(xk+1 ) ⌃ !(xk+1 ; xk ) + = f (xk ) + g(xk ) • This is a key insight for the convergence analy- sis. 3 GRADIENT-PROXIMAL METHOD II • Equivalent definition of gradient-proximal: zk = xk − α⇢f (xk ) � xk+1 ✏ arg min g(x) + x⌥X 1 ⇠x − zk ⇠2 2α • Simplifies the implementation of proximal, by using gradient iteration to deal with the case of an inconvenient component f • This is similar to incremental subgradient-proxi- mal method, but the gradient-proximal method does not extend to the case where the cost consists of the sum of multiple components. • Allows a constant stepsize (under the restriction α ⌃ 1/L). This does not extend to incremental methods. • Like all gradient and subgradient methods, con- vergence can be slow. • There are special cases where the method can be fruitfully applied (see the reference by Beck and Teboulle). 4 GENERALIZED PROXIMAL ALGORITHM • Introduce a general regularization term Dk : ⇤ xk+1 ✏ arg min f (x) + Dk (x, xk ) x⌥X ⌅ • Example: 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. • All the ideas for applications and connections of the quadratic form of the proximal algorithm extend to the nonquadratic case (although the analysis may not be trivial). In particular we have: − A dual proximal algorithm (based on Fenchel duality) − Equivalence with (nonquadratic) augmented Lagrangean method − Combinations with polyhedral approximations (bundle-type methods) − Incremental subgradient-proximal methods − Nonlinear gradient projection algorithms 5 ENTROPY MINIMIZATION ALGORITHM • A special case involving entropy regularization: xk+1 ✏ arg min x⌥X ✏ 1 ⌧ i f (x) + x ck n ln i=1 ⌦ i x xik ⌦⇣ −1 where x0 and all subsequent xk have positive components • We use Fenchel duality to obtain a dual form of this minimization • Note: The logarithmic function p(x) = ✏ x(ln x − 1) 0 ∞ if x > 0, if x = 0, if x < 0, and the exponential function p⌥ (y) = ey are a conjugate pair. • The dual problem is yk+1 ✏ arg minn y⌥ ✏ 1 ⌧ i ck y i f (y) + xk e ck n ⌥ i=1 6 ⇣ EXPONENTIAL AUGMENTED LAGRANGIAN • The dual proximal iteration is xik+1 = i i ck yk+1 xk e , i = 1, . . . , n where yk+1 is obtained from the dual proximal: yk+1 ✏ arg minn y⌥ ✏ 1 ⌧ i ck y i f (y) + xk e ck n ⌥ i=1 ⇣ • A special case for the convex problem minimize f (x) subject to g1 (x) ⌃ 0, . . . , gr (x) ⌃ 0, x ✏ X is the exponential augmented Lagrangean method • Consists of unconstrained minimizations xk ✏ arg min x⌥X ✏ 1 ⌧ j ck gj (x) f (x) + µk e ck r j=1 followed by the multiplier iterations µjk+1 = j µkj eck gj (xk ) , 7 j = 1, . . . , r ⇣ , NONLINEAR PROJECTION ALGORITHM • Subgradient projection with general regularization term Dk : xk+1 ⇤ ⌅ ˜ (xk )⇧ (x−xk )+Dk (x, xk ) ✏ arg min f (xk )+ ⇢f x⌥X ˜ f (xk ) is a subgradient of f at xk . Also where ⇢ called mirror descent method. • Linearization of f simplifies the minimization • The use of nonquadratic linearization is useful in problems with special structure • Entropic descent method: Minimize f⌅(x) over ⇤ � the unit simplex X = x ⌥ 0 | ni=1 xi = 1 . • Method: xk+1 ✏ arg min x⌥X n ⌧ i x gki i=1 1 + ln αk i x xik ⌦⌦ ˜ (xk ). where gki are the components of ⇢f • This minimization can be done in closed form: i i −αk gk xk e n j −αk g j k x e j=1 k xik+1 = � 8 , i = 1, . . . , n 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.