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.
Article
View Simultaneously solving seven optimization problems in relative scale