logo

SCIENTIA SINICA Mathematica, Volume 47 , Issue 10 : 1119-1142(2017) https://doi.org/10.1360/N012016-00173

Accelerated bundle level methods with inexact oracle

More info
  • ReceivedOct 2, 2016
  • AcceptedJun 23, 2017
  • PublishedAug 8, 2017

Abstract

In this paper, four accelerated bundle level methods are proposed to solve smooth and convex, smooth and strongly convex optimization problems and a class of saddle-point problems, respectively, by using the inexact first-order information of the objective functions. For each method two cases, where the accuracy of the oracle is chosen by the user and where the accuracy of the oracle is fixed in advance, are studied. The desired accuracy of the approximate solution and its corresponding iteration complexity of each proposed algorithm in each case are analyzed.


Funded by

美国国家科学基金(DMS-1319050)

美国国家科学基金(DMS-1719932)


References

[1] Nemirovski A, Yudin D B, Dawson E R. Problem Complexity and Method Efficiency in Optimization. New York: A Wiley-Interscience Publication, 1983. Google Scholar

[2] Nemirovski A, Nesterov Y. Optimal methods of smooth convex minimization. Zh Vychisl Mat Mat Fiz, 1985, 25: 356-369. Google Scholar

[3] Nesterov Y. On an approach to the construction of optimal methods of minimization of smooth convex functions. Ekonomika Mat Metody, 1988, 24: 509-517. Google Scholar

[4] Devolder O, Glineur F, Nesterov Y. First-order methods of smooth convex optimization with inexact oracle. Math Program, 2014, 146: 37-75 CrossRef Google Scholar

[5] Lemar{é}chal C, Nemirovski A, Nesterov Y. New variants of bundle methods. Math Program, 1995, 69: 111-147. Google Scholar

[6] Kiwiel K C. Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities. Math Program, 1995, 69: 89-109. Google Scholar

[7] Br{ä}nnlund U, Kiwiel K C, Lindberg P O. A descent proximal level bundle method for convex nondifferentiable optimization. Oper Res Lett, 1995, 17: 121-126 CrossRef Google Scholar

[8] Ben-Tal A, Nemirovski A. Non-euclidean restricted memory level method for large-scale convex optimization. Math Program, 2005, 102: 407-456 CrossRef Google Scholar

[9] Lan G H. Bundle-level type methods uniformly optimal for smooth and nonsmooth convex optimization. Math Program, 2013, 149: 1-45. Google Scholar

[10] Chen Y M, Lan G H, Ouyang Y Y, et al. Fast bundle level type methods for unconstrained and ball-constrained convex optimization. ArXiv:1412.2128, 2014. Google Scholar

[11] Kelley Jr J E. The cutting-plane method for solving convex programs. J Soc Ind Appl Math, 1960, 8: 703-712 CrossRef Google Scholar

[12] Kiwiel K C. Proximity control in bundle methods for convex nondifferentiable minimization. Math Program, 1990, 46: 105-122 CrossRef Google Scholar

[13] Oliveira W, Sagastiz{á}bal C, Lemar{é}chal C. Convex proximal bundle methods in depth: A unified analysis for inexact oracles. Math Program, 2014, 148: 241-277 CrossRef Google Scholar

[14] Richt{á}rik P. Approximate level method for nonsmooth convex minimization. J Optim Theory Appl, 2012, 152: 334-350 CrossRef Google Scholar

[15] Noll D. Bundle method for non-convex minimization with inexact subgradients and function values. In: Computational and Analytical Mathematics. New York: Springer, 2013, 555-592. Google Scholar

[16] Kiwiel K C. Bundle methods for convex minimization with partially inexact oracles. Comput Optim Appl, 2012, 1702: 1703. Google Scholar

[17] Oliveira W, Sagastiz{á}bal C. Level bundle methods for oracles with on-demand accuracy. Optim Methods Software, 2014, 29: 1180-1209 CrossRef Google Scholar

[18] Lin H L. An inexact spectral bundle method for convex quadratic semidefinite programming. Comput Optim Appl, 2012, 53: 45-89 CrossRef Google Scholar

[19] Pang L P, Shen J. An approximate bundle method for solving variational inequalities. Commun Optim Theory, 2012, 1: 1-18. Google Scholar

[20] van Ackooij W, Sagastiz{á}bal C. Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J Optim, 2014, 24: 733-765 CrossRef Google Scholar

[21] Oliveira W, Sagastiz{á}bal C, Scheimberg S. Inexact bundle methods for two-stage stochastic programming. SIAM J Optim, 2011, 21: 517-544 CrossRef Google Scholar

[22] Kiwiel K C, Lemar{é}chal C. An inexact bundle variant suited to column generation. Math Program, 2009, 118: 177-206 CrossRef Google Scholar

[23] Emiel G, Sagastiz{á}bal C. Incremental-like bundle methods with application to energy planning. Comput Optim Appl, 2010, 46: 305-332 CrossRef Google Scholar

[24] Kiwiel K C. An inexact bundle approach to cutting-stock problems. INFORMS J Comput, 2010, 22: 131-143 CrossRef Google Scholar

[25] F{á}bi{á}n C I, Sz{\H{o}}ke Z. Solving two-stage stochastic programming problems with level decomposition. Comput Manag Sci, 2007, 4: 313-353 CrossRef Google Scholar

[26] Hinterm{ü}ller M. A proximal bundle method based on approximate subgradients. Comput Optim Appl, 2001, 20: 245-266 CrossRef Google Scholar

[27] F{á}bi{á}n C I. Bundle-type methods for inexact data. CEJOR Cent Eur J Oper Res, 2000, 8: 35-55. Google Scholar

[28] Kiwiel K C. A method of centers with approximate subgradient linearizations for nonsmooth convex optimization. SIAM J Optim, 2008, 18: 1467-1489 CrossRef Google Scholar

[29] Solodov M V. On approximations with finite precision in bundle methods for nonsmooth optimization. J Optim Theory Appl, 2003, 119: 151-165 CrossRef Google Scholar

[30] Kiwiel K C. A proximal bundle method with approximate subgradient linearizations. SIAM J Optim, 2006, 16: 1007-1023 CrossRef Google Scholar

[31] Zakeri G, Philpott A B, Ryan D M. Inexact cuts in benders decomposition. SIAM J Optim, 2000, 10: 643-657 CrossRef Google Scholar

[32] Malick J, Oliveira W, Zaourar S. Uncontrolled inexact information within bundle methods. Euro J Comput Optim, 2017, 5: 5-29 CrossRef Google Scholar

[33] Devolder O, Glineur F, Nesterov Y, et al. First-Order Methods with Inexact Oracle: The Strongly Convex Case. Technical Report, UCL, 2013. Google Scholar

[34] Villa S, Salzo S, Baldassarre L, et al. Accelerated and inexact forward-backward algorithms. SIAM J Optim, 2013, 23: 1607-1633 CrossRef Google Scholar

[35] Beck A, Teboulle M. Smoothing and first order methods: A unified framework. SIAM J Optim, 2012, 22: 557-580 CrossRef Google Scholar

[36] Schmidt M, Roux N L, Bach F. Minimizing finite sums with the stochastic average gradient. Math Program, 2017, 162: 83-112 CrossRef Google Scholar

[37] Jiang K F, Sun D F, Toh K C. An inexact accelerated proximal gradient method for large scale linearly constrained convex sdp. SIAM J Optim, 2012, 22: 1042-1064 CrossRef Google Scholar

[38] Nesterov Y. Smooth minimization of non-smooth functions. Math Program, 2005, 103: 127-152 CrossRef Google Scholar

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号