Abstract
Uniformly optimal convex programming algorithms have been designed to achieve the optimal complexity bounds for convex optimization problems regardless of the level of smoothness of the objective function. In this paper, we present a generic framework to extend such existing algorithms to solve more general nonlinear, possibly nonconvex, optimization problems. The basic idea is to incorporate a local search step (gradient descent or Quasi-Newton iteration) into the uniformly optimal convex programming methods, and then enforce a monotone decreasing property of the function values computed along the trajectory. While optimal methods for nonconvex programming are not generally known, algorithms of these types will achieve the best known complexity for nonconvex problems, and the optimal complexity for convex ones without requiring any problem parameters. As a consequence, we can have a unified treatment for a general class of nonlinear programming problems regardless of their convexity and smoothness level. In particular, we show that the accelerated gradient and level methods, both originally designed for solving convex optimization problems only, can be used for solving both convex and nonconvex problems uniformly. In a similar vein, we show that some well-studied techniques for nonlinear programming, e.g., Quasi-Newton iteration, can be embedded into optimal convex optimization algorithms to possibly further enhance their numerical performance. Our theoretical and algorithmic developments are complemented by some promising numerical results obtained for solving a few important nonconvex and nonlinear data analysis problems in the literature.
Similar content being viewed by others
Notes
This complexity bound was also derived for the gradient descent method as a homework assignment given by the second author in Spring 2014, later summarized by one of the class participants in [30]. However this development requires the problem to be unconstrained and the parameters H and \(\nu \) be a given priori.
References
Asmussen, S., Glynn, P.W.: Stochastic Simulation: Algorithm and Analysis. Springer, New York (2000)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)
Becker, Stephen, Fadili, Jalal M.: A quasi-newton proximal splitting method. Adv. Neural Inf. Process. Syst. 25, 2618–2626 (2012)
Ben-Tal, A., Nemirovski, A.S.: Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Program. 102, 407–456 (2005)
Byrd, R.H., Nocedal, J., Schnabel, R.B.: Representations of quasi-newton matrices and their use in limited memory methods. Math. Program. 63(4), 129–156 (1994)
Cartis, C., Gould, N.I.M., Toint, PhL: On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization. SIAM J. Optim. 20(6), 2833–2852 (2010)
Chen, Y., Lan, G., Ouyang, Y., Zhang, W.: Fast bundle-level type methods for unconstrained and ball-constrained convex optimization. Manuscript, University of Florida, Gainesville, FL 32611, USA, December 2014. http://www.optimization-online.org/
Fan, J., Li, R.: Variable selection via nonconcave penalized likelihood and its oracle properties. J. Am. Stat. Assoc. 96, 13481360 (2001)
Fu, M.: Optimization for simulation: theory vs. practice. INFORMS J. Comput. 14, 192–215 (2002)
Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. SIAM J. Optim. 23, 2061–2089 (2013)
Ghadimi, S., Lan, G.: Accelerated gradient methods for nonconvex nonlinear and stochastic optimization. Math. Program. (2015). https://doi.org/10.1007/s10107-015-0871-8
Ghadimi, S., Lan, G., Zhang, H.: Mini-batch stochastic approximation methods for constrained nonconvex stochastic programming. Math. Program. (2014). https://doi.org/10.1007/s10107-014-0846-1
Hager, W.W., Zhang, H.: Projection on a polyhedron that exploits sparsity. Manuscript, University of Florida and Louisiana State University, Gainesville, FL 32611, USA and Baton Rouge, LA (June 2015)
Lan, G.: An optimal method for stochastic composite optimization. Math. Program. 133(1), 365–397 (2012)
Lan, G.: Bundle-level type methods uniformly optimal for smooth and non-smooth convex optimization. Math. Program. 149(1), 145 (2015)
Lan, G.: The complexity of large-scale convex programming under a linear optimization oracle. Manuscript, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, USA (June 2013). http://www.optimization-online.org
Law, A.M.: Simulation Modeling and Analysis. McGraw Hill, New York (2007)
Lemaréchal, C., Nemirovski, A.S., Nesterov, Y.E.: New variants of bundle methods. Math. Program. 69, 111–148 (1995)
Mairal, J., Bach, F., Ponce, J., Sapiro, G.: Online dictionary learning for sparse coding. In: ICML, pp. 689–696 (2009)
Mason, L., Baxter, J., Bartlett, P., Frean, M.: Boosting algorithms as gradient descent in function space. In: Proceedings of the NIPS, vol. 12, pp. 512–518 (1999)
Nemirovski, A.S., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. Wiley, XV, New York (1983)
Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence \(O(1/k^2)\). Dokl. Acad. Nauk SSSR 269, 543–547 (1983)
Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Boston (2004)
Nesterov, Y.E.: Gradient methods for minimizing composite objective functions. Math. Program. Ser. B 140, 125–161 (2013)
Nesterov, Y.E.: Universal gradient methods for convex optimization problems. Math.Program. Ser. A (2014). https://doi.org/10.1007/s10107-014-0790-0
Nocedal, J.: Updating quasi-newton matrices with limited storage. Math. Comput. 35(151), 773–782 (1980)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999)
Devolder, O., Glineur, F., Nesterov, Y.E.: First-order methods of smooth convex optimization with inexact oracle. CORE, Université catholique de Louvain, Louvain-la-Neuve, Belgium, Manuscript (December 2010)
Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. University of Washington, Seattle, Manuscript (May 2008)
Yashtini, M.: On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients. Optim. Lett. (2015). https://doi.org/10.1007/s11590-015-0936-x
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was partially supported by NSF Grants CMMI-1254446, CMMI-1537414, DMS-1319050, DMS-1522654, DMS-1819161 and ONR Grant N00014-13-1-0036. This paper was first released on Ar**v in August, 2015 (ar**v:1508.07384).
Rights and permissions
About this article
Cite this article
Ghadimi, S., Lan, G. & Zhang, H. Generalized Uniformly Optimal Methods for Nonlinear Programming. J Sci Comput 79, 1854–1881 (2019). https://doi.org/10.1007/s10915-019-00915-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-019-00915-4
Keywords
- Nonconvex optimization
- Uniformly optimal methods
- Parameter free methods
- Quasi-Newton methods
- Accelerated gradient methods
- Accelerated level methods