eCommons@Cornell >
Cornell University Graduate School >
Cornell Theses and Dissertations >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/8155
Title:  Some Algorithms for LargeScale Linear and Convex Minimization in Relative Scale 
Authors:  Richtarik, Peter 
Keywords:  largescale optimization linear programming convex minimization firstorder methods nonsmooth optimization relative scale truss topology design coptimality optimal design FrankWolfe algorithm ellipsoid method iteratively reweighted least squares O(1/\epsilon) convergence 
Issue Date:  3Aug2007 
Abstract:  This thesis is concerned with the study of algorithms for approximately
solving largescale linear and nonsmooth convex minimization problems
within a prescribed relative error $\delta$ of the optimum. The methods we
propose converge in $O(1/\delta^2)$ or $O(1/\delta)$ iterations of a
firstorder type. While the theoretical lower iteration bound for
approximately solving (in the absolute sense) nonsmooth convex
minimization problems in the blackbox computational model of complexity
is $O(1/\epsilon^2)$, the algorithms developed in this thesis are able to
perform better by effectively utilizing the information about the
\emph{structure} of the problems.
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
$Q$ given as the convex hull of a collection of points. Our
algorithms produce a sequence of ellipsoids inscribed in $Q$,
``converging" towards the intersection points. It turns out that in
doing so we simultaneously solve a number of closely related
problems such as the problem of finding the minimum $\ell_1$ norm
solution of a full rank underdetermined linear system, minimizing
the maximum of absolute values of linear functions, or linear
optimization over the polytope polar to $Q$. We finish the
discussion by describing applications to truss topology design and
optimal design of statistical experiments. 
Description:  A dissertation written under the guidance of Michael J. Todd 
URI:  http://hdl.handle.net/1813/8155 
Appears in Collections:  Cornell Theses and Dissertations

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
