An optimal subgradient algorithm for large-scale bound-constrained convex optimization

作者：Ahookhosh Masoud^*; Neumaier Arnold

来源：Mathematical Methods of Operations Research, 2017, 86(1): 123-147.

DOI：10.1007/s00186-017-0585-1

• Bound-constrained convex optimization
• Nonsmooth optimization
• First-order black-box oracle
• Subgradient methods
• Optimal complexity
• High-dimensional data

This paper shows that the optimal subgradient algorithm (OSGA)-which uses first-order information to solve convex optimization problems with optimal complexity-can be used to efficiently solve arbitrary bound-constrained convex optimization problems. This is done by constructing an explicit method as well as an inexact scheme for solving the bound-constrained rational subproblem required by OSGA. This leads to an efficient implementation of OSGA on large-scale problems in applications arising from signal and image processing, machine learning and statistics. Numerical experiments demonstrate the promising performance of OSGA on such problems. A software package implementing OSGA for bound-constrained convex problems is available.

• 出版日期2017-8