Dual Convergence for Penalty Algorithms in Convex Programming

Felipe Alvarez, Miguel Carrasco, Thierry Champion

Research output: Contribution to journalArticlepeer-review

Abstract

Algorithms for convex programming, based on penalty methods, can be designed to have good primal convergence properties even without uniqueness of optimal solutions. Taking primal convergence for granted, in this paper we investigate the asymptotic behavior of an appropriate dual sequence obtained directly from primal iterates. First, under mild hypotheses, which include the standard Slater condition but neither strict complementarity nor second-order conditions, we show that this dual sequence is bounded and also, each cluster point belongs to the set of Karush-Kuhn-Tucker multipliers. Then we identify a general condition on the behavior of the generated primal objective values that ensures the full convergence of the dual sequence to a specific multiplier. This dual limit depends only on the particular penalty scheme used by the algorithm. Finally, we apply this approach to prove the first general dual convergence result of this kind for penalty-proximal algorithms in a nonlinear setting.

Original languageEnglish
Pages (from-to)388-407
Number of pages20
JournalJournal of Optimization Theory and Applications
Volume153
Issue number2
DOIs
StatePublished - May 2012

Bibliographical note

Funding Information:
Acknowledgements The first author was supported by the Institute on Complex Engineering Systems (ICM: P-05-004-F, CONICYT: FBO16) of Universidad de Chile. The second author was supported by the FONDECYT grant 11090328. The third author was partially supported by the CNRS UMI 2807 (CMM, Universidad de Chile).

Keywords

  • Convex programming
  • Dual problem
  • Penalty function

Fingerprint Dive into the research topics of 'Dual Convergence for Penalty Algorithms in Convex Programming'. Together they form a unique fingerprint.

Cite this