A proximal bundle method with approximate subgradient linearizations

被引：69

作者：

Kiwiel, KC ^{[1
]}

机构：

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

来源：

SIAM JOURNAL ON OPTIMIZATION | 2006年 / 16卷 / 04期

关键词：

nondifferentiable optimization; convex programming; proximal bundle methods; approximate subgradients; Lagrangian relaxation;

D O I：

10.1137/040603929

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give a proximal bundle method for minimizing a convex function f over a closed convex set. It only requires evaluating f and its subgradients with an accuracy epsilon > 0, which is fixed but possibly unknown. It asymptotically finds points that are epsilon-optimal. When applied to Lagrangian relaxation, it allows for epsilon-accurate solutions of Lagrangian subproblems and finds epsilon-optimal solutions of convex programs.

引用

页码：1007 / 1023

页数：17

共 18 条

[1]

Bertsekas D., 1999, NONLINEAR PROGRAMMIN

[2] Dual applications of proximal bundle methods, including Lagrangian relaxation of nonconvex problems [J].

Feltenmark, S ;

Kiwiel, KC .

SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (03) :697-721

[3] A spectral bundle method for semidefinite programming [J].

Helmberg, C ;

Rendl, F .

SIAM JOURNAL ON OPTIMIZATION, 2000, 10 (03) :673-696

[4] A spectral bundle method with bounds [J].

Helmberg, C ;

Kiwiel, KC .

MATHEMATICAL PROGRAMMING, 2002, 93 (02) :173-194

[5] A proximal bundle method based on approximate subgradients [J].

Hintermüller, M .

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 20 (03) :245-266

[6]

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

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

KIWIEL, KC .

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

[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] FINDING NORMAL SOLUTIONS IN PIECEWISE-LINEAR PROGRAMMING [J].

KIWIEL, KC .

APPLIED MATHEMATICS AND OPTIMIZATION, 1995, 32 (03) :235-254

[10] PROXIMITY CONTROL IN BUNDLE METHODS FOR CONVEX NONDIFFERENTIABLE MINIMIZATION [J].

KIWIEL, KC .

MATHEMATICAL PROGRAMMING, 1990, 46 (01) :105-122

← 1 2 →