A Proximal‐Projection Bundle Method for Lagrangian Relaxation, Including Semidefinite Programming

We give a proximal bundle method for minimizing a convex function $f$ over a convex set $C$. It requires evaluating $f$ and its subgradients with a fixed but possibly unknown accuracy $\epsilon>0$. Each iteration involves solving an unconstrained proximal subproblem and projecting a certain point...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on optimization 2006-01, Vol.17 (4), p.1015-1034
Main Author: Kiwiel, Krzysztof C.
Format: Article
Language:English
Subjects:
Accuracy
Eigenvalues
Eigenvectors
Methods
Semidefinite programming
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We give a proximal bundle method for minimizing a convex function $f$ over a convex set $C$. It requires evaluating $f$ and its subgradients with a fixed but possibly unknown accuracy $\epsilon>0$. Each iteration involves solving an unconstrained proximal subproblem and projecting a certain point onto $C$. The method asymptotically finds points that are $\epsilon$-optimal. In Lagrangian relaxation of convex programs, it allows for ε-accurate solutions of Lagrangian subproblems and finds ε-optimal primal solutions. For semidefinite programming problems, it extends the highly successful spectral bundle method to the case of inexact eigenvalue computations.
ISSN:1052-6234
1095-7189
DOI:10.1137/050639284