Approximate Level Method

Peter Richtarik(peter.richtarikuclouvain.be)

Abstract: In this paper we propose and analyze a variant of the level method [4], which is an algorithm for minimizing nonsmooth convex functions. The main work per iteration is spent on 1) minimizing a piecewise-linear model of the objective function and on 2) projecting onto the intersection of the feasible region and a polyhedron arising as a level set of the model. We show that by replacing exact computations in both cases by approximate computations, in relative scale, the theoretical iteration complexity increases only by the factor of four. This means that while spending less work on the subproblems, we are able to retain the good theoretical properties of the level method.

Keywords: level method, approximate projections in relative scale, nonsmoth convex optimization, sensitivity analysis, large scale optimization.

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: CORE DISCUSSION PAPER 2008/83

Download: [PDF]

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

Modify/Update this entry