Efficiency of Proximal Bundle Methods

被引：0
作者：
K. C. Kiwiel
机构：
[1] Systems Research Institute,
来源：
Journal of Optimization Theory and Applications | 2000年 / 104卷
关键词：
nondifferentiable optimization; convex programming; proximal bundle methods; efficiency; complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We give efficiency estimates for proximal bundle methods for finding f*≔minXf, where f and X are convex. We show that, for any accuracy ∈<0, these methods find a point xk∈X such that f(xk)−f*≤∈ after at most k=O(1/∈3) objective and subgradient evaluations.
引用
收藏
页码：589 / 603
页数：14
相关论文
共 50 条
[31]   An inexact bundle variant suited to column generation [J].
K. C. Kiwiel ;
C. Lemaréchal .
Mathematical Programming, 2009, 118 :177-206
[32]   An inexact bundle variant suited to column generation [J].
Kiwiel, K. C. ;
Lemarechal, C. .
MATHEMATICAL PROGRAMMING, 2009, 118 (01) :177-206
[33]   Accelerated Proximal Envelopes: Application to Componentwise Methods [J].
Anikin, A. S. ;
Matyukhin, V. V. ;
Pasechnyuk, D. A. .
COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS, 2022, 62 (02) :336-345
[34]   ON THE CONVERGENCE RATE OF ENTROPIC PROXIMAL OPTIMIZATION METHODS [J].
IUSEM, AN ;
TEBOULLE, M .
MATEMATICA APLICADA E COMPUTACIONAL, 1993, 12 (02) :153-168
[35]   Revenue and efficiency ranking in large multi-unit and bundle auctions [J].
Chakraborty, Indranil ;
Shyamalkumar, Nariankadu D. .
JOURNAL OF MATHEMATICAL ECONOMICS, 2014, 50 :12-21
[36]   AUGMENTED LAGRANGIAN DUAL FOR NONCONVEX MINIMAX FRACTIONAL PROGRAMS AND PROXIMAL BUNDLE ALGORITHMS FOR ITS RESOLUTION [J].
Boualam, Hssaine ;
Roubi, Ahmed .
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2023, 19 (05) :3610-3636
[37]   Inexact proximal point algorithms and descent methods in optimization [J].
Humes, C ;
Silva, PJS .
OPTIMIZATION AND ENGINEERING, 2005, 6 (02) :257-271
[38]   Inexact Proximal Point Algorithms and Descent Methods in Optimization [J].
Carlos Humes ;
Paulo J. S. Silva .
Optimization and Engineering, 2005, 6 :257-271
[39]   AN ACCELERATED HYBRID PROXIMAL EXTRAGRADIENT METHOD FOR CONVEX OPTIMIZATION AND ITS IMPLICATIONS TO SECOND-ORDER METHODS [J].
Monteiro, Renato D. C. ;
Svaiter, B. F. .
SIAM JOURNAL ON OPTIMIZATION, 2013, 23 (02) :1092-1125
[40]   On the Convergence of Proximal Gradient Methods for Convex Simple Bilevel Optimization [J].
Latafat, Puya ;
Themelis, Andreas ;
Villa, Silvia ;
Patrinos, Panagiotis .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2025, 204 (03)
12345