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

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.