The use of Band Matrices for Second Derivative Approximations in Trust Region Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

M. J. D. Powell

ABSTRACT

In many trust region algorithms for optimization calculations, each iteration seeks a vectord ∈ Rn that solves the linear system of equations (B +λI)d = -g, whereB is a symmetric estimate of a second derivative matrix, I is the unit matrix,g is a known gradient vector, and λ is a parameter that controls the length ofd. Several values of λ may be tried on each iteration, and, when there is no helpful sparsity inB, it is usual for each solution to require O(n3) operations. However, if an orthogonal matrix Ω, is available such thatM =ΩTBΩ is an nxn matrix of bandwidth 2s+1, thenΩTd can be calculated in onlyO(ns2) operations for each new λ, by writing the system in the form (M+λI)(ΩTd) = — ΩTg. We find, unfortunately, that the construction ofM and Ω fromB is usually more expensive than the solution of the original system, but in variable metric and quasi-Newton algorithms for unconstrained optimization, each iteration changesB by a matrix whose rank is at most two, and then updating techniques can be applied to Ω. Thus it is possible to reduce the average work per iteration fromO(n3) to O(n7/3) operations. Here the elements of each orthogonal matrix are calculated explicitly, but instead one can express the orthogonal matrix updates as products of Givens rotations, which allows the average work per iteration to be only O(n11/5) operations. Details of procedures that achieve these savings are described, and the O(n7/3) complexity is confirmed by numerical results. More... »

PAGES

3-28

