Global ellipsoidal approximations and homotopy methods for solving convex analytic programs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1990-01

AUTHORS

G. Sonnevend, J. Stoer

ABSTRACT

This paper deals with some problems of algorithmic complexity arising when solving convex programming problems by following the path of analytic centers (i.e., the trajectory formed by the minimizers of the logarithmic barrier function). We prove that in the case ofm convex quadratic constraints we can obtain in a simple constructive way a two-sided ellipsoidal approximation for the feasible set (intersection ofm ellipsoids), whose tightness depends only onm. This can be used for the early identification of those constraints which are active at the optimum, and it also explains the efficiency of Newton's method used as a corrector when following the central path. Various parametrizations of the central path are studied. This also leads to an extrapolation (predictor) algorithm which can be regarded as a generalization of the method of conjugate gradients. More... »

PAGES

139-165

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Institut f\u00fcr Angewandte Mathematik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, D-8700, W\u00fcrzburg, West Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathematik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, D-8700, W\u00fcrzburg, West Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sonnevend", 
        "givenName": "G.", 
        "id": "sg:person.010104416602.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010104416602.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Angewandte Mathematik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, D-8700, W\u00fcrzburg, West Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathematik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, D-8700, W\u00fcrzburg, West Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stoer", 
        "givenName": "J.", 
        "id": "sg:person.011465456275.61", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02165238", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006395107", 
          "https://doi.org/10.1007/bf02165238"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-0348-9297-1_20", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014295173", 
          "https://doi.org/10.1007/978-3-0348-9297-1_20"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02579150", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035950209", 
          "https://doi.org/10.1007/bf02579150"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0042223", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045273451", 
          "https://doi.org/10.1007/bfb0042223"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840457", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016603453", 
          "https://doi.org/10.1007/bf01840457"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0043914", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021827905", 
          "https://doi.org/10.1007/bfb0043914"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01588796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042006649", 
          "https://doi.org/10.1007/bf01588796"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580848", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022571826", 
          "https://doi.org/10.1007/bf01580848"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1990-01", 
    "datePublishedReg": "1990-01-01", 
    "description": "This paper deals with some problems of algorithmic complexity arising when solving convex programming problems by following the path of analytic centers (i.e., the trajectory formed by the minimizers of the logarithmic barrier function). We prove that in the case ofm convex quadratic constraints we can obtain in a simple constructive way a two-sided ellipsoidal approximation for the feasible set (intersection ofm ellipsoids), whose tightness depends only onm. This can be used for the early identification of those constraints which are active at the optimum, and it also explains the efficiency of Newton's method used as a corrector when following the central path. Various parametrizations of the central path are studied. This also leads to an extrapolation (predictor) algorithm which can be regarded as a generalization of the method of conjugate gradients.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01445161", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1120592", 
        "issn": [
          "0095-4616", 
          "1432-0606"
        ], 
        "name": "Applied Mathematics & Optimization", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "21"
      }
    ], 
    "keywords": [
      "ellipsoidal approximation", 
      "central path", 
      "convex quadratic constraints", 
      "convex programming problem", 
      "quadratic constraints", 
      "homotopy method", 
      "Newton method", 
      "analytic center", 
      "feasible set", 
      "programming problem", 
      "extrapolation algorithm", 
      "algorithmic complexity", 
      "approximation", 
      "constructive way", 
      "constraints", 
      "problem", 
      "parametrization", 
      "generalization", 
      "path", 
      "algorithm", 
      "corrector", 
      "optimum", 
      "complexity", 
      "set", 
      "analytics programs", 
      "gradient", 
      "tightness", 
      "efficiency", 
      "cases", 
      "way", 
      "identification", 
      "center", 
      "program", 
      "early identification", 
      "method", 
      "paper"
    ], 
    "name": "Global ellipsoidal approximations and homotopy methods for solving convex analytic programs", 
    "pagination": "139-165", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022928088"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01445161"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01445161", 
      "https://app.dimensions.ai/details/publication/pub.1022928088"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-08-04T16:51", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/article/article_256.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01445161"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

