Ontology type: schema:ScholarlyArticle
1990-01
AUTHORS ABSTRACTThis 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... »
PAGES139-165
http://scigraph.springernature.com/pub.10.1007/bf01445161
DOIhttp://dx.doi.org/10.1007/bf01445161
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1022928088
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/bf02165238",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006395107",
"https://doi.org/10.1007/bf02165238"
],
"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/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"
},
{
"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/bfb0043914",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021827905",
"https://doi.org/10.1007/bfb0043914"
],
"type": "CreativeWork"
},
{
"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/bf01580848",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1022571826",
"https://doi.org/10.1007/bf01580848"
],
"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",
"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",
"set",
"analytics programs",
"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-08-04T16:51",
"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_256.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/bf01445161"
}
]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/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.
132 TRIPLES
21 PREDICATES
69 URIs
53 LITERALS
6 BLANK NODES