A cubic regularization of Newton’s method with finite difference Hessian approximations View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2021-10-13

AUTHORS

G. N. Grapiglia, M. L. N. Gonçalves, G. N. Silva

ABSTRACT

In this paper, we present a version of the cubic regularization of Newton’s method for unconstrained nonconvex optimization, in which the Hessian matrices are approximated by forward finite difference Hessians. The regularization parameter of the cubic models and the accuracy of the Hessian approximations are jointly adjusted using a nonmonotone line search criterion. Assuming that the Hessian of the objective function is globally Lipschitz continuous, we show that the proposed method needs at most On𝜖−3/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {O}\left (n\epsilon ^{-3/2}\right )$\end{document} function and gradient evaluations to generate an 𝜖-approximate stationary point, where n is the dimension of the domain of the objective function. Preliminary numerical results corroborate our theoretical findings. More... »

PAGES

1-24

References to SciGraph publications

  • 2016-10-15. Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization in JOURNAL OF GLOBAL OPTIMIZATION
  • 2016-05-17. A trust region algorithm with a worst-case iteration complexity of O(ϵ-3/2) for nonconvex optimization in MATHEMATICAL PROGRAMMING
  • 2019-06-07. Lower bounds for finding stationary points I in MATHEMATICAL PROGRAMMING
  • 2017-09-16. Fast derivatives of likelihood functionals for ODE based models using adjoint-state method in COMPUTATIONAL STATISTICS
  • 2006-04-25. Cubic regularization of Newton method and its global performance in MATHEMATICAL PROGRAMMING
  • 2018-07-10. A Line-Search Algorithm Inspired by the Adaptive Cubic Regularization Framework and Complexity Analysis in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2016-08-30. Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models in MATHEMATICAL PROGRAMMING
  • 1912-12. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung) in MATHEMATISCHE ANNALEN
  • 2017-07-26. On the worst-case evaluation complexity of non-monotone line search algorithms in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • 2009-05-19. Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results in MATHEMATICAL PROGRAMMING
  • 2010-01-10. Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11075-021-01200-y

    DOI

    http://dx.doi.org/10.1007/s11075-021-01200-y

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Departamento de Matem\u00e1tica, Universidade Federal do Paran\u00e1, Centro Polit\u00e9cnico, Cx. postal 19.081, 81531-980, Curitiba, PR, Brazil", 
              "id": "http://www.grid.ac/institutes/grid.20736.30", 
              "name": [
                "Departamento de Matem\u00e1tica, Universidade Federal do Paran\u00e1, Centro Polit\u00e9cnico, Cx. postal 19.081, 81531-980, Curitiba, PR, Brazil"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Grapiglia", 
            "givenName": "G. N.", 
            "id": "sg:person.010427573717.89", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010427573717.89"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "IME, Universidade Federal de Goi\u00e1s, Campus II- Cx. postal 131, 74001-970, Goi\u00e2nia, GO, Brazil", 
              "id": "http://www.grid.ac/institutes/grid.411195.9", 
              "name": [
                "IME, Universidade Federal de Goi\u00e1s, Campus II- Cx. postal 131, 74001-970, Goi\u00e2nia, GO, Brazil"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gon\u00e7alves", 
            "givenName": "M. L. N.", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Colegiado de Matem\u00e1tica, Universidade Federal do Oeste da Bahia, 47808-021, Barreiras, BA, Brazil", 
              "id": "http://www.grid.ac/institutes/grid.472638.c", 
              "name": [
                "Colegiado de Matem\u00e1tica, Universidade Federal do Oeste da Bahia, 47808-021, Barreiras, BA, Brazil"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Silva", 
            "givenName": "G. N.", 
            "id": "sg:person.016672542147.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016672542147.21"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10107-016-1026-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008021320", 
              "https://doi.org/10.1007/s10107-016-1026-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-009-0337-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007745891", 
              "https://doi.org/10.1007/s10107-009-0337-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00180-017-0765-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091817170", 
              "https://doi.org/10.1007/s00180-017-0765-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01456804", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023104003", 
              "https://doi.org/10.1007/bf01456804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-006-0706-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001889025", 
              "https://doi.org/10.1007/s10107-006-0706-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10589-017-9928-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1090902476", 
              "https://doi.org/10.1007/s10589-017-9928-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-018-1341-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105463477", 
              "https://doi.org/10.1007/s10957-018-1341-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-016-1065-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007770754", 
              "https://doi.org/10.1007/s10107-016-1065-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-009-0286-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011221568", 
              "https://doi.org/10.1007/s10107-009-0286-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10898-016-0475-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008845437", 
              "https://doi.org/10.1007/s10898-016-0475-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-019-01406-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1116870816", 
              "https://doi.org/10.1007/s10107-019-01406-y"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-10-13", 
        "datePublishedReg": "2021-10-13", 
        "description": "In this paper, we present a version of the cubic regularization of Newton\u2019s method for unconstrained nonconvex optimization, in which the Hessian matrices are approximated by forward finite difference Hessians. The regularization parameter of the cubic models and the accuracy of the Hessian approximations are jointly adjusted using a nonmonotone line search criterion. Assuming that the Hessian of the objective function is globally Lipschitz continuous, we show that the proposed method needs at most On\ud835\udf16\u22123/2\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathcal {O}\\left (n\\epsilon ^{-3/2}\\right )$\\end{document} function and gradient evaluations to generate an \ud835\udf16-approximate stationary point, where n is the dimension of the domain of the objective function. Preliminary numerical results corroborate our theoretical findings.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11075-021-01200-y", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1050467", 
            "issn": [
              "1017-1398", 
              "1572-9265"
            ], 
            "name": "Numerical Algorithms", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "cubic regularization", 
          "Hessian approximation", 
          "Newton method", 
          "unconstrained nonconvex optimization", 
          "line search criterion", 
          "objective function", 
          "approximate stationary point", 
          "preliminary numerical results", 
          "nonconvex optimization", 
          "gradient evaluations", 
          "regularization parameter", 
          "Hessian matrix", 
          "stationary points", 
          "theoretical findings", 
          "numerical results", 
          "Hessian", 
          "approximation", 
          "cubic model", 
          "regularization", 
          "Lipschitz", 
          "optimization", 
          "function", 
          "matrix", 
          "parameters", 
          "accuracy", 
          "dimensions", 
          "model", 
          "version", 
          "point", 
          "domain", 
          "criteria", 
          "results", 
          "search criteria", 
          "evaluation", 
          "findings", 
          "method", 
          "paper"
        ], 
        "name": "A cubic regularization of Newton\u2019s method with finite difference Hessian approximations", 
        "pagination": "1-24", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1141849951"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11075-021-01200-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11075-021-01200-y", 
          "https://app.dimensions.ai/details/publication/pub.1141849951"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T10:27", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_887.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11075-021-01200-y"
      }
    ]
     

    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/s11075-021-01200-y'

    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/s11075-021-01200-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11075-021-01200-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11075-021-01200-y'


     

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

    152 TRIPLES      22 PREDICATES      71 URIs      52 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11075-021-01200-y schema:about anzsrc-for:01
    2 anzsrc-for:0103
    3 schema:author Ncdcd98df280c47af81de146e89f63a10
    4 schema:citation sg:pub.10.1007/bf01456804
    5 sg:pub.10.1007/s00180-017-0765-8
    6 sg:pub.10.1007/s10107-006-0706-8
    7 sg:pub.10.1007/s10107-009-0286-5
    8 sg:pub.10.1007/s10107-009-0337-y
    9 sg:pub.10.1007/s10107-016-1026-2
    10 sg:pub.10.1007/s10107-016-1065-8
    11 sg:pub.10.1007/s10107-019-01406-y
    12 sg:pub.10.1007/s10589-017-9928-3
    13 sg:pub.10.1007/s10898-016-0475-8
    14 sg:pub.10.1007/s10957-018-1341-2
    15 schema:datePublished 2021-10-13
    16 schema:datePublishedReg 2021-10-13
    17 schema:description In this paper, we present a version of the cubic regularization of Newton’s method for unconstrained nonconvex optimization, in which the Hessian matrices are approximated by forward finite difference Hessians. The regularization parameter of the cubic models and the accuracy of the Hessian approximations are jointly adjusted using a nonmonotone line search criterion. Assuming that the Hessian of the objective function is globally Lipschitz continuous, we show that the proposed method needs at most On𝜖−3/2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {O}\left (n\epsilon ^{-3/2}\right )$\end{document} function and gradient evaluations to generate an 𝜖-approximate stationary point, where n is the dimension of the domain of the objective function. Preliminary numerical results corroborate our theoretical findings.
    18 schema:genre article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf sg:journal.1050467
    22 schema:keywords Hessian
    23 Hessian approximation
    24 Hessian matrix
    25 Lipschitz
    26 Newton method
    27 accuracy
    28 approximate stationary point
    29 approximation
    30 criteria
    31 cubic model
    32 cubic regularization
    33 dimensions
    34 domain
    35 evaluation
    36 findings
    37 function
    38 gradient evaluations
    39 line search criterion
    40 matrix
    41 method
    42 model
    43 nonconvex optimization
    44 numerical results
    45 objective function
    46 optimization
    47 paper
    48 parameters
    49 point
    50 preliminary numerical results
    51 regularization
    52 regularization parameter
    53 results
    54 search criteria
    55 stationary points
    56 theoretical findings
    57 unconstrained nonconvex optimization
    58 version
    59 schema:name A cubic regularization of Newton’s method with finite difference Hessian approximations
    60 schema:pagination 1-24
    61 schema:productId N44506910c0914a9da624cc11c4cc61d6
    62 Nf2edbc0a9c6c4c1192dd4fb13ce8bb4b
    63 schema:sameAs https://app.dimensions.ai/details/publication/pub.1141849951
    64 https://doi.org/10.1007/s11075-021-01200-y
    65 schema:sdDatePublished 2022-05-10T10:27
    66 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    67 schema:sdPublisher N6f3d681a75c246babb30c1da11b39340
    68 schema:url https://doi.org/10.1007/s11075-021-01200-y
    69 sgo:license sg:explorer/license/
    70 sgo:sdDataset articles
    71 rdf:type schema:ScholarlyArticle
    72 N44506910c0914a9da624cc11c4cc61d6 schema:name doi
    73 schema:value 10.1007/s11075-021-01200-y
    74 rdf:type schema:PropertyValue
    75 N5897e47c48594cb69e8f2c49b7a548c1 schema:affiliation grid-institutes:grid.411195.9
    76 schema:familyName Gonçalves
    77 schema:givenName M. L. N.
    78 rdf:type schema:Person
    79 N595e725623c848e1973ef42762591871 rdf:first sg:person.016672542147.21
    80 rdf:rest rdf:nil
    81 N6f3d681a75c246babb30c1da11b39340 schema:name Springer Nature - SN SciGraph project
    82 rdf:type schema:Organization
    83 Nbd3b8fc646034c26b490ffcff4de360a rdf:first N5897e47c48594cb69e8f2c49b7a548c1
    84 rdf:rest N595e725623c848e1973ef42762591871
    85 Ncdcd98df280c47af81de146e89f63a10 rdf:first sg:person.010427573717.89
    86 rdf:rest Nbd3b8fc646034c26b490ffcff4de360a
    87 Nf2edbc0a9c6c4c1192dd4fb13ce8bb4b schema:name dimensions_id
    88 schema:value pub.1141849951
    89 rdf:type schema:PropertyValue
    90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Mathematical Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Numerical and Computational Mathematics
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1050467 schema:issn 1017-1398
    97 1572-9265
    98 schema:name Numerical Algorithms
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.010427573717.89 schema:affiliation grid-institutes:grid.20736.30
    102 schema:familyName Grapiglia
    103 schema:givenName G. N.
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010427573717.89
    105 rdf:type schema:Person
    106 sg:person.016672542147.21 schema:affiliation grid-institutes:grid.472638.c
    107 schema:familyName Silva
    108 schema:givenName G. N.
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016672542147.21
    110 rdf:type schema:Person
    111 sg:pub.10.1007/bf01456804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023104003
    112 https://doi.org/10.1007/bf01456804
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/s00180-017-0765-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091817170
    115 https://doi.org/10.1007/s00180-017-0765-8
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/s10107-006-0706-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001889025
    118 https://doi.org/10.1007/s10107-006-0706-8
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/s10107-009-0286-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011221568
    121 https://doi.org/10.1007/s10107-009-0286-5
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/s10107-009-0337-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1007745891
    124 https://doi.org/10.1007/s10107-009-0337-y
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/s10107-016-1026-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008021320
    127 https://doi.org/10.1007/s10107-016-1026-2
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/s10107-016-1065-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007770754
    130 https://doi.org/10.1007/s10107-016-1065-8
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/s10107-019-01406-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1116870816
    133 https://doi.org/10.1007/s10107-019-01406-y
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/s10589-017-9928-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1090902476
    136 https://doi.org/10.1007/s10589-017-9928-3
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/s10898-016-0475-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008845437
    139 https://doi.org/10.1007/s10898-016-0475-8
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/s10957-018-1341-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105463477
    142 https://doi.org/10.1007/s10957-018-1341-2
    143 rdf:type schema:CreativeWork
    144 grid-institutes:grid.20736.30 schema:alternateName Departamento de Matemática, Universidade Federal do Paraná, Centro Politécnico, Cx. postal 19.081, 81531-980, Curitiba, PR, Brazil
    145 schema:name Departamento de Matemática, Universidade Federal do Paraná, Centro Politécnico, Cx. postal 19.081, 81531-980, Curitiba, PR, Brazil
    146 rdf:type schema:Organization
    147 grid-institutes:grid.411195.9 schema:alternateName IME, Universidade Federal de Goiás, Campus II- Cx. postal 131, 74001-970, Goiânia, GO, Brazil
    148 schema:name IME, Universidade Federal de Goiás, Campus II- Cx. postal 131, 74001-970, Goiânia, GO, Brazil
    149 rdf:type schema:Organization
    150 grid-institutes:grid.472638.c schema:alternateName Colegiado de Matemática, Universidade Federal do Oeste da Bahia, 47808-021, Barreiras, BA, Brazil
    151 schema:name Colegiado de Matemática, Universidade Federal do Oeste da Bahia, 47808-021, Barreiras, BA, Brazil
    152 rdf:type schema:Organization
     




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


    ...