References to SciGraph publications

  • 1983. Recent Developments in Algorithms and Software for Trust Region Methods in MATHEMATICAL PROGRAMMING THE STATE OF THE ART
  • Book

    TITLE

    Advances in Nonlinear Programming

    ISBN

    978-1-4613-3337-1
    978-1-4613-3335-7

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-1-4613-3335-7_1

    DOI

    http://dx.doi.org/10.1007/978-1-4613-3335-7_1

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1033777821


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Numerical and Computational Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Cambridge", 
              "id": "https://www.grid.ac/institutes/grid.5335.0", 
              "name": [
                "Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, CB3 9EW, Cambridge, England"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Powell", 
            "givenName": "M. J. D.", 
            "id": "sg:person.07731545105.07", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-68874-4_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010656325", 
              "https://doi.org/10.1007/978-3-642-68874-4_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0024-3795(96)00157-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039147129"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0720042", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062852930"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0904038", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062855628"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1998", 
        "datePublishedReg": "1998-01-01", 
        "description": "In many trust region algorithms for optimization calculations, each iteration seeks a vectord \u2208 Rn that solves the linear system of equations (B +\u03bbI)d = -g, whereB is a symmetric estimate of a second derivative matrix, I is the unit matrix,g is a known gradient vector, and \u03bb is a parameter that controls the length ofd. Several values of \u03bb may be tried on each iteration, and, when there is no helpful sparsity inB, it is usual for each solution to require O(n3) operations. However, if an orthogonal matrix \u03a9, is available such thatM =\u03a9TB\u03a9 is an nxn matrix of bandwidth 2s+1, then\u03a9Td can be calculated in onlyO(ns2) operations for each new \u03bb, by writing the system in the form (M+\u03bbI)(\u03a9Td) = \u2014 \u03a9Tg. We find, unfortunately, that the construction ofM and \u03a9 fromB is usually more expensive than the solution of the original system, but in variable metric and quasi-Newton algorithms for unconstrained optimization, each iteration changesB by a matrix whose rank is at most two, and then updating techniques can be applied to \u03a9. Thus it is possible to reduce the average work per iteration fromO(n3) to O(n7/3) operations. Here the elements of each orthogonal matrix are calculated explicitly, but instead one can express the orthogonal matrix updates as products of Givens rotations, which allows the average work per iteration to be only O(n11/5) operations. Details of procedures that achieve these savings are described, and the O(n7/3) complexity is confirmed by numerical results.", 
        "editor": [
          {
            "familyName": "Yuan", 
            "givenName": "Ya-xiang", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-1-4613-3335-7_1", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-1-4613-3337-1", 
            "978-1-4613-3335-7"
          ], 
          "name": "Advances in Nonlinear Programming", 
          "type": "Book"
        }, 
        "name": "The use of Band Matrices for Second Derivative Approximations in Trust Region Algorithms", 
        "pagination": "3-28", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033777821"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-1-4613-3335-7_1"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a0e7c6594a1ed4d4b32a22506a804da845a846b4df37f8ef1fbb4bf6554ef115"
            ]
          }
        ], 
        "publisher": {
          "location": "Boston, MA", 
          "name": "Springer US", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-1-4613-3335-7_1", 
          "https://app.dimensions.ai/details/publication/pub.1033777821"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T09:43", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000374_0000000374/records_119754_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-1-4613-3335-7_1"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3335-7_1'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3335-7_1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3335-7_1'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-3335-7_1'


     

    This table displays all metadata directly associated to this object as RDF triples.

    78 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-1-4613-3335-7_1 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N3be8b4948b274f65ab0635ff6aade371
    4 schema:citation sg:pub.10.1007/978-3-642-68874-4_11
    5 https://doi.org/10.1016/s0024-3795(96)00157-7
    6 https://doi.org/10.1137/0720042
    7 https://doi.org/10.1137/0904038
    8 schema:datePublished 1998
    9 schema:datePublishedReg 1998-01-01
    10 schema:description In many trust region algorithms for optimization calculations, each iteration seeks a vectord ∈ Rn that solves the linear system of equations (B +λI)d = -g, whereB is a symmetric estimate of a second derivative matrix, I is the unit matrix,g is a known gradient vector, and λ is a parameter that controls the length ofd. Several values of λ may be tried on each iteration, and, when there is no helpful sparsity inB, it is usual for each solution to require O(n3) operations. However, if an orthogonal matrix Ω, is available such thatM =ΩTBΩ is an nxn matrix of bandwidth 2s+1, thenΩTd can be calculated in onlyO(ns2) operations for each new λ, by writing the system in the form (M+λI)(ΩTd) = — ΩTg. We find, unfortunately, that the construction ofM and Ω fromB is usually more expensive than the solution of the original system, but in variable metric and quasi-Newton algorithms for unconstrained optimization, each iteration changesB by a matrix whose rank is at most two, and then updating techniques can be applied to Ω. Thus it is possible to reduce the average work per iteration fromO(n3) to O(n7/3) operations. Here the elements of each orthogonal matrix are calculated explicitly, but instead one can express the orthogonal matrix updates as products of Givens rotations, which allows the average work per iteration to be only O(n11/5) operations. Details of procedures that achieve these savings are described, and the O(n7/3) complexity is confirmed by numerical results.
    11 schema:editor N99d4856f1f4a474d95b1eb364878e868
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf N2cba9db8c0054da2964135181623b881
    16 schema:name The use of Band Matrices for Second Derivative Approximations in Trust Region Algorithms
    17 schema:pagination 3-28
    18 schema:productId N6eb16f3de44a4032ad0ee2eadbb3d656
    19 N9e13af3d19dd49f9b04fc05f5f7799d9
    20 Nefb2d63e12aa470d8b5f2fd4cea1e8b6
    21 schema:publisher N40a1ee56f9ae4ceeaa8f81fc0954bba6
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033777821
    23 https://doi.org/10.1007/978-1-4613-3335-7_1
    24 schema:sdDatePublished 2019-04-16T09:43
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher N64dac967ad14409ebbe88eedb64a5a8d
    27 schema:url https://link.springer.com/10.1007%2F978-1-4613-3335-7_1
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N2cba9db8c0054da2964135181623b881 schema:isbn 978-1-4613-3335-7
    32 978-1-4613-3337-1
    33 schema:name Advances in Nonlinear Programming
    34 rdf:type schema:Book
    35 N3be8b4948b274f65ab0635ff6aade371 rdf:first sg:person.07731545105.07
    36 rdf:rest rdf:nil
    37 N40a1ee56f9ae4ceeaa8f81fc0954bba6 schema:location Boston, MA
    38 schema:name Springer US
    39 rdf:type schema:Organisation
    40 N64dac967ad14409ebbe88eedb64a5a8d schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N6eb16f3de44a4032ad0ee2eadbb3d656 schema:name doi
    43 schema:value 10.1007/978-1-4613-3335-7_1
    44 rdf:type schema:PropertyValue
    45 N99d4856f1f4a474d95b1eb364878e868 rdf:first N9e175c76d00f46319a832c6cb452cf42
    46 rdf:rest rdf:nil
    47 N9e13af3d19dd49f9b04fc05f5f7799d9 schema:name readcube_id
    48 schema:value a0e7c6594a1ed4d4b32a22506a804da845a846b4df37f8ef1fbb4bf6554ef115
    49 rdf:type schema:PropertyValue
    50 N9e175c76d00f46319a832c6cb452cf42 schema:familyName Yuan
    51 schema:givenName Ya-xiang
    52 rdf:type schema:Person
    53 Nefb2d63e12aa470d8b5f2fd4cea1e8b6 schema:name dimensions_id
    54 schema:value pub.1033777821
    55 rdf:type schema:PropertyValue
    56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Mathematical Sciences
    58 rdf:type schema:DefinedTerm
    59 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Numerical and Computational Mathematics
    61 rdf:type schema:DefinedTerm
    62 sg:person.07731545105.07 schema:affiliation https://www.grid.ac/institutes/grid.5335.0
    63 schema:familyName Powell
    64 schema:givenName M. J. D.
    65 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07731545105.07
    66 rdf:type schema:Person
    67 sg:pub.10.1007/978-3-642-68874-4_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010656325
    68 https://doi.org/10.1007/978-3-642-68874-4_11
    69 rdf:type schema:CreativeWork
    70 https://doi.org/10.1016/s0024-3795(96)00157-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039147129
    71 rdf:type schema:CreativeWork
    72 https://doi.org/10.1137/0720042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062852930
    73 rdf:type schema:CreativeWork
    74 https://doi.org/10.1137/0904038 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855628
    75 rdf:type schema:CreativeWork
    76 https://www.grid.ac/institutes/grid.5335.0 schema:alternateName University of Cambridge
    77 schema:name Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Silver Street, CB3 9EW, Cambridge, England
    78 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...