  


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 matrixvector 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, 23) the problem of finding the intersection of a ray and a centrallysymmetric polytope represented as a convex hull of a collection of points, 4) centrallysymmetric 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 rankone objective and constraint matrices. We finish the discussion by describing applications to truss topology design and design of statistical experiments. Keywords: nonsmooth convex optimization, variablemetric subgradient method, linear programming (LP), centrally symmetric linear programming (CSLP), ellipsoidsqueezing method, sparse solution of underdetermined linear systems, iteratively reweighted least squares (IRLS), iteratively reweighted Euclidean projection (IREP), basis pursuit, $\ell_1$norm minimization, coptimal design, Elfving set, multiplicativeupdate method, Khachiyan's ellipsoidal rounding algorithm, FrankWolfe 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  