Analysis of a self-scaling quasi-Newton method View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-08

AUTHORS

Jorge Nocedal, Ya-xiang Yuan

ABSTRACT

We study the self-scaling BFGS method of Oren and Luenberger (1974) for solving unconstrained optimization problems. For general convex functions, we prove that the method is globally convergent with inexact line searches. We also show that the directions generated by the self-scaling BFGS method approach Newton's direction asymptotically. This would ensure superlinear convergence if, in addition, the search directions were well-scaled, but we show that this is not always the case. We find that the method has a major drawback: to achieve superlinear convergence it may be necessary to evaluate the function twice per iteration, even very near the solution. An example is constructed to show that the step-sizes required to achieve a superlinear rate converge to 2 and 0.5 alternately. More... »

PAGES

19-37

References to SciGraph publications

  • 1987-07. Updating conjugate directions by the BFGS formula in MATHEMATICAL PROGRAMMING
  • 1982-06. Perspectives on self-scaling variable metric algorithms in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 1978-12. Matrix conditioning and nonlinear optimization in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "Northwestern University", 
              "id": "https://www.grid.ac/institutes/grid.16753.36", 
              "name": [
                "Department of Electrical Engineering and Computer Science, Northwestern University, 60208, Evanston, IL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Nocedal", 
            "givenName": "Jorge", 
            "id": "sg:person.01157306714.71", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01157306714.71"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Chinese Academy of Sciences", 
              "id": "https://www.grid.ac/institutes/grid.9227.e", 
              "name": [
                "Computing Center, Academia Sinica, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yuan", 
            "givenName": "Ya-xiang", 
            "id": "sg:person.0644124765.67", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0644124765.67"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02591850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039185361", 
              "https://doi.org/10.1007/bf02591850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02591850", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039185361", 
              "https://doi.org/10.1007/bf02591850"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00934764", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040761822", 
              "https://doi.org/10.1007/bf00934764"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1974-0343581-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041195304"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355934.355936", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043056536"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01588962", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048725219", 
              "https://doi.org/10.1007/bf01588962"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/12.2.171", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052839649"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0724077", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062853304"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0726042", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062853446"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1011036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062860143"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1013035", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062860380"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.20.5.845", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064717375"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1993-08", 
        "datePublishedReg": "1993-08-01", 
        "description": "We study the self-scaling BFGS method of Oren and Luenberger (1974) for solving unconstrained optimization problems. For general convex functions, we prove that the method is globally convergent with inexact line searches. We also show that the directions generated by the self-scaling BFGS method approach Newton's direction asymptotically. This would ensure superlinear convergence if, in addition, the search directions were well-scaled, but we show that this is not always the case. We find that the method has a major drawback: to achieve superlinear convergence it may be necessary to evaluate the function twice per iteration, even very near the solution. An example is constructed to show that the step-sizes required to achieve a superlinear rate converge to 2 and 0.5 alternately.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01582136", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047630", 
            "issn": [
              "0025-5610", 
              "1436-4646"
            ], 
            "name": "Mathematical Programming", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "61"
          }
        ], 
        "name": "Analysis of a self-scaling quasi-Newton method", 
        "pagination": "19-37", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "eaaa2b0041d3d510722607a8f84aac6678c164bbe3d19cf6b01c8b92c05d2192"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01582136"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1049259876"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01582136", 
          "https://app.dimensions.ai/details/publication/pub.1049259876"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T18:24", 
        "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/0000000001_0000000264/records_8675_00000534.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF01582136"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    107 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01582136 schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Nac22d5b601164437adf4e172826452b8
    4 schema:citation sg:pub.10.1007/bf00934764
    5 sg:pub.10.1007/bf01588962
    6 sg:pub.10.1007/bf02591850
    7 https://doi.org/10.1090/s0025-5718-1974-0343581-1
    8 https://doi.org/10.1093/comjnl/12.2.171
    9 https://doi.org/10.1137/0724077
    10 https://doi.org/10.1137/0726042
    11 https://doi.org/10.1137/1011036
    12 https://doi.org/10.1137/1013035
    13 https://doi.org/10.1145/355934.355936
    14 https://doi.org/10.1287/mnsc.20.5.845
    15 schema:datePublished 1993-08
    16 schema:datePublishedReg 1993-08-01
    17 schema:description We study the self-scaling BFGS method of Oren and Luenberger (1974) for solving unconstrained optimization problems. For general convex functions, we prove that the method is globally convergent with inexact line searches. We also show that the directions generated by the self-scaling BFGS method approach Newton's direction asymptotically. This would ensure superlinear convergence if, in addition, the search directions were well-scaled, but we show that this is not always the case. We find that the method has a major drawback: to achieve superlinear convergence it may be necessary to evaluate the function twice per iteration, even very near the solution. An example is constructed to show that the step-sizes required to achieve a superlinear rate converge to 2 and 0.5 alternately.
    18 schema:genre research_article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf Nb40e484dae294bd4a12fb9919b8e0065
    22 Nd87ea47eb0b14a0f87b0c6d89592d511
    23 sg:journal.1047630
    24 schema:name Analysis of a self-scaling quasi-Newton method
    25 schema:pagination 19-37
    26 schema:productId N876f5acac6fb4856b2a7131a96ddc5a0
    27 Nca46faf9d5a8401494ccdd33354a8421
    28 Ne9ade9ee649141ff9daff1250d81cd63
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049259876
    30 https://doi.org/10.1007/bf01582136
    31 schema:sdDatePublished 2019-04-10T18:24
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher N30425b1a2b984a81bbc78f82626360dc
    34 schema:url http://link.springer.com/10.1007%2FBF01582136
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset articles
    37 rdf:type schema:ScholarlyArticle
    38 N2c72109bc469451c93930748ac71abae rdf:first sg:person.0644124765.67
    39 rdf:rest rdf:nil
    40 N30425b1a2b984a81bbc78f82626360dc schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N876f5acac6fb4856b2a7131a96ddc5a0 schema:name readcube_id
    43 schema:value eaaa2b0041d3d510722607a8f84aac6678c164bbe3d19cf6b01c8b92c05d2192
    44 rdf:type schema:PropertyValue
    45 Nac22d5b601164437adf4e172826452b8 rdf:first sg:person.01157306714.71
    46 rdf:rest N2c72109bc469451c93930748ac71abae
    47 Nb40e484dae294bd4a12fb9919b8e0065 schema:volumeNumber 61
    48 rdf:type schema:PublicationVolume
    49 Nca46faf9d5a8401494ccdd33354a8421 schema:name dimensions_id
    50 schema:value pub.1049259876
    51 rdf:type schema:PropertyValue
    52 Nd87ea47eb0b14a0f87b0c6d89592d511 schema:issueNumber 1-3
    53 rdf:type schema:PublicationIssue
    54 Ne9ade9ee649141ff9daff1250d81cd63 schema:name doi
    55 schema:value 10.1007/bf01582136
    56 rdf:type schema:PropertyValue
    57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    58 schema:name Mathematical Sciences
    59 rdf:type schema:DefinedTerm
    60 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    61 schema:name Numerical and Computational Mathematics
    62 rdf:type schema:DefinedTerm
    63 sg:journal.1047630 schema:issn 0025-5610
    64 1436-4646
    65 schema:name Mathematical Programming
    66 rdf:type schema:Periodical
    67 sg:person.01157306714.71 schema:affiliation https://www.grid.ac/institutes/grid.16753.36
    68 schema:familyName Nocedal
    69 schema:givenName Jorge
    70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01157306714.71
    71 rdf:type schema:Person
    72 sg:person.0644124765.67 schema:affiliation https://www.grid.ac/institutes/grid.9227.e
    73 schema:familyName Yuan
    74 schema:givenName Ya-xiang
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0644124765.67
    76 rdf:type schema:Person
    77 sg:pub.10.1007/bf00934764 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040761822
    78 https://doi.org/10.1007/bf00934764
    79 rdf:type schema:CreativeWork
    80 sg:pub.10.1007/bf01588962 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048725219
    81 https://doi.org/10.1007/bf01588962
    82 rdf:type schema:CreativeWork
    83 sg:pub.10.1007/bf02591850 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039185361
    84 https://doi.org/10.1007/bf02591850
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1090/s0025-5718-1974-0343581-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041195304
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1093/comjnl/12.2.171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052839649
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1137/0724077 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062853304
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1137/0726042 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062853446
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1137/1011036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062860143
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1137/1013035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062860380
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1145/355934.355936 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043056536
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1287/mnsc.20.5.845 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064717375
    101 rdf:type schema:CreativeWork
    102 https://www.grid.ac/institutes/grid.16753.36 schema:alternateName Northwestern University
    103 schema:name Department of Electrical Engineering and Computer Science, Northwestern University, 60208, Evanston, IL, USA
    104 rdf:type schema:Organization
    105 https://www.grid.ac/institutes/grid.9227.e schema:alternateName Chinese Academy of Sciences
    106 schema:name Computing Center, Academia Sinica, Beijing, China
    107 rdf:type schema:Organization
     




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


    ...