On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
Mathematical ProgrammingPublished 28 April 2005
Andreas Wächter, Lorenz T. Biegler
Citations9,439
SJR quartileQ1
SJR score1.73
SNIP2.20
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A comprehensive description of the primal-dual interior-point algorithm with a filter line-search method for nonlinear programming is provided, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix.
Abstract
We present a primal-dual interior-point algorithm with a filter line-search method for nonlinear programming. Local and global convergence properties of this method were analyzed in previous work. Here we provide a comprehensive description of the algorithm, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix. Heuristics are also considered that allow faster performance. This method has been implemented in the IPOPT code, which we demonstrate in a detailed numerical study based on 954 problems from the CUTEr test set. An evaluation is made of several line-search options, and a comparison is provided with two state-of-the-art interior-point codes for nonlinear programming.
Keywords
Computer ScienceMathematics
Cambridge University Press eBooksNumerical optimization
14,107 Citations2021W. John Braun, Duncan J. Murdoch
Numerical Optimization
9,247 Citations1999Jorge Nocedal, Stephen J. Wright
Practical Methods of Optimization
6,403 Citations2000R. Ian Fletcher
Mathematical ProgrammingBenchmarking optimization software with performance profiles
4,354 Citations2002Elizabeth D. Dolan, Jorge J. Morè
It is shown that performance profiles combine the best features of other tools for performance evaluation to create a single tool for benchmarking and comparing optimization software.
Society for Industrial and Applied Mathematics eBooksTrust Region Methods
2,901 Citations2000Andrew R. Conn, Nicholas I. M. Gould +1 more
This chapter discusses Trust-Region Mewthods for General Constained Optimization and Systems of Nonlinear Equations and Nonlinear Fitting, and some of the methods used in this chapter dealt with these systems.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Nonlinear programming: sequential unconstrained minimization techniques
2,272 Citations1968Anthony V. Fiacco, Garth P. McCormick
SIAM Journal on OptimizationAn Interior Point Algorithm for Large-Scale Nonlinear Programming
1,693 Citations1999Richard H. Byrd, Mary E. Hribar +1 more
The design and implementation of a new algorithm for solving large nonlinear programming problems follows a barrier approach that employs sequential quadratic programming and trust regions to solve the subproblems occurring in the iteration.
Mathematical ProgrammingA trust region method based on interior point techniques for nonlinear programming
1,648 Citations2000Richard H. Byrd, Jean Charles Gilbert +1 more
This paper focuses on the primal version of the new algorithm, an algorithm for minimizing a nonlinear function subject to nonlinear inequality constraints, which applies sequential quadratic programming techniques to a sequence of barrier problems.
Mathematical ProgrammingAn interior algorithm for nonlinear optimization that combines line search and trust region steps
1,059 Citations2005Richard A. Waltz, José Luis Morales +2 more
An interior-point method for nonlinear programming that enjoys the flexibility of switching between a line search method that computes steps by factoring the primal-dual equations and a trust region method that uses a conjugate gradient iteration.
Mathematical ProgrammingNonlinear programming without a penalty function
859 Citations2002R. Fletcher, Sven Leyffer
The aim of the present work is to promote global convergence without the need to use a penalty function, so a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function.
SIAM ReviewInterior Methods for Nonlinear Optimization
677 Citations2002Anders Forsgren, Philip E. Gill +1 more
A condensed, selective look at classical material and recent research about interior methods for nonlinearly constrained optimization shows how their influence has transformed both the theory and practice of constrained optimization.
ACM Transactions on Mathematical SoftwareCUTEr and SifDec
572 Citations2003Nicholas I. M. Gould, Dominique Orban +1 more
A new version of CUTE, now known as CUTEr, is presented, which includes reorganisation of the environment to allow simultaneous multi-platform installation, new tools for, and interfaces to, optimization packages, and a considerably simplified and entirely automated installation procedure for unix systems.
Computational Optimization and ApplicationsAn Interior-Point Algorithm for Nonconvex Nonlinear Programming
525 Citations1999Robert J. Vanderbei, David F. Shanno
Numerical comparisons with MINOS and LANCELOT show that the interior-point algorithm for nonconvex nonlinear programming is efficient, and has the promise of greatly reducing solution times on at least some classes of models.
Lancelot: A FORTRAN Package for Large-Scale Nonlinear Optimization (Release A)
482 Citations1992Andrew R. Conn, Nicholas I. M. Gould +1 more
This book, which is concerned with algorithms for solving large-scale non-linear optimization problems, is the only complete source of documentation for the software package Lancelot and will mainly be used as a manual in conjunction with the software Package Lancelot.
SIAM Journal on OptimizationLine Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence
395 Citations2005Andreas Wächter, Lorenz T. Biegler
Under mild assumptions it is shown that every limit point of the sequence of iterates generated by the algorithm is feasible, and that there exists at least one limit point that is a stationary point for the problem under consideration.
Journal of Optimization Theory and ApplicationsOn the formulation and theory of the Newton interior-point method for nonlinear programming
360 Citations1996Amr El-Bakry, R. A. Tapia +2 more
This work study in detail the formulation of the primal-dual interior-point method for linear programming and extends the formulation to general nonlinear programming, and proves that this algorithm can be implemented so that it is locally and Q-quadratically convergent under only the standard Newton method assumptions.
SIAM Journal on OptimizationOn the Global Convergence of a Filter--SQP Algorithm
322 Citations2002R. Fletcher, Sven Leyffer +1 more
A mechanism for proving global convergence in SQP--filter methods for nonlinear programming (NLP) is described, and the main point of interest is to demonstrate how convergence for NLP can be induced without forcing sufficient descent in a penalty-type merit function.
Mathematical programming studiesThe watchdog technique for forcing convergence in algorithms for constrained optimization
313 Citations1982Richard Chamberlain, M. J. D. Powell +2 more
The watchdog technique is described and discussed, and some global and Q-superlinear convergence properties are proved.
Springer series in computational mathematicsLancelot
285 Citations1992Andrew R. Conn, Nicholas I. M. Gould +1 more
SIAM Journal on OptimizationGlobal Convergence of a Trust-Region SQP-Filter Algorithm for General Nonlinear Programming
272 Citations2002R. Fletcher, Nicholas I. M. Gould +3 more
It is proved that, under reasonable conditions and for every possible choice of the starting point, the sequence of iterates has at least one first-order critical accumulation point.
Mathematical ProgrammingA globally convergent primal-dual interior-point filter method for nonlinear programming
208 Citations2004Michael Ulbrich, Stefan Ulbrich +1 more
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.
Computational Optimization and ApplicationsInterior-Point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions
112 Citations2002Hande Y. Benson, Robert J. Vanderbei +1 more
This paper analyzes possible ways to implement a filter-based approach in an interior-point algorithm and shows that such an approach is more efficient than using a merit function alone.
Optimization methods & softwareA globally convergent primal-dual interior point method for constrained optimization
99 Citations1998Hiroshi Yamashita
It is proved that the proposed primal-dual interior point method is globally convergent from an arbitrary initial point that strictly satisfies the bounds on the variables.
Mathematical ProgrammingFailure of global convergence for a class of interior point methods for nonlinear programming
98 Citations2000Andreas Wächter, Lorenz T. Biegler
It is shown that a class of interior point methods for general nonlinear programming, including some current methods, is not globally convergent, and those algorithms produce limit points that are neither feasible nor stationary points of some measure of the constraint violation, when applied to a well-posed problem.
SIAM Journal on OptimizationA Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties
94 Citations2003André L. Tits, Andreas Wächter +3 more
It is shown that the primal-dual interior-point framework allows for a simpler penalty parameter update rule than the one discussed and analyzed by the originators of the scheme in the context of first order methods of feasible direction.
Mathematical ProgrammingA primal-dual trust-region algorithm for non-convex nonlinear programming
81 Citations2000Andrew R. Conn, Nicholas I. M. Gould +2 more
A new primal-dual algorithm is proposed for the minimization of non-convex objective functions subject to general inequality and linear equality constraints and it is shown that convergence is proved to second-order critical points from arbitrary starting points.
SIAM Journal on OptimizationSuperlinear Convergence of Primal-Dual Interior Point Algorithms for Nonlinear Programming
67 Citations2001Nicholas I. M. Gould, Dominique Orban +2 more
It is shown that, asymptotically, for each value of the barrier parameter, solving a single primal-dual linear system is enough to produce an iterate that already matches the barrier subproblem accuracy requirements, and the asymPTotic rate of convergence of the resulting algorithm is Q-superlinear and may be chosen arbitrarily close to quadratic.
Mathematical ProgrammingA globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization
54 Citations2004Hiroshi Yamashita, Hiroshi Yabe +1 more
A primal-dual interior point method for solving large scale nonlinearly constrained optimization problems that uses second derivatives of functions for minimizing the barrier-penalty function instead of line search strategies is proposed.
Rice University's digital scholarship archive (Rice University)A Globally Convergent Primal-Dual Interior-Point Filter Method for Nonconvex Nonlinear Programming
41 Citations2000Michael Ulbrich, Stefan Ulbrich +1 more