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/bf01580724", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028120387", 
          "https://doi.org/10.1007/bf01580724"
        ], 
        "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/bf02579150", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035950209", 
          "https://doi.org/10.1007/bf02579150"
        ], 
        "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/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", 
    "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": "27"
      }
    ], 
    "keywords": [
      "path-following method", 
      "curvature integral", 
      "primal-dual space", 
      "first-order methods", 
      "interior feasible solution", 
      "number of points", 
      "dual problem", 
      "optimal solution", 
      "linear program", 
      "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", 
      "derivatives", 
      "respect", 
      "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-06-01T22:01", 
    "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_256.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      22 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 N981b2882e8f94150b95e264e9049e59d
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:inLanguage en
15 schema:isAccessibleForFree false
16 schema:isPartOf N21c13eec18294bd4b18be8e55568dde4
17 N7c73e5155c4f471caf878340b599e8c2
18 sg:journal.1120592
19 schema:keywords accuracy
20 class
21 complexity
22 curvature integral
23 derivatives
24 dual problem
25 feasible solution
26 first-order methods
27 gain
28 integrals
29 integrand
30 interior feasible solution
31 iteration
32 linear program
33 measures
34 method
35 number
36 number of points
37 optimal solution
38 order
39 paper
40 parameters
41 particular class
42 path parameters
43 path-following method
44 point
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 N493ac7d7a3324c258dc0d3dbbdbaf943
59 N777d56619a284d58b5f1a7e58cc7f403
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053613854
61 https://doi.org/10.1007/bf01182599
62 schema:sdDatePublished 2022-06-01T22:01
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher N617578cf26084f519c319a8f76f9f7cb
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 N1800a7c02fdb41bba8f56ea819c23b18 rdf:first sg:person.011465456275.61
70 rdf:rest rdf:nil
71 N21c13eec18294bd4b18be8e55568dde4 schema:issueNumber 1
72 rdf:type schema:PublicationIssue
73 N493ac7d7a3324c258dc0d3dbbdbaf943 schema:name dimensions_id
74 schema:value pub.1053613854
75 rdf:type schema:PropertyValue
76 N617578cf26084f519c319a8f76f9f7cb schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N777d56619a284d58b5f1a7e58cc7f403 schema:name doi
79 schema:value 10.1007/bf01182599
80 rdf:type schema:PropertyValue
81 N7c73e5155c4f471caf878340b599e8c2 schema:volumeNumber 27
82 rdf:type schema:PublicationVolume
83 N981b2882e8f94150b95e264e9049e59d rdf:first sg:person.011530401251.34
84 rdf:rest N1800a7c02fdb41bba8f56ea819c23b18
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)


...