On the cost of solving augmented Lagrangian subproblems View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-08

AUTHORS

Damián Fernández, Mikhail Solodov

ABSTRACT

At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two linear systems in the equality-constrained case). In other words, two inner Newtonian iterations are sufficient. To the best of our knowledge, such results are not available even under the strongest assumptions (of second-order sufficiency, strict complementarity, and the linear independence constraint qualification). Our analysis is performed under second-order sufficiency only, which is the weakest assumption for obtaining local convergence and rate of convergence of outer iterations of the augmented Lagrangian algorithm. The structure of the quadratic problems in question is related to the stabilized sequential quadratic programming and to second-order corrections. More... »

PAGES

1-19

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10107-019-01384-1

DOI

http://dx.doi.org/10.1007/s10107-019-01384-1

DIMENSIONS

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


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": "National University of C\u00f3rdoba", 
          "id": "https://www.grid.ac/institutes/grid.10692.3c", 
          "name": [
            "CIEM-CONICET and FaMAF, Universidad Nacional de C\u00f3rdoba, Medina Allende s/n, 5000, C\u00f3rdoba, Argentina"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fern\u00e1ndez", 
        "givenName": "Dami\u00e1n", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Instituto de Pesquisas Jardim Bot\u00e2nico do Rio de Janeiro", 
          "id": "https://www.grid.ac/institutes/grid.452542.0", 
          "name": [
            "IMPA \u2013 Instituto de Matem\u00e1tica Pura e Aplicada, Estrada Dona Castorina 110, Jardim Bot\u00e2nico, 22460-320, Rio de Janeiro, RJ, Brazil"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Solodov", 
        "givenName": "Mikhail", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1023/a:1008640419184", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002449132", 
          "https://doi.org/10.1023/a:1008640419184"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10589-012-9502-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006876046", 
          "https://doi.org/10.1007/s10589-012-9502-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10589-014-9658-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008576671", 
          "https://doi.org/10.1007/s10589-014-9658-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-008-0255-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011218940", 
          "https://doi.org/10.1007/s10107-008-0255-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-008-0255-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011218940", 
          "https://doi.org/10.1007/s10107-008-0255-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-002-0364-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011931685", 
          "https://doi.org/10.1007/s10107-002-0364-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10957-016-0889-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015047056", 
          "https://doi.org/10.1007/s10957-016-0889-y"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00927673", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018609722", 
          "https://doi.org/10.1007/bf00927673"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00927673", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018609722", 
          "https://doi.org/10.1007/bf00927673"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/10556780701577730", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028164163"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s101070050051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036132814", 
          "https://doi.org/10.1007/s101070050051"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-012-0586-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040096561", 
          "https://doi.org/10.1007/s10107-012-0586-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580138", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042457178", 
          "https://doi.org/10.1007/bf01580138"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580138", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042457178", 
          "https://doi.org/10.1007/bf01580138"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-006-0077-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045078655", 
          "https://doi.org/10.1007/s10107-006-0077-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-006-0077-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045078655", 
          "https://doi.org/10.1007/s10107-006-0077-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-016-1066-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046460114", 
          "https://doi.org/10.1007/s10107-016-1066-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-016-1066-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046460114", 
          "https://doi.org/10.1007/s10107-016-1066-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10589-015-9744-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048546065", 
          "https://doi.org/10.1007/s10589-015-9744-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1093/imanum/drw004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059689993"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/030601235", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842750"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/10081085x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062859514"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s1052623496305882", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062883561"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973365", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098553842"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-03-08", 
    "datePublishedReg": "2019-03-08", 
    "description": "At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two linear systems in the equality-constrained case). In other words, two inner Newtonian iterations are sufficient. To the best of our knowledge, such results are not available even under the strongest assumptions (of second-order sufficiency, strict complementarity, and the linear independence constraint qualification). Our analysis is performed under second-order sufficiency only, which is the weakest assumption for obtaining local convergence and rate of convergence of outer iterations of the augmented Lagrangian algorithm. The structure of the quadratic problems in question is related to the stabilized sequential quadratic programming and to second-order corrections.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10107-019-01384-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }
    ], 
    "name": "On the cost of solving augmented Lagrangian subproblems", 
    "pagination": "1-19", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8c05d5cc9b076978dd69cdf6ca7423230096d6c31a4ecd366c5d908a82dd59bf"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10107-019-01384-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112634109"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10107-019-01384-1", 
      "https://app.dimensions.ai/details/publication/pub.1112634109"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:19", 
    "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/0000000354_0000000354/records_11713_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10107-019-01384-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/s10107-019-01384-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/s10107-019-01384-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10107-019-01384-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10107-019-01384-1'


 

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

133 TRIPLES      21 PREDICATES      43 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10107-019-01384-1 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N946596a47fb74d6291ff144b2d87279e
4 schema:citation sg:pub.10.1007/bf00927673
5 sg:pub.10.1007/bf01580138
6 sg:pub.10.1007/s10107-002-0364-4
7 sg:pub.10.1007/s10107-006-0077-1
8 sg:pub.10.1007/s10107-008-0255-4
9 sg:pub.10.1007/s10107-012-0586-z
10 sg:pub.10.1007/s10107-016-1066-7
11 sg:pub.10.1007/s101070050051
12 sg:pub.10.1007/s10589-012-9502-y
13 sg:pub.10.1007/s10589-014-9658-8
14 sg:pub.10.1007/s10589-015-9744-6
15 sg:pub.10.1007/s10957-016-0889-y
16 sg:pub.10.1023/a:1008640419184
17 https://doi.org/10.1080/10556780701577730
18 https://doi.org/10.1093/imanum/drw004
19 https://doi.org/10.1137/030601235
20 https://doi.org/10.1137/1.9781611973365
21 https://doi.org/10.1137/10081085x
22 https://doi.org/10.1137/s1052623496305882
23 schema:datePublished 2019-03-08
24 schema:datePublishedReg 2019-03-08
25 schema:description At each iteration of the augmented Lagrangian algorithm, a nonlinear subproblem is being solved. The number of inner iterations (of some/any method) needed to obtain a solution of the subproblem, or even a suitable approximate stationary point, is in principle unknown. In this paper we show that to compute an approximate stationary point sufficient to guarantee local superlinear convergence of the augmented Lagrangian iterations, it is enough to solve two quadratic programming problems (or two linear systems in the equality-constrained case). In other words, two inner Newtonian iterations are sufficient. To the best of our knowledge, such results are not available even under the strongest assumptions (of second-order sufficiency, strict complementarity, and the linear independence constraint qualification). Our analysis is performed under second-order sufficiency only, which is the weakest assumption for obtaining local convergence and rate of convergence of outer iterations of the augmented Lagrangian algorithm. The structure of the quadratic problems in question is related to the stabilized sequential quadratic programming and to second-order corrections.
26 schema:genre research_article
27 schema:inLanguage en
28 schema:isAccessibleForFree false
29 schema:isPartOf sg:journal.1047630
30 schema:name On the cost of solving augmented Lagrangian subproblems
31 schema:pagination 1-19
32 schema:productId N4c105c0c93c94cf380ff5db7669957a1
33 N8a83148d4c174fd69ae5c89499d3e982
34 Nfae4da65f11540df8017f533bc6ebaf8
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112634109
36 https://doi.org/10.1007/s10107-019-01384-1
37 schema:sdDatePublished 2019-04-11T11:19
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher N4a952be4a399400daf5597253506b014
40 schema:url https://link.springer.com/10.1007%2Fs10107-019-01384-1
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N0f95692e5fe74d99b35fb957924e17a1 schema:affiliation https://www.grid.ac/institutes/grid.10692.3c
45 schema:familyName Fernández
46 schema:givenName Damián
47 rdf:type schema:Person
48 N4a952be4a399400daf5597253506b014 schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N4c105c0c93c94cf380ff5db7669957a1 schema:name dimensions_id
51 schema:value pub.1112634109
52 rdf:type schema:PropertyValue
53 N8a83148d4c174fd69ae5c89499d3e982 schema:name readcube_id
54 schema:value 8c05d5cc9b076978dd69cdf6ca7423230096d6c31a4ecd366c5d908a82dd59bf
55 rdf:type schema:PropertyValue
56 N946596a47fb74d6291ff144b2d87279e rdf:first N0f95692e5fe74d99b35fb957924e17a1
57 rdf:rest Ndfb909435035421dabbd4fcaad9de441
58 Na46bc49233e5417bac9d20fad4e6ca1d schema:affiliation https://www.grid.ac/institutes/grid.452542.0
59 schema:familyName Solodov
60 schema:givenName Mikhail
61 rdf:type schema:Person
62 Ndfb909435035421dabbd4fcaad9de441 rdf:first Na46bc49233e5417bac9d20fad4e6ca1d
63 rdf:rest rdf:nil
64 Nfae4da65f11540df8017f533bc6ebaf8 schema:name doi
65 schema:value 10.1007/s10107-019-01384-1
66 rdf:type schema:PropertyValue
67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
68 schema:name Mathematical Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
71 schema:name Numerical and Computational Mathematics
72 rdf:type schema:DefinedTerm
73 sg:journal.1047630 schema:issn 0025-5610
74 1436-4646
75 schema:name Mathematical Programming
76 rdf:type schema:Periodical
77 sg:pub.10.1007/bf00927673 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018609722
78 https://doi.org/10.1007/bf00927673
79 rdf:type schema:CreativeWork
80 sg:pub.10.1007/bf01580138 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042457178
81 https://doi.org/10.1007/bf01580138
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/s10107-002-0364-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011931685
84 https://doi.org/10.1007/s10107-002-0364-4
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/s10107-006-0077-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045078655
87 https://doi.org/10.1007/s10107-006-0077-1
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/s10107-008-0255-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011218940
90 https://doi.org/10.1007/s10107-008-0255-4
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/s10107-012-0586-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1040096561
93 https://doi.org/10.1007/s10107-012-0586-z
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/s10107-016-1066-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046460114
96 https://doi.org/10.1007/s10107-016-1066-7
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/s101070050051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036132814
99 https://doi.org/10.1007/s101070050051
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/s10589-012-9502-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1006876046
102 https://doi.org/10.1007/s10589-012-9502-y
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/s10589-014-9658-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008576671
105 https://doi.org/10.1007/s10589-014-9658-8
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/s10589-015-9744-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048546065
108 https://doi.org/10.1007/s10589-015-9744-6
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/s10957-016-0889-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1015047056
111 https://doi.org/10.1007/s10957-016-0889-y
112 rdf:type schema:CreativeWork
113 sg:pub.10.1023/a:1008640419184 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002449132
114 https://doi.org/10.1023/a:1008640419184
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1080/10556780701577730 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028164163
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1093/imanum/drw004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059689993
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/030601235 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842750
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/1.9781611973365 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098553842
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1137/10081085x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062859514
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/s1052623496305882 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883561
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.10692.3c schema:alternateName National University of Córdoba
129 schema:name CIEM-CONICET and FaMAF, Universidad Nacional de Córdoba, Medina Allende s/n, 5000, Córdoba, Argentina
130 rdf:type schema:Organization
131 https://www.grid.ac/institutes/grid.452542.0 schema:alternateName Instituto de Pesquisas Jardim Botânico do Rio de Janeiro
132 schema:name IMPA – Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, 22460-320, Rio de Janeiro, RJ, Brazil
133 rdf:type schema:Organization
 




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


...