On the complexity of following the central path of linear programs by linear extrapolation II View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1991-05

AUTHORS

G. Sonnevend, J. Stoer, G. Zhao

ABSTRACT

A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, δ) of steps needed to go from an initial pointx(R) to a final pointx(δ), R>δ>0, by an integral of the local “weighted curvature” of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr↓0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constmα log(R/δ), whereα < 1/2 e.g.α = 1/4 orα = 3/8 (note thatα = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only forα ⩾ 1/3.As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded. More... »

PAGES

527-553

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Angewandte Mathemaik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathemaik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, 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 Mathemaik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathemaik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Angewandte Mathemaik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathemaik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhao", 
        "givenName": "G.", 
        "id": "sg:person.011530401251.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011530401251.34"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-1-4613-9617-8_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019101691", 
          "https://doi.org/10.1007/978-1-4613-9617-8_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01594942", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012514764", 
          "https://doi.org/10.1007/bf01594942"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01582903", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053610614", 
          "https://doi.org/10.1007/bf01582903"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01445161", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022928088", 
          "https://doi.org/10.1007/bf01445161"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01586056", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050071136", 
          "https://doi.org/10.1007/bf01586056"
        ], 
        "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/978-1-4757-2108-9_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045410346", 
          "https://doi.org/10.1007/978-1-4757-2108-9_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0083587", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048822435", 
          "https://doi.org/10.1007/bfb0083587"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01587095", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014973872", 
          "https://doi.org/10.1007/bf01587095"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01904781", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010658891", 
          "https://doi.org/10.1007/bf01904781"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1991-05", 
    "datePublishedReg": "1991-05-01", 
    "description": "A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, \u03b4) of steps needed to go from an initial pointx(R) to a final pointx(\u03b4), R>\u03b4>0, by an integral of the local \u201cweighted curvature\u201d of the (primal\u2014dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr\u21930. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constm\u03b1 log(R/\u03b4), where\u03b1 < 1/2 e.g.\u03b1 = 1/4 or\u03b1 = 3/8 (note that\u03b1 = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only for\u03b1 \u2a7e 1/3.As a byproduct, many analytical and structural properties of the primal\u2014dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01582904", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "52"
      }
    ], 
    "keywords": [
      "central path", 
      "primal-dual central path", 
      "class of algorithms", 
      "linear programming problem", 
      "logarithmic penalty", 
      "Newton method", 
      "slack variables", 
      "explicit results", 
      "programming problem", 
      "convergence behavior", 
      "linear program", 
      "logarithmic derivative", 
      "large class", 
      "total numberN", 
      "central curve", 
      "related results", 
      "adaptive choice", 
      "integrals", 
      "problem", 
      "steplength", 
      "structural properties", 
      "curvature", 
      "linear extrapolation", 
      "complexity", 
      "above estimation", 
      "parameterR", 
      "class", 
      "numbern", 
      "path", 
      "estimation", 
      "algorithm", 
      "trajectories", 
      "close relation", 
      "dependence", 
      "extrapolation", 
      "variables", 
      "properties", 
      "point", 
      "quantity", 
      "latter", 
      "penalty", 
      "results", 
      "instances", 
      "curves", 
      "where\u03b1", 
      "number", 
      "derivatives", 
      "behavior", 
      "step", 
      "choice", 
      "relation", 
      "byproducts", 
      "family", 
      "program", 
      "method"
    ], 
    "name": "On the complexity of following the central path of linear programs by linear extrapolation II", 
    "pagination": "527-553", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1003736353"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01582904"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01582904", 
      "https://app.dimensions.ai/details/publication/pub.1003736353"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-06-01T21:59", 
    "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_237.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01582904"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

