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, primal convergence in dual subgradient schemes for convex programming, II: the case of inconsistent primal problems
Chalmers, Sweden; University of Gothenburg, Sweden.
Chalmers, Sweden; University of Gothenburg, Sweden.
Chalmers, Sweden; University of Gothenburg, Sweden.
Chalmers, Sweden; University of Gothenburg, Sweden.
Show others and affiliations
2017 (English)In: Mathematical programming, ISSN 0025-5610, E-ISSN 1436-4646, Vol. 163, no 1-2, 57-84 p.Article in journal (Refereed) Published
Abstract [en]

Consider the utilization of a Lagrangian dual method which is convergent for consistent convex optimization problems. When it is used to solve an infeasible optimization problem, its inconsistency will then manifest itself through the divergence of the sequence of dual iterates. Will then the sequence of primal subproblem solutions still yield relevant information regarding the primal program? We answer this question in the affirmative for a convex program and an associated subgradient algorithm for its Lagrange dual. We show that the primal-dual pair of programs corresponding to an associated homogeneous dual function is in turn associated with a saddle-point problem, in which-in the inconsistent case-the primal part amounts to finding a solution in the primal space such that the Euclidean norm of the infeasibility in the relaxed constraints is minimized; the dual part amounts to identifying a feasible steepest ascent direction for the Lagrangian dual function. We present convergence results for a conditional epsilon-subgradient optimization algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence of the primal-dual sequence to the set of saddle-points of the associated homogeneous Lagrangian function; for linear programs, convergence to the subset in which the primal objective is at minimum is also achieved.

Place, publisher, year, edition, pages
SPRINGER HEIDELBERG , 2017. Vol. 163, no 1-2, 57-84 p.
Keyword [en]
Inconsistent convex program; Lagrange dual; Homogeneous Lagrangian function; Subgradient algorithm; Ergodic primal sequence
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-137082DOI: 10.1007/s10107-016-1055-xISI: 000399178500003OAI: oai:DiVA.org:liu-137082DiVA: diva2:1093282
Note

Funding Agencies|Swedish Natural Science Research Council (NFR); Swedish Energy Agency, Chalmers University of Technology, University of Gothenburg; Linkoping University

Available from: 2017-05-05 Created: 2017-05-05 Last updated: 2017-05-30

Open Access in DiVA

fulltext(796 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 796 kBChecksum SHA-512
a4fbfe99c6d069f5c24e89028044f4ab47cd148be79c658e003fe6c01f26e3e89ef9fe40e323c4fe9a3f80c060bc190db2134c3e7334f77390acbdfaadd84500
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Larsson, Torbjörn
By organisation
Optimization Faculty of Science & Engineering
In the same journal
Mathematical programming
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
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: 72 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