Optimally conditioned optimization algorithms without line searches View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1975-12

AUTHORS

William C. Davidon

ABSTRACT

New variable metric algorithms are presented with three distinguishing features:They make no line searches and allow quite arbitrary step directions while maintaining quadratic termination and positive updates for the matrixH, whose inverse is the hessian matrix of second derivatives for a quadratic approximation to the objective function.The updates fromH toH+ are optimally conditioned in the sense that they minimize the ratio of the largest to smallest eigenvalue ofH−1H+.Instead of working with the matrixH directly, these algorithms represent it asJJT, and only store and update the Jacobian matrix J. A theoretical basis is laid for this family of algorithms and an example is given along with encouraging numerical results obtained with several standard test functions. They make no line searches and allow quite arbitrary step directions while maintaining quadratic termination and positive updates for the matrixH, whose inverse is the hessian matrix of second derivatives for a quadratic approximation to the objective function. The updates fromH toH+ are optimally conditioned in the sense that they minimize the ratio of the largest to smallest eigenvalue ofH−1H+. Instead of working with the matrixH directly, these algorithms represent it asJJT, and only store and update the Jacobian matrix J. A theoretical basis is laid for this family of algorithms and an example is given along with encouraging numerical results obtained with several standard test functions. More... »

PAGES

1-30

