An inexact Newton method for nonconvex equality constrained optimization View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-04

AUTHORS

Richard H. Byrd, Frank E. Curtis, Jorge Nocedal

ABSTRACT

We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal–dual iteration matrix. Negative curvature may arise from second-order information of the problem functions, but in fact exact second derivatives are not required in the approach. The complete algorithm is characterized by its emphasis on sufficient reductions in a model of an exact penalty function. We analyze the global behavior of the algorithm and present numerical results on a collection of test problems. More... »

PAGES

273

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10107-008-0248-3

DOI

http://dx.doi.org/10.1007/s10107-008-0248-3

DIMENSIONS

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


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": "University of Colorado Boulder", 
          "id": "https://www.grid.ac/institutes/grid.266190.a", 
          "name": [
            "Department of Computer Science, University of Colorado, 80309, Boulder, CO, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Byrd", 
        "givenName": "Richard H.", 
        "id": "sg:person.01213635733.38", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01213635733.38"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Northwestern University", 
          "id": "https://www.grid.ac/institutes/grid.16753.36", 
          "name": [
            "Department of Industrial Engineering and Management Sciences, Northwestern University, 60208, Evanston, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Curtis", 
        "givenName": "Frank E.", 
        "id": "sg:person.016631330455.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016631330455.40"
        ], 
        "type": "Person"
      }, 
      {
        "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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-69777-0_73", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010383877", 
          "https://doi.org/10.1007/978-3-540-69777-0_73"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1008677427361", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014509349", 
          "https://doi.org/10.1023/a:1008677427361"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/200979.201043", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017765448"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02192282", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019371171", 
          "https://doi.org/10.1007/bf02192282"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02192282", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019371171", 
          "https://doi.org/10.1007/bf02192282"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s101070050066", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026863026", 
          "https://doi.org/10.1007/s101070050066"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s101070100263", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040788378", 
          "https://doi.org/10.1007/s101070100263"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/962437.962439", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041348218"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-002-0360-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046895990", 
          "https://doi.org/10.1007/s10107-002-0360-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/060674004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062849845"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0712047", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062852294"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0907058", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062855843"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s1052623494276026", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062883465"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s1052623499361543", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062883749"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.1050.0150", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064722811"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/moor.23.3.746", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064724158"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9780898719857", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098555834"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010-04", 
    "datePublishedReg": "2010-04-01", 
    "description": "We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351\u2013369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal\u2013dual iteration matrix. Negative curvature may arise from second-order information of the problem functions, but in fact exact second derivatives are not required in the approach. The complete algorithm is characterized by its emphasis on sufficient reductions in a model of an exact penalty function. We analyze the global behavior of the algorithm and present numerical results on a collection of test problems.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10107-008-0248-3", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "122"
      }
    ], 
    "name": "An inexact Newton method for nonconvex equality constrained optimization", 
    "pagination": "273", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f71beb7b600a14c2ee4f338b8589cbcd45025522ddf814d1cc13b098c7b16e54"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10107-008-0248-3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051876321"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10107-008-0248-3", 
      "https://app.dimensions.ai/details/publication/pub.1051876321"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T14:25", 
    "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/0000000373_0000000373/records_13068_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs10107-008-0248-3"
  }
]
 

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-008-0248-3'

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-008-0248-3'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10107-008-0248-3'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10107-008-0248-3'


 

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

