Skip to Main content Skip to Navigation
Reports

The Efficiency of subgradient projection methods for convex nondifferentiable optimization

Krzysztof C. Kiwiel 1
1 PROMATH - Mathematical Programming
Inria Paris-Rocquencourt
Abstract : We study subgradient methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We show that they enjoy almost optimal efficiency estimates. We present several variants, establish their efficiency estimates and discuss possible implementations. In particular, their projection subproblems may be solved inexactly via relaxation methods, thus opening the way for parallel implementations. We discuss accelerations of relaxation methods based on simultaneous projections, surrogate constraints and conjugate and projected (conditional) subgradient techniques.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074827
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:30:41 PM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:35:51 PM

Identifiers

  • HAL Id : inria-00074827, version 1

Collections

Citation

Krzysztof C. Kiwiel. The Efficiency of subgradient projection methods for convex nondifferentiable optimization. [Research Report] RR-1845, INRIA. 1993. ⟨inria-00074827⟩

Share

Metrics

Record views

146

Files downloads

107