Superlinear convergence of primal-dual interior point algorithms for nonlinear programming

Nick Gould, Dominique. Orban, A. Sartenaer, Philippe Toint

Résultats de recherche: Contribution à un journal/une revueArticle

Résumé

The local convergence properties of a class of primal-dual interior point methods are analyzed. These methods are designed to minimize a nonlinear, nonconvex, objective function subject to linear equality constraints and general inequalities. They involve an inner iteration in which the log-barrier merit function is approximately minimized subject to satisfying the linear equality constraints, and an outer iteration that specifies both the decrease in the barrier parameter and the level of accuracy for the inner minimization. Under nondegeneracy assumptions, 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. The asymptotic rate of convergence of the resulting algorithm is Q-superlinear and may be chosen arbitrarily close to quadratic. Furthermore, this rate applies componentwise. These results hold in particular for the method described in [A. R. Conn, N. I. M. Gould, D. Orban, and P. L. Toint, Math. Program. Ser. B, 87 (2000), pp. 215-249] and indicate that the details of its inner minimization are irrelevant in the asymptotics, except for its accuracy requirements.
langueAnglais
Pages974-1002
Nombre de pages29
journalSIAM Journal on Optimization
Volume11
Numéro4
Les DOIs
étatPublié - 1 mars 2001

Empreinte digitale

Primal-dual Interior-point Algorithm
Superlinear Convergence
Nonlinear programming
Nonlinear Programming
Equality Constraints
Linear Constraints
Primal-dual Interior Point Method
Linear systems
Iteration
Barrier Function
Merit Function
Nondegeneracy
Primal-dual
Requirements
Local Properties
Local Convergence
Iterate
Convergence Properties
Rate of Convergence
Objective function

Citer ceci

@article{b5a970d131d04fb491f7a7c075042182,
title = "Superlinear convergence of primal-dual interior point algorithms for nonlinear programming",
abstract = "The local convergence properties of a class of primal-dual interior point methods are analyzed. These methods are designed to minimize a nonlinear, nonconvex, objective function subject to linear equality constraints and general inequalities. They involve an inner iteration in which the log-barrier merit function is approximately minimized subject to satisfying the linear equality constraints, and an outer iteration that specifies both the decrease in the barrier parameter and the level of accuracy for the inner minimization. Under nondegeneracy assumptions, 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. The asymptotic rate of convergence of the resulting algorithm is Q-superlinear and may be chosen arbitrarily close to quadratic. Furthermore, this rate applies componentwise. These results hold in particular for the method described in [A. R. Conn, N. I. M. Gould, D. Orban, and P. L. Toint, Math. Program. Ser. B, 87 (2000), pp. 215-249] and indicate that the details of its inner minimization are irrelevant in the asymptotics, except for its accuracy requirements.",
author = "Nick Gould and Dominique. Orban and A. Sartenaer and Philippe Toint",
note = "Copyright 2005 Elsevier Science B.V., Amsterdam. All rights reserved.",
year = "2001",
month = "3",
day = "1",
doi = "10.1137/S1052623400370515",
language = "English",
volume = "11",
pages = "974--1002",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics",
number = "4",

}

Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. / Gould, Nick; Orban, Dominique.; Sartenaer, A.; Toint, Philippe.

Dans: SIAM Journal on Optimization, Vol 11, Numéro 4, 01.03.2001, p. 974-1002.

Résultats de recherche: Contribution à un journal/une revueArticle

TY - JOUR

T1 - Superlinear convergence of primal-dual interior point algorithms for nonlinear programming

AU - Gould,Nick

AU - Orban,Dominique.

AU - Sartenaer,A.

AU - Toint,Philippe

N1 - Copyright 2005 Elsevier Science B.V., Amsterdam. All rights reserved.

PY - 2001/3/1

Y1 - 2001/3/1

N2 - The local convergence properties of a class of primal-dual interior point methods are analyzed. These methods are designed to minimize a nonlinear, nonconvex, objective function subject to linear equality constraints and general inequalities. They involve an inner iteration in which the log-barrier merit function is approximately minimized subject to satisfying the linear equality constraints, and an outer iteration that specifies both the decrease in the barrier parameter and the level of accuracy for the inner minimization. Under nondegeneracy assumptions, 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. The asymptotic rate of convergence of the resulting algorithm is Q-superlinear and may be chosen arbitrarily close to quadratic. Furthermore, this rate applies componentwise. These results hold in particular for the method described in [A. R. Conn, N. I. M. Gould, D. Orban, and P. L. Toint, Math. Program. Ser. B, 87 (2000), pp. 215-249] and indicate that the details of its inner minimization are irrelevant in the asymptotics, except for its accuracy requirements.

AB - The local convergence properties of a class of primal-dual interior point methods are analyzed. These methods are designed to minimize a nonlinear, nonconvex, objective function subject to linear equality constraints and general inequalities. They involve an inner iteration in which the log-barrier merit function is approximately minimized subject to satisfying the linear equality constraints, and an outer iteration that specifies both the decrease in the barrier parameter and the level of accuracy for the inner minimization. Under nondegeneracy assumptions, 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. The asymptotic rate of convergence of the resulting algorithm is Q-superlinear and may be chosen arbitrarily close to quadratic. Furthermore, this rate applies componentwise. These results hold in particular for the method described in [A. R. Conn, N. I. M. Gould, D. Orban, and P. L. Toint, Math. Program. Ser. B, 87 (2000), pp. 215-249] and indicate that the details of its inner minimization are irrelevant in the asymptotics, except for its accuracy requirements.

UR - http://www.scopus.com/inward/record.url?scp=0035603909&partnerID=8YFLogxK

U2 - 10.1137/S1052623400370515

DO - 10.1137/S1052623400370515

M3 - Article

VL - 11

SP - 974

EP - 1002

JO - SIAM Journal on Optimization

T2 - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 4

ER -