Some Algorithms for Large-Scale Linear and Convex Minimization in Relative Scale
No Access Until
Permanent Link(s)
Collections
Other Titles
Author(s)
Abstract
This thesis is concerned with the study of algorithms for approximately
solving large-scale linear and nonsmooth convex minimization problems
within a prescribed relative error
Chapter 1 contains a brief account of the relevant part of complexity theory for convex optimization problems. This is done in order to be able to better communicate the proper setting of our work within the current literature. We finish with concise synopses of the following chapters.
In Chapter 2 we study the general problem of unconstrained convex minimization in relative scale. Algorithms of this type are hard to find in the literature and are known perhaps only for a narrow class of specialized transportation problems. It was recently suggested by Nesterov \cite{Nesterov:2003:Unconstr_conv_min_in_rel_scale},\cite{Nesterov:2004:Rounding} that this problem can be efficiently treated via a conic reformulation and by utilizing the information gained from the computation of a pair of John ellipsoids for the subdifferential of the objective function evaluated at the origin. Our main contribution is the improvement of the theoretical performance of the algorithms in the cited papers by incorporating a simple bisection idea. We also show that it is possible to design potentially more practical ``nonrestarting" versions of these methods at no or only negligible cost in their theoretical guarantees.
In Chapter 3 we consider the geometric problem of finding
the intersection of a line and a centrally symmetric convex body