nonsmooth convex optimization – Optimization Online

Bundle methods in the XXIst century: A bird’s-eye view

Published: 2013/10/21

Convex Optimization bundle method, inexact oracles, nonsmooth convex optimization

Bundle methods are often the algorithms of choice for nonsmooth convex optimization, especially if accuracy in the solution and reliability are a concern. We review several algorithms based on the bundle methodology that have been developed recently and that, unlike their forerunner variants, have the ability to provide exact solutions even if most of the … Read more

Simultaneously solving seven optimization problems in relative scale

Published: 2009/01/08

Peter Richtarik

Linear Programming, Nonsmooth Optimization, Statistics $\ell_1hBcnorm minimization, basis pursuit, c-optimal design, centrally symmetric linear programming (cslp), elfving set, ellipsoid-squeezing method, frank-wolfe, iteratively reweighted euclidean projection (irep), iteratively reweighted least squares (irls), khachiyan's ellipsoidal rounding algorithm, linear programming, multiplicative-update method, nonsmooth convex optimization, sparse solution of underdetermined linear systems, variable-metric subgradient method

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)$ … Read more