Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1993-01

AUTHORS

G. Zhao, J. Stoer

ABSTRACT

In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a “long” step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral. More... »

PAGES

85-103

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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, W-8700, W\u00fcrzburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathematik 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"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Angewandte Mathematik 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 Mathematik 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"
      }
    ], 
    "citation": [
      {
        "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/bf01580724", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028120387", 
          "https://doi.org/10.1007/bf01580724"
        ], 
        "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/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"
      }
    ], 
    "datePublished": "1993-01", 
    "datePublishedReg": "1993-01-01", 
    "description": "In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a \u201clong\u201d step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01182599", 
    "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": "27"
      }
    ], 
    "keywords": [
      "path-following method", 
      "curvature integral", 
      "primal-dual path-following method", 
      "primal-dual space", 
      "first-order methods", 
      "interior feasible solution", 
      "number of points", 
      "dual problem", 
      "linear program", 
      "optimal solution", 
      "second derivative", 
      "path parameters", 
      "integrals", 
      "particular class", 
      "feasible solution", 
      "weighted measure", 
      "trajectories", 
      "integrand", 
      "solution", 
      "class", 
      "iteration", 
      "complexity", 
      "space", 
      "problem", 
      "tangent", 
      "parameters", 
      "accuracy", 
      "point", 
      "step", 
      "order", 
      "number", 
      "respect", 
      "derivatives", 
      "gain", 
      "measures", 
      "program", 
      "method", 
      "paper"
    ], 
    "name": "Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals", 
    "pagination": "85-103", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053613854"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01182599"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01182599", 
      "https://app.dimensions.ai/details/publication/pub.1053613854"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-08-04T16:50", 
    "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_227.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01182599"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

126 TRIPLES      21 PREDICATES      69 URIs      55 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01182599 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N6055c8eee1ba466dae97ea664a3baa0b
4 schema:citation sg:pub.10.1007/bf01445161
5 sg:pub.10.1007/bf01580724
6 sg:pub.10.1007/bf01587095
7 sg:pub.10.1007/bf02579150
8 sg:pub.10.1007/bfb0042223
9 sg:pub.10.1007/bfb0083587
10 schema:datePublished 1993-01
11 schema:datePublishedReg 1993-01-01
12 schema:description In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a “long” step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral.
13 schema:genre article
14 schema:isAccessibleForFree false
15 schema:isPartOf N2a33f82679fa4eca83e0b91275ee165f
16 N66b67963ddff4114b12b877277660caa
17 sg:journal.1120592
18 schema:keywords accuracy
19 class
20 complexity
21 curvature integral
22 derivatives
23 dual problem
24 feasible solution
25 first-order methods
26 gain
27 integrals
28 integrand
29 interior feasible solution
30 iteration
31 linear program
32 measures
33 method
34 number
35 number of points
36 optimal solution
37 order
38 paper
39 parameters
40 particular class
41 path parameters
42 path-following method
43 point
44 primal-dual path-following method
45 primal-dual space
46 problem
47 program
48 respect
49 second derivative
50 solution
51 space
52 step
53 tangent
54 trajectories
55 weighted measure
56 schema:name Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
57 schema:pagination 85-103
58 schema:productId N22515d15a3e94e76bebfd8046cd55536
59 Na871e1b7bd66442396596d27acabef59
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053613854
61 https://doi.org/10.1007/bf01182599
62 schema:sdDatePublished 2022-08-04T16:50
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher Nc190841236da4d7c9d01c2235aa687c4
65 schema:url https://doi.org/10.1007/bf01182599
66 sgo:license sg:explorer/license/
67 sgo:sdDataset articles
68 rdf:type schema:ScholarlyArticle
69 N22515d15a3e94e76bebfd8046cd55536 schema:name doi
70 schema:value 10.1007/bf01182599
71 rdf:type schema:PropertyValue
72 N2a33f82679fa4eca83e0b91275ee165f schema:issueNumber 1
73 rdf:type schema:PublicationIssue
74 N6055c8eee1ba466dae97ea664a3baa0b rdf:first sg:person.011530401251.34
75 rdf:rest N7f02bdd3daf9405aaa56a15f29d026af
76 N66b67963ddff4114b12b877277660caa schema:volumeNumber 27
77 rdf:type schema:PublicationVolume
78 N7f02bdd3daf9405aaa56a15f29d026af rdf:first sg:person.011465456275.61
79 rdf:rest rdf:nil
80 Na871e1b7bd66442396596d27acabef59 schema:name dimensions_id
81 schema:value pub.1053613854
82 rdf:type schema:PropertyValue
83 Nc190841236da4d7c9d01c2235aa687c4 schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
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.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
97 schema:familyName Stoer
98 schema:givenName J.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
100 rdf:type schema:Person
101 sg:person.011530401251.34 schema:affiliation grid-institutes:grid.8379.5
102 schema:familyName Zhao
103 schema:givenName G.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011530401251.34
105 rdf:type schema:Person
106 sg:pub.10.1007/bf01445161 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022928088
107 https://doi.org/10.1007/bf01445161
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/bf01580724 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028120387
110 https://doi.org/10.1007/bf01580724
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/bf01587095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014973872
113 https://doi.org/10.1007/bf01587095
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/bf02579150 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035950209
116 https://doi.org/10.1007/bf02579150
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/bfb0042223 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045273451
119 https://doi.org/10.1007/bfb0042223
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bfb0083587 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048822435
122 https://doi.org/10.1007/bfb0083587
123 rdf:type schema:CreativeWork
124 grid-institutes:grid.8379.5 schema:alternateName Institut für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany
125 schema:name Institut für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany
126 rdf:type schema:Organization
 




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


...