Optimization and Systems Theory Seminar

October 19, at 11.00, room 3721, Lindstedtsvägen 25, KTH:
Ann-Brith Strömberg,Chalmers, Sweden

Lagrangian optimization for inconsistent linear programs

When a Lagrangean dual method is used to solve an infeasible optimization problem, the inconsistency is manifested through the divergence of the dual iterates. Will then the primal sequence of subproblem solutions still yield relevant information about the primal solution? We answer this question in the affirmative for a linear program and an associated Lagrangian dual algorithm. We show that the primal-dual linear program can be 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 total amount of infeasibility in the relaxed constraints is minimized; the (homogeneous) dual part aims to identify a steepest feasible ascent direction. We present convergence results for a subgradient algorithm applied to the Lagrangian dual problem, and the construction of an ergodic sequence of primal subproblem solutions; this composite algorithm yields convergence to the subset of the set of saddle points at which the original objective function is minimized. The research behind this talk is joint work with Emil Gustavsson, Torbjörn Larsson, Michael Patriksson, and Magnus Önnheim.


Calendar of seminars Last update: October 11, 2012.