Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

Ergodic, primal convergen… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

Ergodic, primal convergence in dual subgradient schemes for convex programming, II: the case of inconsistent primal problems

Artikel i vetenskaplig tidskrift
Författare Magnus Önnheim
Emil Gustavsson
Ann-Brith Strömberg
Michael Patriksson
Torbjörn Larsson
Publicerad i Mathematical programming
Volym 163
Nummer/häfte 1
Sidor 57-84
ISSN 0025-5610
Publiceringsår 2017
Publicerad vid Institutionen för matematiska vetenskaper
Sidor 57-84
Språk en
Länkar dx.doi.org/10.1007/s10107-016-1055-...
Ämnesord inconsistent convex program, Lagrange dual, homogeneous Lagrangian function, subgradient algorithm, ergodic primal sequence
Ämneskategorier Optimeringslära, systemteori

Sammanfattning

Consider the utilization of a Lagrangian dual method which is convergent for consistent 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 ε-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.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?