Seminar 27th May 2010 4 p.m. University of Southampton, Building 2, Room 3041
CORMSIS Seminar: Simultaneously solving seven optimization problems in relative scale
Dr Peter Richtárik
University of Edinburgh
- Web page
- http://www.cormsis.soton.ac.uk/seminar-details.php?SeminarID=2182
- Categories
- Optimisation
- Submitter
- Petrina Butler
Dr Peter Richtárik from the University of Edinburgh
(a guest of Houduo Qi)
Simultaneously solving seven optimization problems in relative scale
Abstract:
We develop and analyze an efficient algorithm which solves seven related optimization problems simultaneously, in relative scale. Each iteration of our method is very cheap, with main work spent on matrix-vector multiplication. We prove that if a certain sequence generated by the algorithm remains bounded, then the method must terminate in O (1/delta) iterations, producing delta-approximate solutions to all seven problems, where delta is the prescribed relative error.
The seven problems are 1) a specific sublinear minimization program with a single homogeneous linear constraint, 2-3) the problem of finding the intersection of a ray and a centrally-symmetric polytope represented as a convex hull of a collection of points, 4) centrally-symmetric linear programming, 5) the problem of finding the least l1-norm solution of an underdetermined linear system (basis pursuit), 6) a certain smooth convex minimization problem on the unit simplex and, finally, 7) a semidefinite program with rank-one objective and constraint matrices.
We finish the discussion by describing applications to truss topology design and design of statistical experiments.
for information contact: Katarzyna (Kasia) Bijak
CORMSIS Facilitator
School of Management / School of Mathematics
University of Southampton