Simultaneously solving seven optimization problems in relative scale

Peter Richtarik

Research output: Working paperDiscussion paper

Abstract / Description of output

In this paper 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 $\ell_1$-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.
Original languageEnglish
Publication statusUnpublished - 2009


Dive into the research topics of 'Simultaneously solving seven optimization problems in relative scale'. Together they form a unique fingerprint.

Cite this