Approximate Level Method
Abstract: In this paper we propose and analyze a variant of the level method , 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
Entry Submitted: 01/08/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|