133 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10107-008-0248-3 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Ne7b34297f8b84b94a4407eb4eee93e4a
4 schema:citation sg:pub.10.1007/978-3-540-69777-0_73
5 sg:pub.10.1007/bf02192282
6 sg:pub.10.1007/s10107-002-0360-8
7 sg:pub.10.1007/s101070050066
8 sg:pub.10.1007/s101070100263
9 sg:pub.10.1023/a:1008677427361
10 https://doi.org/10.1137/060674004
11 https://doi.org/10.1137/0712047
12 https://doi.org/10.1137/0907058
13 https://doi.org/10.1137/1.9780898719857
14 https://doi.org/10.1137/s1052623494276026
15 https://doi.org/10.1137/s1052623499361543
16 https://doi.org/10.1145/200979.201043
17 https://doi.org/10.1145/962437.962439
18 https://doi.org/10.1287/moor.1050.0150
19 https://doi.org/10.1287/moor.23.3.746
20 schema:datePublished 2010-04
21 schema:datePublishedReg 2010-04-01
22 schema:description We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351–369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal–dual iteration matrix. Negative curvature may arise from second-order information of the problem functions, but in fact exact second derivatives are not required in the approach. The complete algorithm is characterized by its emphasis on sufficient reductions in a model of an exact penalty function. We analyze the global behavior of the algorithm and present numerical results on a collection of test problems.
23 schema:genre research_article
24 schema:inLanguage en
25 schema:isAccessibleForFree true
26 schema:isPartOf N25d8218300ac44ca8bfe4a7b1e249e1e
27 Ne534017be3c946e395b8d2cc500a9869
28 sg:journal.1047630
29 schema:name An inexact Newton method for nonconvex equality constrained optimization
30 schema:pagination 273
31 schema:productId Nc978610cae9f4ae2873cb4504fecc983
32 Ndecd71ec4ee5499798f6293de7349c64
33 Nf84fa92785b242cbaf91471dbe2a47df
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051876321
35 https://doi.org/10.1007/s10107-008-0248-3
36 schema:sdDatePublished 2019-04-11T14:25
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher N46e96467bf9d44ffbb1cea65da6b6ec2
39 schema:url http://link.springer.com/10.1007%2Fs10107-008-0248-3
40 sgo:license sg:explorer/license/
41 sgo:sdDataset articles
42 rdf:type schema:ScholarlyArticle
43 N25d8218300ac44ca8bfe4a7b1e249e1e schema:volumeNumber 122
44 rdf:type schema:PublicationVolume
45 N2e0eac96eeaf437fbb98f9b11771cf15 rdf:first sg:person.016631330455.40
46 rdf:rest Nc8f2554143534d3f859db8fc31614aad
47 N46e96467bf9d44ffbb1cea65da6b6ec2 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 Nc8f2554143534d3f859db8fc31614aad rdf:first sg:person.01157306714.71
50 rdf:rest rdf:nil
51 Nc978610cae9f4ae2873cb4504fecc983 schema:name doi
52 schema:value 10.1007/s10107-008-0248-3
53 rdf:type schema:PropertyValue
54 Ndecd71ec4ee5499798f6293de7349c64 schema:name readcube_id
55 schema:value f71beb7b600a14c2ee4f338b8589cbcd45025522ddf814d1cc13b098c7b16e54
56 rdf:type schema:PropertyValue
57 Ne534017be3c946e395b8d2cc500a9869 schema:issueNumber 2
58 rdf:type schema:PublicationIssue
59 Ne7b34297f8b84b94a4407eb4eee93e4a rdf:first sg:person.01213635733.38
60 rdf:rest N2e0eac96eeaf437fbb98f9b11771cf15
61 Nf84fa92785b242cbaf91471dbe2a47df schema:name dimensions_id
62 schema:value pub.1051876321
63 rdf:type schema:PropertyValue
64 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
65 schema:name Mathematical Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
68 schema:name Numerical and Computational Mathematics
69 rdf:type schema:DefinedTerm
70 sg:journal.1047630 schema:issn 0025-5610
71 1436-4646
72 schema:name Mathematical Programming
73 rdf:type schema:Periodical
74 sg:person.01157306714.71 schema:affiliation https://www.grid.ac/institutes/grid.16753.36
75 schema:familyName Nocedal
76 schema:givenName Jorge
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01157306714.71
78 rdf:type schema:Person
79 sg:person.01213635733.38 schema:affiliation https://www.grid.ac/institutes/grid.266190.a
80 schema:familyName Byrd
81 schema:givenName Richard H.
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01213635733.38
83 rdf:type schema:Person
84 sg:person.016631330455.40 schema:affiliation https://www.grid.ac/institutes/grid.16753.36
85 schema:familyName Curtis
86 schema:givenName Frank E.
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016631330455.40
88 rdf:type schema:Person
89 sg:pub.10.1007/978-3-540-69777-0_73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010383877
90 https://doi.org/10.1007/978-3-540-69777-0_73
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/bf02192282 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019371171
93 https://doi.org/10.1007/bf02192282
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/s10107-002-0360-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046895990
96 https://doi.org/10.1007/s10107-002-0360-8
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/s101070050066 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026863026
99 https://doi.org/10.1007/s101070050066
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/s101070100263 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040788378
102 https://doi.org/10.1007/s101070100263
103 rdf:type schema:CreativeWork
104 sg:pub.10.1023/a:1008677427361 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014509349
105 https://doi.org/10.1023/a:1008677427361
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1137/060674004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062849845
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1137/0712047 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062852294
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/0907058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062855843
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1137/1.9780898719857 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098555834
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1137/s1052623494276026 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883465
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1137/s1052623499361543 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883749
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/200979.201043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017765448
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/962437.962439 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041348218
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1287/moor.1050.0150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064722811
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1287/moor.23.3.746 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064724158
126 rdf:type schema:CreativeWork
127 https://www.grid.ac/institutes/grid.16753.36 schema:alternateName Northwestern University
128 schema:name Department of Electrical Engineering and Computer Science, Northwestern University, 60208, Evanston, IL, USA
129 Department of Industrial Engineering and Management Sciences, Northwestern University, 60208, Evanston, IL, USA
130 rdf:type schema:Organization
131 https://www.grid.ac/institutes/grid.266190.a schema:alternateName University of Colorado Boulder
132 schema:name Department of Computer Science, University of Colorado, 80309, Boulder, CO, USA
133 rdf:type schema:Organization
 




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


...