liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On the convergence of conditional e-subgradient methods for convex programs and convex-concave saddle-point problems
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .ORCID iD: 0000-0003-2094-7376
2003 (English)In: European Journal of Operational Research, ISSN 0377-2217, Vol. 151, no 3, 461-473 p.Article in journal (Refereed) Published
Abstract [en]

The paper provides two contributions. First, we present new convergence results for conditional e-subgradient algorithms for general convex programs. The results obtained here extend the classical ones by Polyak [Sov. Math. Doklady 8 (1967) 593, USSR Comput. Math. Math. Phys. 9 (1969) 14, Introduction to Optimization, Optimization Software, New York, 1987] as well as the recent ones in [Math. Program. 62 (1993) 261, Eur. J. Oper. Res. 88 (1996) 382, Math. Program. 81 (1998) 23] to a broader framework. Secondly, we establish the application of this technique to solve non-strictly convex-concave saddle point problems, such as primal-dual formulations of linear programs. Contrary to several previous solution algorithms for such problems, a saddle-point is generated by a very simple scheme in which one component is constructed by means of a conditional e-subgradient algorithm, while the other is constructed by means of a weighted average of the (inexact) subproblem solutions generated within the subgradient method. The convergence result extends those of [Minimization Methods for Non-Differentiable Functions, Springer-Verlag, Berlin, 1985, Oper. Res. Lett. 19 (1996) 105, Math. Program. 86 (1999) 283] for Lagrangian saddle-point problems in linear and convex programming, and of [Int. J. Numer. Meth. Eng. 40 (1997) 1295] for a linear-quadratic saddle-point problem arising in topology optimization in contact mechanics.

Place, publisher, year, edition, pages
2003. Vol. 151, no 3, 461-473 p.
National Category
URN: urn:nbn:se:liu:diva-22333DOI: 10.1016/S0377-2217(02)00629-XLocal ID: 1534OAI: diva2:242646
Available from: 2009-10-07 Created: 2009-10-07 Last updated: 2013-08-30

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Larsson, Torbjörn
By organisation
The Institute of TechnologyOptimization
In the same journal
European Journal of Operational Research

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 397 hits
ReferencesLink to record
Permanent link

Direct link