Optimization Online


A predictor-corrector path-following algorithm for dual-degenerate parametric optimization problems

Vyacheslav Kungurtsev(vyacheslav.kungurtsev***at***fel.cvut.cz)
Johannes Jäschke(jaschke***at***ntnu.no)

Abstract: Most path-following algorithms for tracing a solution path of a parametric nonlinear optimization problem are only certifiably convergent under strong regularity assumptions about the problem functions, in particular, the linear independence of the constraint gradients at the solutions, which implies a unique multiplier solution for every nonlinear program. In this paper we propose and prove convergence results for a procedure designed to solve problems satisfying a weaker set of conditions, allowing for non-unique (but bounded) multipliers, applying known sensitivity results for this class of problems. Each iteration along the path consists of three parts: (1) a Newton corrector step for the primal and dual variables, this is obtained by solving a linear system of equations. (2) a tangential predictor step for the primal and dual variables, which is found as the solution of a quadratic programming problem, and (3) a jump step for the dual variables, which is found as the solution of a linear programming problem. We present a convergence proof, and demonstrate the successful solution tracking of the algorithm numerically on a couple of illustrative examples.

Keywords: Parametric optimization, Predictor-corrector path-following, Dual-degeneracy, Optimal solution sensitivity

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report, Norwegian University of Science and Technology, March 2016

Download: [PDF]

Entry Submitted: 03/30/2016
Entry Accepted: 03/30/2016
Entry Last Modified: 03/30/2016

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