132 TRIPLES      21 PREDICATES      69 URIs      53 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01445161 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N83529addbc13477aa28b6e3c7c178cba
4 schema:citation sg:pub.10.1007/978-3-0348-9297-1_20
5 sg:pub.10.1007/bf01580848
6 sg:pub.10.1007/bf01588796
7 sg:pub.10.1007/bf01840457
8 sg:pub.10.1007/bf02165238
9 sg:pub.10.1007/bf02579150
10 sg:pub.10.1007/bfb0042223
11 sg:pub.10.1007/bfb0043914
12 schema:datePublished 1990-01
13 schema:datePublishedReg 1990-01-01
14 schema:description This paper deals with some problems of algorithmic complexity arising when solving convex programming problems by following the path of analytic centers (i.e., the trajectory formed by the minimizers of the logarithmic barrier function). We prove that in the case ofm convex quadratic constraints we can obtain in a simple constructive way a two-sided ellipsoidal approximation for the feasible set (intersection ofm ellipsoids), whose tightness depends only onm. This can be used for the early identification of those constraints which are active at the optimum, and it also explains the efficiency of Newton's method used as a corrector when following the central path. Various parametrizations of the central path are studied. This also leads to an extrapolation (predictor) algorithm which can be regarded as a generalization of the method of conjugate gradients.
15 schema:genre article
16 schema:isAccessibleForFree false
17 schema:isPartOf N3a6993a2273f4bbda1f6140e4d4b9132
18 Nd6a5b06c6b2d43a8bf4d65f0c67ab522
19 sg:journal.1120592
20 schema:keywords Newton method
21 algorithm
22 algorithmic complexity
23 analytic center
24 analytics programs
25 approximation
26 cases
27 center
28 central path
29 complexity
30 constraints
31 constructive way
32 convex programming problem
33 convex quadratic constraints
34 corrector
35 early identification
36 efficiency
37 ellipsoidal approximation
38 extrapolation algorithm
39 feasible set
40 generalization
41 gradient
42 homotopy method
43 identification
44 method
45 optimum
46 paper
47 parametrization
48 path
49 problem
50 program
51 programming problem
52 quadratic constraints
53 set
54 tightness
55 way
56 schema:name Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
57 schema:pagination 139-165
58 schema:productId N599e40f4e0324b9e816b1d3b30faab23
59 Nac7b43c45b1743a2bc902411c6381404
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022928088
61 https://doi.org/10.1007/bf01445161
62 schema:sdDatePublished 2022-08-04T16:51
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N7a4b1745d27149a69d5f6fc06bc17eeb
65 schema:url https://doi.org/10.1007/bf01445161
66 sgo:license sg:explorer/license/
67 sgo:sdDataset articles
68 rdf:type schema:ScholarlyArticle
69 N3a6993a2273f4bbda1f6140e4d4b9132 schema:issueNumber 1
70 rdf:type schema:PublicationIssue
71 N599e40f4e0324b9e816b1d3b30faab23 schema:name dimensions_id
72 schema:value pub.1022928088
73 rdf:type schema:PropertyValue
74 N7a4b1745d27149a69d5f6fc06bc17eeb schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N83529addbc13477aa28b6e3c7c178cba rdf:first sg:person.010104416602.18
77 rdf:rest Nb26b933e41374f5fb242a3f4249832b0
78 Nac7b43c45b1743a2bc902411c6381404 schema:name doi
79 schema:value 10.1007/bf01445161
80 rdf:type schema:PropertyValue
81 Nb26b933e41374f5fb242a3f4249832b0 rdf:first sg:person.011465456275.61
82 rdf:rest rdf:nil
83 Nd6a5b06c6b2d43a8bf4d65f0c67ab522 schema:volumeNumber 21
84 rdf:type schema:PublicationVolume
85 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
86 schema:name Mathematical Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
89 schema:name Numerical and Computational Mathematics
90 rdf:type schema:DefinedTerm
91 sg:journal.1120592 schema:issn 0095-4616
92 1432-0606
93 schema:name Applied Mathematics & Optimization
94 schema:publisher Springer Nature
95 rdf:type schema:Periodical
96 sg:person.010104416602.18 schema:affiliation grid-institutes:grid.8379.5
97 schema:familyName Sonnevend
98 schema:givenName G.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010104416602.18
100 rdf:type schema:Person
101 sg:person.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
102 schema:familyName Stoer
103 schema:givenName J.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
105 rdf:type schema:Person
106 sg:pub.10.1007/978-3-0348-9297-1_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014295173
107 https://doi.org/10.1007/978-3-0348-9297-1_20
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/bf01580848 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022571826
110 https://doi.org/10.1007/bf01580848
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/bf01588796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042006649
113 https://doi.org/10.1007/bf01588796
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/bf01840457 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016603453
116 https://doi.org/10.1007/bf01840457
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/bf02165238 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006395107
119 https://doi.org/10.1007/bf02165238
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bf02579150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035950209
122 https://doi.org/10.1007/bf02579150
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/bfb0042223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045273451
125 https://doi.org/10.1007/bfb0042223
126 rdf:type schema:CreativeWork
127 sg:pub.10.1007/bfb0043914 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021827905
128 https://doi.org/10.1007/bfb0043914
129 rdf:type schema:CreativeWork
130 grid-institutes:grid.8379.5 schema:alternateName Institut für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, D-8700, Würzburg, West Germany
131 schema:name Institut für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, D-8700, Würzburg, West Germany
132 rdf:type schema:Organization
 




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


...