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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Ergodic Convergence in Subgradient Optimization with Application to Simplicial Decomposition of Convex Programs
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0003-2094-7376
Linköping University, Department of Mathematics. Linköping University, The Institute of Technology.
Chalmers, Göteborg, Sweden.
2012 (English)In: Contemporary Mathematics, ISSN 0271-4132, E-ISSN 1098-3627, Vol. 568, 159-189 p.Article in journal (Refereed) Published
Abstract [en]

When non-smooth, convex minimization problems are solved by subgradient optimization methods, the subgradients used will in general not accumulate to subgradients that verify the optimality of a solution obtained in the limit. It is therefore not a straightforward task to monitor the progress of subgradient methods in terms of the approximate fulfilment of optimality conditions. Further, certain supplementary information, such as convergent estimates of Lagrange multipliers and convergent lower bounds on the optimal objective value, is not directly available in subgradient schemes. As a means of overcoming these weaknesses in subgradient methods, we introduced in our previous articles the computation of an ergoclic (averaged) sequence of subgradients. Specifically, we considered a non-smooth, convex program solved by a conditional subgradient optimization scheme with divergent series step lengths, and showed that the elements of the ergodic sequence of subgradients in the limit fulfil the optimality conditions at the optimal solution, to which the sequence of iterates converges. This result has three important implications. The first is the finite identification of active constraints at the solution obtained in the limit. The second is the establishment of the convergence of ergodic sequences of Lagrange multipliers; this result enables sensitivity analyses for solutions obtained by subgradient methods. The third is the convergence of a lower bounding procedure based on an ergodic sequence of affine underestimates of the objective function; this procedure also provides a proper termination criterion for subgradient optimization methods. This article gives first an overview of results and applications found in our previous articles pertaining to the generation of ergodic sequences of subgradients generated within a subgradient scheme. It then presents an application of these results to that of the first instance of a simplicial decomposition algorithm for convex and non-smooth optimization problems.

Place, publisher, year, edition, pages
American Mathematical Society , 2012. Vol. 568, 159-189 p.
Keyword [en]
Non-smooth minimization; conditional subgradient optimization; ergodic convergence; simplicial decomposition
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:liu:diva-87596DOI: 10.1090/conm/568/11282ISI: 000308514100011OAI: oai:DiVA.org:liu-87596DiVA: diva2:589530
Available from: 2013-01-18 Created: 2013-01-18 Last updated: 2017-12-06

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Larsson, TorbjörnPatriksson, Michael

Search in DiVA

By author/editor
Larsson, TorbjörnPatriksson, Michael
By organisation
Optimization The Institute of TechnologyDepartment of Mathematics
In the same journal
Contemporary Mathematics
Natural Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 125 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf