Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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 Methods for Solving Symmetric Systems of Linear Equations Arising in Optimization
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
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 [en]
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
Keyword [sv]
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: urn:nbn:se:kth:diva-166675ISBN: 978-91-7595-514-8 (print)OAI: oai:DiVA.org:kth-166675DiVA: diva2:811798
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
List of papers
1. On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems
Open this publication in new window or tab >>On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems
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
Keyword
conjugate gradient method, quasi-Newton method, unconstrained program
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-166670 (URN)10.1007/s10589-014-9677-5 (DOI)000350470800004 ()2-s2.0-84924222130 (Scopus ID)
Funder
Swedish Research Council
Note

QC 20150518

Available from: 2015-05-13 Created: 2015-05-13 Last updated: 2017-12-04Bibliographically approved
2. On solving symmetric systems of linear equations in an unnormalized Krylov subspace framework
Open this publication in new window or tab >>On solving symmetric systems of linear equations in an unnormalized Krylov subspace framework
(English)Article in journal (Other academic) Submitted
Abstract [en]

In an unnormalized Krylov subspace framework for solving symmetric systems of linear equations, the orthogonal vectors that are generated by a Lanczos process are not necessarily on the form of gradients. Associating each orthogonal vector with a triple, and using only the three-term recurrences of the triples, we give conditions on whether a symmetric system of linear equations is compatible or incompatible. In the compatible case, a solution is given and in the incompatible case, a certificate of incompatibility is obtained. In particular, the case when the matrix is singular is handled.

We also derive a minimum-residual method based on this framework and show how the iterates may be updated explicitly based on the triples, and in the incompatible case a minimum-residual solution of minimum Euclidean norm is obtained.

Keyword
Krylov subspace method, symmetric system of linear equations, unnormalized Lanczos vectors, minimum-residual method
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-166671 (URN)
Funder
Swedish Research Council
Note

QS 2015

Available from: 2015-05-13 Created: 2015-05-13 Last updated: 2015-05-19Bibliographically approved
3. On the equivalence of the method of conjugate gradients and quasi-Newton methods on quadratic problems
Open this publication in new window or tab >>On the equivalence of the method of conjugate gradients and quasi-Newton methods on quadratic problems
(English)In: Computational optimization and applications, ISSN 0926-6003, E-ISSN 1573-2894Article in journal (Other academic) Submitted
Abstract [en]

In this paper we state necessary and sufficient conditions for equivalence of the method of conjugate gradients and quasi-Newton methods on a quadratic problem. We show that the set of quasi-Newton schemes that generate parallel search directions to those of the method of conjugate gradients is strictly larger than the one-parameter Broyden family. In addition, we show that this set contains an infinite number of symmetric rank-one update schemes.

Keyword
method of conjugate gradients, quasi-Newton method, uncon- strained quadratic program
National Category
Computational Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-166674 (URN)
Funder
Swedish Research Council
Note

QS 2015

Available from: 2015-05-13 Created: 2015-05-13 Last updated: 2017-12-04Bibliographically approved

Open Access in DiVA

Intro(501 kB)409 downloads
File information
File name FULLTEXT01.pdfFile size 501 kBChecksum SHA-512
274f6384db3d0f8777e7f346f44752792a5a89d5a240b1d1c463ef24beaeb2500773b68d1e116be60c713f1e3c06336b64b5ea8cf26d32c689b977d766492365
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Odland, Tove
By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 409 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 477 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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