167 TRIPLES      22 PREDICATES      91 URIs      73 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01582904 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5b9fcb0b9e1444d6832713585be51a23
4 schema:citation sg:pub.10.1007/978-1-4613-9617-8_1
5 sg:pub.10.1007/978-1-4757-2108-9_14
6 sg:pub.10.1007/bf01445161
7 sg:pub.10.1007/bf01582903
8 sg:pub.10.1007/bf01586056
9 sg:pub.10.1007/bf01587095
10 sg:pub.10.1007/bf01594942
11 sg:pub.10.1007/bf01904781
12 sg:pub.10.1007/bfb0042223
13 sg:pub.10.1007/bfb0083587
14 schema:datePublished 1991-05
15 schema:datePublishedReg 1991-05-01
16 schema:description A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, δ) of steps needed to go from an initial pointx(R) to a final pointx(δ), R>δ>0, by an integral of the local “weighted curvature” of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr↓0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constmα log(R/δ), whereα < 1/2 e.g.α = 1/4 orα = 3/8 (note thatα = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only forα ⩾ 1/3.As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.
17 schema:genre article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N96779138e9eb4a919722093219d717e6
21 Nca317a582a0c4e07abd17ad7cbdf69d6
22 sg:journal.1047630
23 schema:keywords Newton method
24 above estimation
25 adaptive choice
26 algorithm
27 behavior
28 byproducts
29 central curve
30 central path
31 choice
32 class
33 class of algorithms
34 close relation
35 complexity
36 convergence behavior
37 curvature
38 curves
39 dependence
40 derivatives
41 estimation
42 explicit results
43 extrapolation
44 family
45 instances
46 integrals
47 large class
48 latter
49 linear extrapolation
50 linear program
51 linear programming problem
52 logarithmic derivative
53 logarithmic penalty
54 method
55 number
56 numbern
57 parameterR
58 path
59 penalty
60 point
61 primal-dual central path
62 problem
63 program
64 programming problem
65 properties
66 quantity
67 related results
68 relation
69 results
70 slack variables
71 step
72 steplength
73 structural properties
74 total numberN
75 trajectories
76 variables
77 whereα
78 schema:name On the complexity of following the central path of linear programs by linear extrapolation II
79 schema:pagination 527-553
80 schema:productId N261c7cf2033142b49cd728e0bd7f1476
81 N3aa5673d0a1647a59c1b7fc18f7fe966
82 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003736353
83 https://doi.org/10.1007/bf01582904
84 schema:sdDatePublished 2022-06-01T21:59
85 schema:sdLicense https://scigraph.springernature.com/explorer/license/
86 schema:sdPublisher N129dcd5073c54e9ab6aa909cc63245b0
87 schema:url https://doi.org/10.1007/bf01582904
88 sgo:license sg:explorer/license/
89 sgo:sdDataset articles
90 rdf:type schema:ScholarlyArticle
91 N129dcd5073c54e9ab6aa909cc63245b0 schema:name Springer Nature - SN SciGraph project
92 rdf:type schema:Organization
93 N261c7cf2033142b49cd728e0bd7f1476 schema:name doi
94 schema:value 10.1007/bf01582904
95 rdf:type schema:PropertyValue
96 N3aa5673d0a1647a59c1b7fc18f7fe966 schema:name dimensions_id
97 schema:value pub.1003736353
98 rdf:type schema:PropertyValue
99 N4b861b4747a249e18cf59a26bde83359 rdf:first sg:person.011530401251.34
100 rdf:rest rdf:nil
101 N5b9fcb0b9e1444d6832713585be51a23 rdf:first sg:person.010104416602.18
102 rdf:rest N97c0d69776fa4170b6948e9aee80629e
103 N96779138e9eb4a919722093219d717e6 schema:issueNumber 1-3
104 rdf:type schema:PublicationIssue
105 N97c0d69776fa4170b6948e9aee80629e rdf:first sg:person.011465456275.61
106 rdf:rest N4b861b4747a249e18cf59a26bde83359
107 Nca317a582a0c4e07abd17ad7cbdf69d6 schema:volumeNumber 52
108 rdf:type schema:PublicationVolume
109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
110 schema:name Information and Computing Sciences
111 rdf:type schema:DefinedTerm
112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
113 schema:name Computation Theory and Mathematics
114 rdf:type schema:DefinedTerm
115 sg:journal.1047630 schema:issn 0025-5610
116 1436-4646
117 schema:name Mathematical Programming
118 schema:publisher Springer Nature
119 rdf:type schema:Periodical
120 sg:person.010104416602.18 schema:affiliation grid-institutes:grid.8379.5
121 schema:familyName Sonnevend
122 schema:givenName G.
123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010104416602.18
124 rdf:type schema:Person
125 sg:person.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
126 schema:familyName Stoer
127 schema:givenName J.
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
129 rdf:type schema:Person
130 sg:person.011530401251.34 schema:affiliation grid-institutes:grid.8379.5
131 schema:familyName Zhao
132 schema:givenName G.
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011530401251.34
134 rdf:type schema:Person
135 sg:pub.10.1007/978-1-4613-9617-8_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019101691
136 https://doi.org/10.1007/978-1-4613-9617-8_1
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/978-1-4757-2108-9_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045410346
139 https://doi.org/10.1007/978-1-4757-2108-9_14
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/bf01445161 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022928088
142 https://doi.org/10.1007/bf01445161
143 rdf:type schema:CreativeWork
144 sg:pub.10.1007/bf01582903 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053610614
145 https://doi.org/10.1007/bf01582903
146 rdf:type schema:CreativeWork
147 sg:pub.10.1007/bf01586056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050071136
148 https://doi.org/10.1007/bf01586056
149 rdf:type schema:CreativeWork
150 sg:pub.10.1007/bf01587095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014973872
151 https://doi.org/10.1007/bf01587095
152 rdf:type schema:CreativeWork
153 sg:pub.10.1007/bf01594942 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012514764
154 https://doi.org/10.1007/bf01594942
155 rdf:type schema:CreativeWork
156 sg:pub.10.1007/bf01904781 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010658891
157 https://doi.org/10.1007/bf01904781
158 rdf:type schema:CreativeWork
159 sg:pub.10.1007/bfb0042223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045273451
160 https://doi.org/10.1007/bfb0042223
161 rdf:type schema:CreativeWork
162 sg:pub.10.1007/bfb0083587 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048822435
163 https://doi.org/10.1007/bfb0083587
164 rdf:type schema:CreativeWork
165 grid-institutes:grid.8379.5 schema:alternateName Institut für Angewandte Mathemaik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany
166 schema:name Institut für Angewandte Mathemaik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany
167 rdf:type schema:Organization
 




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


...