Efficiency of proximal bundle methods

被引：29

作者：

Kiwiel, KC ^{[1
]}

机构：

[1] Polish Acad Sci, Syst Res Inst, PL-01447 Warsaw, Poland

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 2000年 / 104卷 / 03期

基金：

瑞典研究理事会;

关键词：

nondifferentiable optimization; convex programming; proximal bundle methods; efficiency; complexity;

D O I：

10.1023/A:1004689609425

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We give efficiency estimates for proximal bundle methods for finding f* := min(x)f, where f and X are convex. We show that, for any accuracy epsilon>0, these methods find a point x(k) is an element of X such that f(x(k)) - f* less than or equal to epsilon after at most k = O (1/epsilon(3)) objective and subgradient evaluations.

引用

页码：589 / 603

页数：15

共 18 条

[1] CONVERGENCE OF SOME ALGORITHMS FOR CONVEX MINIMIZATION [J].

CORREA, R ;

LEMARECHAL, C .

MATHEMATICAL PROGRAMMING, 1993, 62 (02) :261-275

[2]

Frangioni A., 1997, THESIS U PISA PISA

[3]

Hiriart-Urruty J. B., 1996, CONVEX ANAL MINIMIZA, V305

[4] A CHOLESKY DUAL METHOD FOR PROXIMAL PIECEWISE-LINEAR PROGRAMMING [J].

KIWIEL, KC .

NUMERISCHE MATHEMATIK, 1994, 68 (03) :325-340

[5] Proximal decomposition via alternating linearization [J].

Kiwiel, KC ;

Rosa, CH ;

Ruszczynski, A .

SIAM JOURNAL ON OPTIMIZATION, 1999, 9 (03) :668-689

[6] PROXIMAL LEVEL BUNDLE METHODS FOR CONVEX NONDIFFERENTIABLE OPTIMIZATION, SADDLE-POINT PROBLEMS AND VARIATIONAL-INEQUALITIES [J].

KIWIEL, KC .

MATHEMATICAL PROGRAMMING, 1995, 69 (01) :89-109

[7] The efficiency of ballstep subgradient level methods for convex optimization [J].

Kiwiel, KC ;

Larsson, T ;

Lindberg, PO .

MATHEMATICS OF OPERATIONS RESEARCH, 1999, 24 (01) :237-254

[8] APPROXIMATIONS IN PROXIMAL BUNDLE METHODS AND DECOMPOSITION OF CONVEX-PROGRAMS [J].

KIWIEL, KC .

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1995, 84 (03) :529-548

[9] Efficiency of the analytic center cutting plane method for convex minimization [J].

Kiwiel, KC .

SIAM JOURNAL ON OPTIMIZATION, 1997, 7 (02) :336-346

[10] The efficiency of subgradient projection methods for convex optimization .1. General level methods [J].

Kiwiel, KC .

SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 1996, 34 (02) :660-676

← 1 2 →