Optimization Online


A doubly stabilized bundle method for nonsmooth convex optimization

Welington Oliveira(wlo***at***impa.br)
Mikhail Solodov(solodov***at***impa.br)

Abstract: We propose a bundle method for minimizing nonsmooth convex functions that combines both the level and the proximal stabilizations. Most bundle algorithms use a cutting-plane model of the objective function to formulate a subproblem whose solution gives the next iterate. Proximal bundle methods employ the model in the objective function of the subproblem, while level methods put the model in the subproblem's constraints. The proposed algorithm defines new iterates by solving a subproblem that employs the model in both the objective function and in the constraints. One advantage when compared to the proximal approach is that the new variant is able to update the lower bound for the optimal value, thus providing an additional useful stopping test based on the optimality gap. Furthermore, the level set constraint gives a certain Lagrange multiplier, which is used to update the proximal parameter in a novel manner. We also show that in the case of inexact function and subgradient evaluations, no additional procedure needs to be performed by our variant to deal with inexactness (as opposed to the proximal bundle methods that require special modifications).Numerical experiments on almost seven hundred instances of different types of problems are presented (the model unit-commitment problem in the energy sector, two-stage stochastic linear programming, and some standard nonsmooth optimization test problems). Our experiments show that the doubly stabilized bundle method inherits useful features of the level and the proximal versions, and compares favourably to both of them.

Keywords: Nonsmooth Optimization, Proximal Bundle Method, Level Bundle Method

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 04/13/2013
Entry Accepted: 04/14/2013
Entry Last Modified: 04/13/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society