Optimization Online


On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods

Gabriel Haeser(ghaeser***at***ime.usp.br)
Oliver Hinder(ohinder***at***stanford.edu)
Yinyu Ye(yyye***at***stanford.edu)

Abstract: This paper analyzes sequences generated by infeasible interior point methods. In convex and non-convex settings, we prove that moving the primal feasibility at the same rate as complementarity will ensure that the Lagrange multiplier sequence will remain bounded, provided the limit point of the primal sequence has a Lagrange multiplier, without constraint qualification assumptions. We also show that maximal complementarity holds, which guarantees the algorithm finds a strictly complementary solution, if one exists. Alternatively, in the convex case, if the primal feasibility is reduced too fast and the set of Lagrange multipliers is unbounded, then the Lagrange multiplier sequence generated will be unbounded. Conversely, if the primal feasibility is reduced too slowly, the algorithm will find a minimally complementary solution. We also demonstrate that the dual variables of the interior point solver IPOPT become unnecessarily large on Netlib problems, and we attribute this to the solver reducing the constraint violation too quickly.

Keywords: Interior point methods, Lagrange multipliers, Complementarity, Nonlinear Optimization, Convex optimization

Category 1: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 07/24/2017
Entry Accepted: 07/24/2017
Entry Last Modified: 07/24/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society