A Globally Convergent Primal-Dual Interior-Point Filter Method for Nonlinear Programming


Michael Ulbrich
Technische Universität München
Zentrum Mathematik
Lehrstuhl für Angewandte Mathematik und Mathematische Statistik

Stefan Ulbrich
Technische Universität München
Zentrum Mathematik
Lehrstuhl für Angewandte Mathematik und Mathematische Statistik

Luís N. Vicente
Departamento de Matemática
Universidade de Coimbra, Portugal

April 2000, revised February 2002

Technical Report 00-12
Department of Computational and Applied Mathematics
Rice University

as PDF file (280k).


Abstract

In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters.
The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one resulting from feasibility and centrality, and associated with the normal step; the other resulting from optimality (complementarity and duality), and related with the tangential step.
Global convergence to first-order critical points is proved for the new primal-dual interior-point filter algorithm.

Keywords

Interior-point methods, primal-dual, filter, global convergence

1991 Mathematics Subject Classification

65K05, 90C06, 90C29, 90C30