Simultaneously solving seven optimization problems in relative scale

Peter Richtarik (peter.richtarikuclouvain.be)

Abstract: 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.

Keywords: nonsmooth convex optimization, variable-metric subgradient method, linear programming (LP), centrally symmetric linear programming (CSLP), ellipsoid-squeezing method, sparse solution of underdetermined linear systems, iteratively reweighted least squares (IRLS), iteratively reweighted Euclidean projection (IREP), basis pursuit, $\ell_1$-norm minimization, c-optimal design, Elfving set, multiplicative-update method, Khachiyan's ellipsoidal rounding algorithm, Frank-Wolfe algorithm.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation:

Download: [PDF]

Entry Submitted: 01/08/2009
Entry Accepted: 01/08/2009
Entry Last Modified: 01/08/2009

Modify/Update this entry