QN-like variable storage conjugate gradients View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1983-10

AUTHORS

A. Buckley, A. Lenir

ABSTRACT

Both conjugate gradient and quasi-Newton methods are quite successful at minimizing smooth nonlinear functions of several variables, and each has its advantages. In particular, conjugate gradient methods require much less storage to implement than a quasi-Newton code and therefore find application when storage limitations occur. They are, however, slower, so there have recently been attempts to combine CG and QN algorithms so as to obtain an algorithm with good convergence properties and low storage requirements. One such method is the code CONMIN due to Shanno and Phua; it has proven quite successful but it has one limitation. It has no middle ground, in that it either operates as a quasi-Newton code using O(n2) storage locations, or as a conjugate gradient code using 7n locations, but it cannot take advantage of the not unusual situation where more than 7n locations are available, but a quasi-Newton code requires an excessive amount of storage. In this paper we present a way of looking at conjugate gradient algorithms which was in fact given by Shanno and Phua but which we carry further, emphasize and clarify. This applies in particular to Beale's 3-term recurrence relation. Using this point of view, we develop a new combined CG-QN algorithm which can use whatever storage is available; CONMIN occurs as a special case. We present numerical results to demonstrate that the new algorithm is never worse than CONMIN and that it is almost always better if even a small amount of extra storage is provided. More... »

PAGES

155-175

