Seminar Details
2007-10-16 (14.00) : "An efficient algorithm for large-scale linear and convex optimization in relative scale"
At Euler building
Organized by Mathematical Engineering
Speaker :
Peter RICHTARIK
( Cornell University
)
Abstract :
We propose two variants of a single efficient O(1/epsilon) algorithm simultaneously solving a
number of related optimization problems in relative scale:
1 )Find the intersection of a line and a centrally symmetric convex body Q given as the convex hull of a collection of points.
Interpretation: Our method produces a sequence of ellipsoids inscribed in Q, and ``converging" towards the
intersection points and as such can be viewed as a modification of the ellipsoid rounding algorithm of Khachiyan.
2) Maximize a linear function over the polytope polar to Q.
Interpretation: A "variant" of the ellipsoid method of Nemirovski-Yudin-Shor.
3) Find the minimum l1 norm solution of a full rank underdetermined linear system.
Interpretation: An Iteratively Reweighted Least Squares (IRLS) method.
4) Minimize the maximum of absolute values of linear functions on a hyperplane.
Interpretation: Shor's subgradient method with space dilation.
5)Minimize a (special) smooth convex function on the unit simplex.
Interpretation: A version of the Frank-Wolfe method with specialized line search.
From among the many possible applications we outline those to truss topology design and optimal design of
statistical experiments.