Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Iterative solution of augmented systems arising in interior methods
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0002-6252-7815
2007 (English)In: SIAM Journal on Optimization, ISSN 1052-6234, E-ISSN 1095-7189, Vol. 18, no 2, 666-690 p.Article in journal (Refereed) Published
Abstract [en]

Iterative methods are proposed for certain augmented systems of linear equations that arise in interior methods for general nonlinear optimization. Interior methods de. ne a sequence of KKT equations that represent the symmetrized ( but indefinite) equations associated with Newton's method for a point satisfying the perturbed optimality conditions. These equations involve both the primal and dual variables and become increasingly ill- conditioned as the optimization proceeds. In this context, an iterative linear solver must not only handle the ill- conditioning but also detect the occurrence of KKT matrices with the wrong matrix inertia. A one- parameter family of equivalent linear equations is formulated that includes the KKT system as a special case. The discussion focuses on a particular system from this family, known as the " doubly augmented system," that is positive definite with respect to both the primal and dual variables. This property means that a standard preconditioned conjugate- gradient method involving both primal and dual variables will either terminate successfully or detect if the KKT matrix has the wrong inertia. Constraint preconditioning is a well- known technique for preconditioning the conjugate- gradient method on augmented systems. A family of constraint preconditioners is proposed that provably eliminates the inherent ill- conditioning in the augmented system. A considerable benefit of combining constraint preconditioning with the doubly augmented system is that the preconditioner need not be applied exactly. Two particular " active- set" constraint preconditioners are formulated that involve only a subset of the rows of the augmented system and thereby may be applied with considerably less work. Finally, some numerical experiments illustrate the numerical performance of the proposed preconditioners and highlight some theoretical properties of the preconditioned matrices.

Place, publisher, year, edition, pages
2007. Vol. 18, no 2, 666-690 p.
Keyword [en]
large-scale nonlinear programming, nonconvex optimization, interior, methods, augmented systems, KKT systems, iterative methods, conjugate-gradient method, constraint preconditioning, indefinite systems, point methods, constrained optimization, nonlinear, optimization, linear-systems, newton methods, algorithm, preconditioners, equations
Identifiers
URN: urn:nbn:se:kth:diva-17018DOI: 10.1137/060650210ISI: 000250005300014Scopus ID: 2-s2.0-44649161910OAI: oai:DiVA.org:kth-17018DiVA: diva2:335061
Note
QC 20100525Available from: 2010-08-05 Created: 2010-08-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Forsgren, Anders

Search in DiVA

By author/editor
Forsgren, Anders
By organisation
Optimization and Systems Theory
In the same journal
SIAM Journal on Optimization

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf