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
On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0002-6252-7815
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2015 (English)In: Computational optimization and applications, ISSN 0926-6003, E-ISSN 1573-2894, Vol. 60, no 2, 377-392 p.Article in journal (Refereed) Published
Abstract [en]

It is well known that the conjugate gradient method and a quasi-Newton method, using any well-defined update matrix from the one-parameter Broyden family of up- dates, produce identical iterates on a quadratic problem with positive definite Hessian. This equivalence does not hold for any quasi-Newton method. We define precisely the conditions on the update matrix in the quasi-Newton method that give rise to this behavior. We show that the crucial facts are, that the range of each update matrix lies in the last two dimensions of the Krylov subspaces defined by the conjugate gradient method and that the quasi-Newton condition is satisfied. In the framework based on a sufficient condition to obtain mutually conjugate search directions, we show that the one-parameter Broyden family is complete.

A one-to-one correspondence between the Broyden parameter and the non-zero scaling of the search direction obtained from the corresponding quasi-Newton method compared to the one obtained in the conjugate gradient method is derived. In addition, we show that the update matrices from the one-parameter Broyden family are almost always well-defined on a quadratic problem with positive definte Hessian. The only exception is when the symmetric rank-one update is used and the unit steplength is taken in the same iteration. In this case it is the Broyden parameter that becomes undefined.

Place, publisher, year, edition, pages
Springer US, 2015. Vol. 60, no 2, 377-392 p.
Keyword [en]
conjugate gradient method, quasi-Newton method, unconstrained program
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-166670DOI: 10.1007/s10589-014-9677-5ISI: 000350470800004Scopus ID: 2-s2.0-84924222130OAI: oai:DiVA.org:kth-166670DiVA: diva2:811784
Funder
Swedish Research Council
Note

QC 20150518

Available from: 2015-05-13 Created: 2015-05-13 Last updated: 2017-12-04Bibliographically approved
In thesis
1. On Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization
Open this publication in new window or tab >>On Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we present research on mathematical properties of methods for solv- ing symmetric systems of linear equations that arise in various optimization problem formulations and in methods for solving such problems.

In the first and third paper (Paper A and Paper C), we consider the connection be- tween the method of conjugate gradients and quasi-Newton methods on strictly convex quadratic optimization problems or equivalently on a symmetric system of linear equa- tions with a positive definite matrix. We state conditions on the quasi-Newton matrix and the update matrix such that the search directions generated by the corresponding quasi-Newton method and the method of conjugate gradients respectively are parallel.

In paper A, we derive such conditions on the update matrix based on a sufficient condition to obtain mutually conjugate search directions. These conditions are shown to be equivalent to the one-parameter Broyden family. Further, we derive a one-to-one correspondence between the Broyden parameter and the scaling between the search directions from the method of conjugate gradients and a quasi-Newton method em- ploying some well-defined update scheme in the one-parameter Broyden family.

In paper C, we give necessary and sufficient conditions on the quasi-Newton ma- trix and on the update matrix such that equivalence with the method of conjugate gra- dients hold for the corresponding quasi-Newton method. We show that the set of quasi- Newton schemes admitted by these necessary and sufficient conditions is strictly larger than the one-parameter Broyden family. In addition, we show that this set of quasi- Newton schemes includes an infinite number of symmetric rank-one update schemes.

In the second paper (Paper B), we utilize an unnormalized Krylov subspace frame- work for solving symmetric systems of linear equations. These systems may be incom- patible and the matrix may be indefinite/singular. Such systems of symmetric linear equations arise in constrained optimization. In the case of an incompatible symmetric system of linear equations we give a certificate of incompatibility based on a projection on the null space of the symmetric matrix and characterize a minimum-residual solu- tion. Further we derive a minimum-residual method, give explicit recursions for the minimum-residual iterates and characterize a minimum-residual solution of minimum Euclidean norm.

Abstract [sv]

I denna avhandling betraktar vi matematiska egenskaper hos metoder för att lösa symmetriska linjära ekvationssystem som uppkommer i formuleringar och metoder för en mängd olika optimeringsproblem.

I första och tredje artikeln (Paper A och Paper C), undersöks kopplingen mellan konjugerade gradientmetoden och kvasi-Newtonmetoder när dessa appliceras på strikt konvexa kvadratiska optimeringsproblem utan bivillkor eller ekvivalent på ett symmet- risk linjärt ekvationssystem med en positivt definit symmetrisk matris. Vi ställer upp villkor på kvasi-Newtonmatrisen och uppdateringsmatrisen så att sökriktningen som fås från motsvarande kvasi-Newtonmetod blir parallell med den sökriktning som fås från konjugerade gradientmetoden.

I den första artikeln (Paper A), härleds villkor på uppdateringsmatrisen baserade på ett tillräckligt villkor för att få ömsesidigt konjugerade sökriktningar. Dessa villkor på kvasi-Newtonmetoden visas vara ekvivalenta med att uppdateringsstrategin tillhör Broydens enparameterfamilj. Vi tar också fram en ett-till-ett överensstämmelse mellan Broydenparametern och skalningen mellan sökriktningarna från konjugerade gradient- metoden och en kvasi-Newtonmetod som använder någon väldefinierad uppdaterings- strategi från Broydens enparameterfamilj.

I den tredje artikeln (Paper C), ger vi tillräckliga och nödvändiga villkor på en kvasi-Newtonmetod så att nämnda ekvivalens med konjugerade gradientmetoden er- hålls. Mängden kvasi-Newtonstrategier som uppfyller dessa villkor är strikt större än Broydens enparameterfamilj. Vi visar också att denna mängd kvasi-Newtonstrategier innehåller ett oändligt antal uppdateringsstrategier där uppdateringsmatrisen är en sym- metrisk matris av rang ett.

I den andra artikeln (Paper B), används ett ramverk för icke-normaliserade Krylov- underrumsmetoder för att lösa symmetriska linjära ekvationssystem. Dessa ekvations- system kan sakna lösning och matrisen kan vara indefinit/singulär. Denna typ av sym- metriska linjära ekvationssystem uppkommer i en mängd formuleringar och metoder för optimeringsproblem med bivillkor. I fallet då det symmetriska linjära ekvations- systemet saknar lösning ger vi ett certifikat för detta baserat på en projektion på noll- rummet för den symmetriska matrisen och karaktäriserar en minimum-residuallösning. Vi härleder även en minimum-residualmetod i detta ramverk samt ger explicita rekur- sionsformler för denna metod. I fallet då det symmetriska linjära ekvationssystemet saknar lösning så karaktäriserar vi en minimum-residuallösning av minsta euklidiska norm.

Place, publisher, year, edition, pages
KTH Royal Institute of Technology, 2015. xii, 18 p.
Series
TRITA-MAT-A, 2015:05
Keyword
symmetric system of linear equations, method of conjugate gradients, quasi-Newton method, unconstrained optimization, unconstrained quadratic optimiza- tion, Krylov subspace method, unnormalized Lanczos vectors, minimum-residual method, symmetriska linjära ekvationssystem, konjugerade gradientmetoden, kvasi- Newtonmetoder, optimering utan bivillkor, kvadratisk optimering utan bivillkor, Kry- lovunderrumsmetoder, icke-normaliserade Lanczosvektorer, minimum-residualmetoden
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-166675 (URN)978-91-7595-514-8 (ISBN)
Public defence
2015-06-12, F3, Lindstedtsvägen 26, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Funder
Swedish Research Council
Note

QC 20150519

Available from: 2015-05-19 Created: 2015-05-13 Last updated: 2015-05-22Bibliographically approved

Open Access in DiVA

Paper A(352 kB)47 downloads
File information
File name FULLTEXT01.pdfFile size 352 kBChecksum SHA-512
9b4345b334ad800329516b1783729b4c671d3cd9006c18df649d6d217305e49c348439f13abd58fa062e2199e05b5a3185d8b8d0c0ab25cc44ecd55e6d2e9df5
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusSpringer

Authority records BETA

Forsgren, Anders

Search in DiVA

By author/editor
Forsgren, AndersOdland, Tove
By organisation
Optimization and Systems Theory
In the same journal
Computational optimization and applications
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 47 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 444 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