Ontology type: schema:ScholarlyArticle
1991-05
AUTHORSG. Sonnevend, J. Stoer, G. Zhao
ABSTRACTA 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... »
PAGES527-553
http://scigraph.springernature.com/pub.10.1007/bf01582904
DOIhttp://dx.doi.org/10.1007/bf01582904
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1003736353
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
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