References to SciGraph publications

  • 1972-02. Quasi-newton algorithms generate identical points in MATHEMATICAL PROGRAMMING
  • 1970-06. Unified approach to quadratically convergent algorithms for function minimization in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Journal

    TITLE

    Mathematical Programming

    ISSUE

    1

    VOLUME

    9

    Author Affiliations

    Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied 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": "Haverford College", 
              "id": "https://www.grid.ac/institutes/grid.256868.7", 
              "name": [
                "Haverford College, Haverford, Pa., USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Davidon", 
            "givenName": "William C.", 
            "id": "sg:person.013710774053.84", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013710774053.84"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1090/s0025-5718-1970-0274029-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000595399"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/3.3.175", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003083189"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01584554", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003926874", 
              "https://doi.org/10.1007/bf01584554"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01584554", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003926874", 
              "https://doi.org/10.1007/bf01584554"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1090/s0025-5718-1970-0258249-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004777117"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/9.1.67", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005173175"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/13.3.317", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007597686"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00927440", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016331971", 
              "https://doi.org/10.1007/bf00927440"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00927440", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016331971", 
              "https://doi.org/10.1007/bf00927440"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/6.2.163", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018099115"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/5.2.147", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023046251"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/imamat/11.1.73", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059684298"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/imamat/6.1.76", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059685636"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1975-12", 
        "datePublishedReg": "1975-12-01", 
        "description": "New variable metric algorithms are presented with three distinguishing features:They make no line searches and allow quite arbitrary step directions while maintaining quadratic termination and positive updates for the matrixH, whose inverse is the hessian matrix of second derivatives for a quadratic approximation to the objective function.The updates fromH toH+ are optimally conditioned in the sense that they minimize the ratio of the largest to smallest eigenvalue ofH\u22121H+.Instead of working with the matrixH directly, these algorithms represent it asJJT, and only store and update the Jacobian matrix J. A theoretical basis is laid for this family of algorithms and an example is given along with encouraging numerical results obtained with several standard test functions. They make no line searches and allow quite arbitrary step directions while maintaining quadratic termination and positive updates for the matrixH, whose inverse is the hessian matrix of second derivatives for a quadratic approximation to the objective function. The updates fromH toH+ are optimally conditioned in the sense that they minimize the ratio of the largest to smallest eigenvalue ofH\u22121H+. Instead of working with the matrixH directly, these algorithms represent it asJJT, and only store and update the Jacobian matrix J. A theoretical basis is laid for this family of algorithms and an example is given along with encouraging numerical results obtained with several standard test functions.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf01681328", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1047630", 
            "issn": [
              "0025-5610", 
              "1436-4646"
            ], 
            "name": "Mathematical Programming", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "9"
          }
        ], 
        "name": "Optimally conditioned optimization algorithms without line searches", 
        "pagination": "1-30", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "630abdb9e76e535d8a758a33550120cb7a3f7a0f58b7d25dbb7565d00a7a97a9"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf01681328"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020786346"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf01681328", 
          "https://app.dimensions.ai/details/publication/pub.1020786346"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T09:08", 
        "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/0000000338_0000000338/records_47960_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF01681328"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    96 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf01681328 schema:about anzsrc-for:01
    2 anzsrc-for:0102
    3 schema:author N50fbd42a725947dd9b716fe486c18cb5
    4 schema:citation sg:pub.10.1007/bf00927440
    5 sg:pub.10.1007/bf01584554
    6 https://doi.org/10.1090/s0025-5718-1970-0258249-6
    7 https://doi.org/10.1090/s0025-5718-1970-0274029-x
    8 https://doi.org/10.1093/comjnl/13.3.317
    9 https://doi.org/10.1093/comjnl/3.3.175
    10 https://doi.org/10.1093/comjnl/5.2.147
    11 https://doi.org/10.1093/comjnl/6.2.163
    12 https://doi.org/10.1093/comjnl/9.1.67
    13 https://doi.org/10.1093/imamat/11.1.73
    14 https://doi.org/10.1093/imamat/6.1.76
    15 schema:datePublished 1975-12
    16 schema:datePublishedReg 1975-12-01
    17 schema:description New variable metric algorithms are presented with three distinguishing features:They make no line searches and allow quite arbitrary step directions while maintaining quadratic termination and positive updates for the matrixH, whose inverse is the hessian matrix of second derivatives for a quadratic approximation to the objective function.The updates fromH toH+ are optimally conditioned in the sense that they minimize the ratio of the largest to smallest eigenvalue ofH−1H+.Instead of working with the matrixH directly, these algorithms represent it asJJT, and only store and update the Jacobian matrix J. A theoretical basis is laid for this family of algorithms and an example is given along with encouraging numerical results obtained with several standard test functions. They make no line searches and allow quite arbitrary step directions while maintaining quadratic termination and positive updates for the matrixH, whose inverse is the hessian matrix of second derivatives for a quadratic approximation to the objective function. The updates fromH toH+ are optimally conditioned in the sense that they minimize the ratio of the largest to smallest eigenvalue ofH−1H+. Instead of working with the matrixH directly, these algorithms represent it asJJT, and only store and update the Jacobian matrix J. A theoretical basis is laid for this family of algorithms and an example is given along with encouraging numerical results obtained with several standard test functions.
    18 schema:genre research_article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N042eba8caf3e466f981871ea5fbb59e8
    22 Nf895bf36eff94f95a275c02f0a654fc4
    23 sg:journal.1047630
    24 schema:name Optimally conditioned optimization algorithms without line searches
    25 schema:pagination 1-30
    26 schema:productId N0b44fadd995f4db38aa8402dd6005019
    27 N23f0490969f048fabd59bdfc6082dc0a
    28 N75a2fa5cce024b1dbb8c769f0ee2b069
    29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020786346
    30 https://doi.org/10.1007/bf01681328
    31 schema:sdDatePublished 2019-04-11T09:08
    32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    33 schema:sdPublisher N1b89196666484019ab985ed4a21e82a2
    34 schema:url http://link.springer.com/10.1007%2FBF01681328
    35 sgo:license sg:explorer/license/
    36 sgo:sdDataset articles
    37 rdf:type schema:ScholarlyArticle
    38 N042eba8caf3e466f981871ea5fbb59e8 schema:volumeNumber 9
    39 rdf:type schema:PublicationVolume
    40 N0b44fadd995f4db38aa8402dd6005019 schema:name doi
    41 schema:value 10.1007/bf01681328
    42 rdf:type schema:PropertyValue
    43 N1b89196666484019ab985ed4a21e82a2 schema:name Springer Nature - SN SciGraph project
    44 rdf:type schema:Organization
    45 N23f0490969f048fabd59bdfc6082dc0a schema:name readcube_id
    46 schema:value 630abdb9e76e535d8a758a33550120cb7a3f7a0f58b7d25dbb7565d00a7a97a9
    47 rdf:type schema:PropertyValue
    48 N50fbd42a725947dd9b716fe486c18cb5 rdf:first sg:person.013710774053.84
    49 rdf:rest rdf:nil
    50 N75a2fa5cce024b1dbb8c769f0ee2b069 schema:name dimensions_id
    51 schema:value pub.1020786346
    52 rdf:type schema:PropertyValue
    53 Nf895bf36eff94f95a275c02f0a654fc4 schema:issueNumber 1
    54 rdf:type schema:PublicationIssue
    55 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Mathematical Sciences
    57 rdf:type schema:DefinedTerm
    58 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Applied Mathematics
    60 rdf:type schema:DefinedTerm
    61 sg:journal.1047630 schema:issn 0025-5610
    62 1436-4646
    63 schema:name Mathematical Programming
    64 rdf:type schema:Periodical
    65 sg:person.013710774053.84 schema:affiliation https://www.grid.ac/institutes/grid.256868.7
    66 schema:familyName Davidon
    67 schema:givenName William C.
    68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013710774053.84
    69 rdf:type schema:Person
    70 sg:pub.10.1007/bf00927440 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016331971
    71 https://doi.org/10.1007/bf00927440
    72 rdf:type schema:CreativeWork
    73 sg:pub.10.1007/bf01584554 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003926874
    74 https://doi.org/10.1007/bf01584554
    75 rdf:type schema:CreativeWork
    76 https://doi.org/10.1090/s0025-5718-1970-0258249-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004777117
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1090/s0025-5718-1970-0274029-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1000595399
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.1093/comjnl/13.3.317 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007597686
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1093/comjnl/3.3.175 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003083189
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1093/comjnl/5.2.147 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023046251
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1093/comjnl/6.2.163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018099115
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1093/comjnl/9.1.67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005173175
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1093/imamat/11.1.73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059684298
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1093/imamat/6.1.76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059685636
    93 rdf:type schema:CreativeWork
    94 https://www.grid.ac/institutes/grid.256868.7 schema:alternateName Haverford College
    95 schema:name Haverford College, Haverford, Pa., USA
    96 rdf:type schema:Organization
     




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


    ...