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/bf01588796", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042006649", 
          "https://doi.org/10.1007/bf01588796"
        ], 
        "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/bf01580848", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022571826", 
          "https://doi.org/10.1007/bf01580848"
        ], 
        "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/bf02165238", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006395107", 
          "https://doi.org/10.1007/bf02165238"
        ], 
        "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/bfb0043914", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021827905", 
          "https://doi.org/10.1007/bfb0043914"
        ], 
        "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"
      }
    ], 
    "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", 
    "inLanguage": "en", 
    "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", 
      "analytics programs", 
      "set", 
      "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-06-01T21:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_223.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.

133 TRIPLES      22 PREDICATES      70 URIs      54 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 Nc0d87b21d0b448b3b435bdd499a395b3
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:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N7308e03632ad4284a60e489084d39efe
19 Nba86eaa2edbd490eb356e9b8210ded70
20 sg:journal.1120592
21 schema:keywords Newton method
22 algorithm
23 algorithmic complexity
24 analytic center
25 analytics programs
26 approximation
27 cases
28 center
29 central path
30 complexity
31 constraints
32 constructive way
33 convex programming problem
34 convex quadratic constraints
35 corrector
36 early identification
37 efficiency
38 ellipsoidal approximation
39 extrapolation algorithm
40 feasible set
41 generalization
42 gradient
43 homotopy method
44 identification
45 method
46 optimum
47 paper
48 parametrization
49 path
50 problem
51 program
52 programming problem
53 quadratic constraints
54 set
55 tightness
56 way
57 schema:name Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
58 schema:pagination 139-165
59 schema:productId N8bbf851daee24161b5225ebace258b7f
60 N9cd1ab75d29a45bf841da91d811c0131
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022928088
62 https://doi.org/10.1007/bf01445161
63 schema:sdDatePublished 2022-06-01T21:58
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N153e2dec350b476080a61a77f728794f
66 schema:url https://doi.org/10.1007/bf01445161
67 sgo:license sg:explorer/license/
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N153e2dec350b476080a61a77f728794f schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N5ecd45fa540340cc8cfd68770245d4c8 rdf:first sg:person.011465456275.61
73 rdf:rest rdf:nil
74 N7308e03632ad4284a60e489084d39efe schema:volumeNumber 21
75 rdf:type schema:PublicationVolume
76 N8bbf851daee24161b5225ebace258b7f schema:name dimensions_id
77 schema:value pub.1022928088
78 rdf:type schema:PropertyValue
79 N9cd1ab75d29a45bf841da91d811c0131 schema:name doi
80 schema:value 10.1007/bf01445161
81 rdf:type schema:PropertyValue
82 Nba86eaa2edbd490eb356e9b8210ded70 schema:issueNumber 1
83 rdf:type schema:PublicationIssue
84 Nc0d87b21d0b448b3b435bdd499a395b3 rdf:first sg:person.010104416602.18
85 rdf:rest N5ecd45fa540340cc8cfd68770245d4c8
86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
87 schema:name Mathematical Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
90 schema:name Numerical and Computational Mathematics
91 rdf:type schema:DefinedTerm
92 sg:journal.1120592 schema:issn 0095-4616
93 1432-0606
94 schema:name Applied Mathematics & Optimization
95 schema:publisher Springer Nature
96 rdf:type schema:Periodical
97 sg:person.010104416602.18 schema:affiliation grid-institutes:grid.8379.5
98 schema:familyName Sonnevend
99 schema:givenName G.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010104416602.18
101 rdf:type schema:Person
102 sg:person.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
103 schema:familyName Stoer
104 schema:givenName J.
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
106 rdf:type schema:Person
107 sg:pub.10.1007/978-3-0348-9297-1_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014295173
108 https://doi.org/10.1007/978-3-0348-9297-1_20
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/bf01580848 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022571826
111 https://doi.org/10.1007/bf01580848
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/bf01588796 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042006649
114 https://doi.org/10.1007/bf01588796
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/bf01840457 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016603453
117 https://doi.org/10.1007/bf01840457
118 rdf:type schema:CreativeWork
119 sg:pub.10.1007/bf02165238 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006395107
120 https://doi.org/10.1007/bf02165238
121 rdf:type schema:CreativeWork
122 sg:pub.10.1007/bf02579150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035950209
123 https://doi.org/10.1007/bf02579150
124 rdf:type schema:CreativeWork
125 sg:pub.10.1007/bfb0042223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045273451
126 https://doi.org/10.1007/bfb0042223
127 rdf:type schema:CreativeWork
128 sg:pub.10.1007/bfb0043914 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021827905
129 https://doi.org/10.1007/bfb0043914
130 rdf:type schema:CreativeWork
131 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
132 schema:name Institut für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, D-8700, Würzburg, West Germany
133 rdf:type schema:Organization
 




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


...