References to SciGraph publications

  • 1978-12. Extending the relationship between the conjugate gradient and BFGS algorithms in MATHEMATICAL PROGRAMMING
  • 1982. A Portable Package for Testing Minimization Algorithms in EVALUATING MATHEMATICAL PROGRAMMING TECHNIQUES
  • 1978-08. Numerical comparison of several variable-metric algorithms in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 1978-12. A combined conjugate-gradient quasi-Newton minimization algorithm in MATHEMATICAL PROGRAMMING
  • 1977-12. Restart procedures for the conjugate gradient method in MATHEMATICAL PROGRAMMING
  • 1976-12. Optimal conditioning of self-scaling variable Metric algorithms in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02591943

    DOI

    http://dx.doi.org/10.1007/bf02591943

    DIMENSIONS

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


    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": "Concordia University", 
              "id": "https://www.grid.ac/institutes/grid.410319.e", 
              "name": [
                "Mathematics Department, Concordia University, Montreal, Quebec, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Buckley", 
            "givenName": "A.", 
            "id": "sg:person.016066202217.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016066202217.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Concordia University", 
              "id": "https://www.grid.ac/institutes/grid.410319.e", 
              "name": [
                "Mathematics Department, Concordia University, Montreal, Quebec, Canada"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lenir", 
            "givenName": "A.", 
            "id": "sg:person.012223243007.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012223243007.11"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1093/comjnl/7.2.149", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002056752"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01593790", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006434394", 
              "https://doi.org/10.1007/bf01593790"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01609038", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012435566", 
              "https://doi.org/10.1007/bf01609038"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01609038", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012435566", 
              "https://doi.org/10.1007/bf01609038"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1980-0572855-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016159641"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/6.2.163", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018099115"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00933517", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021380240", 
              "https://doi.org/10.1007/bf00933517"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355921.355933", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024229164"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01609018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027194903", 
              "https://doi.org/10.1007/bf01609018"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01609018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027194903", 
              "https://doi.org/10.1007/bf01609018"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-95406-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036476872", 
              "https://doi.org/10.1007/978-3-642-95406-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01580654", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040008409", 
              "https://doi.org/10.1007/bf01580654"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1978-0483452-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048465494"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0716059", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062852620"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/moor.3.3.244", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064724429"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1983-10", 
        "datePublishedReg": "1983-10-01", 
        "description": "Both conjugate gradient and quasi-Newton methods are quite successful at minimizing smooth nonlinear functions of several variables, and each has its advantages. In particular, conjugate gradient methods require much less storage to implement than a quasi-Newton code and therefore find application when storage limitations occur. They are, however, slower, so there have recently been attempts to combine CG and QN algorithms so as to obtain an algorithm with good convergence properties and low storage requirements. One such method is the code CONMIN due to Shanno and Phua; it has proven quite successful but it has one limitation. It has no middle ground, in that it either operates as a quasi-Newton code using O(n2) storage locations, or as a conjugate gradient code using 7n locations, but it cannot take advantage of the not unusual situation where more than 7n locations are available, but a quasi-Newton code requires an excessive amount of storage. In this paper we present a way of looking at conjugate gradient algorithms which was in fact given by Shanno and Phua but which we carry further, emphasize and clarify. This applies in particular to Beale's 3-term recurrence relation. Using this point of view, we develop a new combined CG-QN algorithm which can use whatever storage is available; CONMIN occurs as a special case. We present numerical results to demonstrate that the new algorithm is never worse than CONMIN and that it is almost always better if even a small amount of extra storage is provided.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02591943", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047630", 
            "issn": [
              "0025-5610", 
              "1436-4646"
            ], 
            "name": "Mathematical Programming", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "27"
          }
        ], 
        "name": "QN-like variable storage conjugate gradients", 
        "pagination": "155-175", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "34bbe832d50973ffbf43f82487582f83cbc8e42188c5cd0d9a27afe770c417bc"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02591943"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1011068366"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02591943", 
          "https://app.dimensions.ai/details/publication/pub.1011068366"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T13:33", 
        "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/0000000370_0000000370/records_46769_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF02591943"
      }
    ]
     

    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/bf02591943'

    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/bf02591943'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02591943'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02591943'


     

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

    113 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02591943 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author N51ae33a4b11341db9dfdfb41fb2683f1
    4 schema:citation sg:pub.10.1007/978-3-642-95406-1_22
    5 sg:pub.10.1007/bf00933517
    6 sg:pub.10.1007/bf01580654
    7 sg:pub.10.1007/bf01593790
    8 sg:pub.10.1007/bf01609018
    9 sg:pub.10.1007/bf01609038
    10 https://doi.org/10.1090/s0025-5718-1978-0483452-7
    11 https://doi.org/10.1090/s0025-5718-1980-0572855-7
    12 https://doi.org/10.1093/comjnl/6.2.163
    13 https://doi.org/10.1093/comjnl/7.2.149
    14 https://doi.org/10.1137/0716059
    15 https://doi.org/10.1145/355921.355933
    16 https://doi.org/10.1287/moor.3.3.244
    17 schema:datePublished 1983-10
    18 schema:datePublishedReg 1983-10-01
    19 schema:description Both conjugate gradient and quasi-Newton methods are quite successful at minimizing smooth nonlinear functions of several variables, and each has its advantages. In particular, conjugate gradient methods require much less storage to implement than a quasi-Newton code and therefore find application when storage limitations occur. They are, however, slower, so there have recently been attempts to combine CG and QN algorithms so as to obtain an algorithm with good convergence properties and low storage requirements. One such method is the code CONMIN due to Shanno and Phua; it has proven quite successful but it has one limitation. It has no middle ground, in that it either operates as a quasi-Newton code using O(n2) storage locations, or as a conjugate gradient code using 7n locations, but it cannot take advantage of the not unusual situation where more than 7n locations are available, but a quasi-Newton code requires an excessive amount of storage. In this paper we present a way of looking at conjugate gradient algorithms which was in fact given by Shanno and Phua but which we carry further, emphasize and clarify. This applies in particular to Beale's 3-term recurrence relation. Using this point of view, we develop a new combined CG-QN algorithm which can use whatever storage is available; CONMIN occurs as a special case. We present numerical results to demonstrate that the new algorithm is never worse than CONMIN and that it is almost always better if even a small amount of extra storage is provided.
    20 schema:genre research_article
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N8d1132e344fa45048db7e0a4c2c3dbdf
    24 N96648c4bf2e242db9cb5c6c967bbd300
    25 sg:journal.1047630
    26 schema:name QN-like variable storage conjugate gradients
    27 schema:pagination 155-175
    28 schema:productId N1467c8e986b1420796f6f996978dc291
    29 N57eb6edceee74f9ea6e723fab38598bf
    30 N955c624513274338a7379ce3a23fd8cc
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011068366
    32 https://doi.org/10.1007/bf02591943
    33 schema:sdDatePublished 2019-04-11T13:33
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher N490cd804e00e4c07aa6f45b8e63b531b
    36 schema:url http://link.springer.com/10.1007%2FBF02591943
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N1467c8e986b1420796f6f996978dc291 schema:name readcube_id
    41 schema:value 34bbe832d50973ffbf43f82487582f83cbc8e42188c5cd0d9a27afe770c417bc
    42 rdf:type schema:PropertyValue
    43 N490cd804e00e4c07aa6f45b8e63b531b schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N51ae33a4b11341db9dfdfb41fb2683f1 rdf:first sg:person.016066202217.47
    46 rdf:rest Ne3120f7251504fb98e6440dee9b78f00
    47 N57eb6edceee74f9ea6e723fab38598bf schema:name doi
    48 schema:value 10.1007/bf02591943
    49 rdf:type schema:PropertyValue
    50 N8d1132e344fa45048db7e0a4c2c3dbdf schema:issueNumber 2
    51 rdf:type schema:PublicationIssue
    52 N955c624513274338a7379ce3a23fd8cc schema:name dimensions_id
    53 schema:value pub.1011068366
    54 rdf:type schema:PropertyValue
    55 N96648c4bf2e242db9cb5c6c967bbd300 schema:volumeNumber 27
    56 rdf:type schema:PublicationVolume
    57 Ne3120f7251504fb98e6440dee9b78f00 rdf:first sg:person.012223243007.11
    58 rdf:rest rdf:nil
    59 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    60 schema:name Mathematical Sciences
    61 rdf:type schema:DefinedTerm
    62 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Numerical and Computational Mathematics
    64 rdf:type schema:DefinedTerm
    65 sg:journal.1047630 schema:issn 0025-5610
    66 1436-4646
    67 schema:name Mathematical Programming
    68 rdf:type schema:Periodical
    69 sg:person.012223243007.11 schema:affiliation https://www.grid.ac/institutes/grid.410319.e
    70 schema:familyName Lenir
    71 schema:givenName A.
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012223243007.11
    73 rdf:type schema:Person
    74 sg:person.016066202217.47 schema:affiliation https://www.grid.ac/institutes/grid.410319.e
    75 schema:familyName Buckley
    76 schema:givenName A.
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016066202217.47
    78 rdf:type schema:Person
    79 sg:pub.10.1007/978-3-642-95406-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036476872
    80 https://doi.org/10.1007/978-3-642-95406-1_22
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/bf00933517 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021380240
    83 https://doi.org/10.1007/bf00933517
    84 rdf:type schema:CreativeWork
    85 sg:pub.10.1007/bf01580654 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040008409
    86 https://doi.org/10.1007/bf01580654
    87 rdf:type schema:CreativeWork
    88 sg:pub.10.1007/bf01593790 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006434394
    89 https://doi.org/10.1007/bf01593790
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/bf01609018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027194903
    92 https://doi.org/10.1007/bf01609018
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/bf01609038 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012435566
    95 https://doi.org/10.1007/bf01609038
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1090/s0025-5718-1978-0483452-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048465494
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1090/s0025-5718-1980-0572855-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016159641
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1093/comjnl/6.2.163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018099115
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1093/comjnl/7.2.149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002056752
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1137/0716059 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062852620
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1145/355921.355933 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024229164
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1287/moor.3.3.244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724429
    110 rdf:type schema:CreativeWork
    111 https://www.grid.ac/institutes/grid.410319.e schema:alternateName Concordia University
    112 schema:name Mathematics Department, Concordia University, Montreal, Quebec, Canada
    113 rdf:type schema:Organization
     




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


    ...