Speaker: |
Arkadi Nemirovski |

Faculty of Industrial Engineering and Management, Technion - Israel Institute of Technology |

**Title: ** Simple Optimization Methods for Extremely Large-Scale Convex Problems

Abstract

Presentation Slides

Paper

When solving extremely large-scale problems (with design dimension *n* like tens/hundreds of thousands), one is enforced to use methods with linear in *n* arithmetic cost of a step --- otherwise the very first iteration will never be finished. This requirement rules out all advanced polynomial time methods (for these methods, the arithmetic cost of a step is in-between *O(n^2)* and *O(n^3))* and, as far as nonsmooth/constrained problems are concerned, leaves us with the only choice - simple black-box-oriented subgradient-type techniques.

A bad news about black-box-oriented techniques is that they are unable to solve * large-scale problems* to high accuracy (for small ε, the arithmetic cost of /ε -solution cannot be less than *O(n^2\ln(1/ε))*, and for all known methods it is at least *O(n^4\ln(1/ε)))*. A good news is that there are cases when * low accuracy solutions can be obtained in nearly dimension-independent number of steps*, like O(1/ε), and that the corresponding methods are ``cheap'' (the arithmetic cost of a step, modulo the effort to evaluate the objective at a current iterate, is just O(n)).

In the talk, we

- Overview theoretical limits of performance of black-box-oriented methods,
- Present a new ``cheap''
*Bundle-Mirror*method for minimizing Lipschitz continuous convex functions over ``simple solids''*X*and demonstrate that with this method, an ε -solution can be obtained in a (nearly) dimension-independent number of steps, provided that X possesses ``favourable geometry'' (e.g., is an Euclidean ball, or a simplex, or the spectahedron {*X*belong to*R^(m x m): X=X^T >= 0, Tr(X)=1*}, and discuss the issue of theoretical optimality of the Bundle-Mirror algorithm, - Illustrate the practical potential of simple optimization methods by a numerical example (Image Reconstruction in Positron Emission Tomography).