Minimization of convex functions on the convex hull of a point set View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2005-10-06

AUTHORS

Nikolai D. Botkin, Josef Stoer

ABSTRACT

A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in Rn is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in Rm, which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution. More... »

PAGES

167-185

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00186-005-0018-4

DOI

http://dx.doi.org/10.1007/s00186-005-0018-4

DIMENSIONS

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


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": "Center of advanced european studies and research (caesar), Ludwig-Erhard-Allee 2, D-53175, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.438114.b", 
          "name": [
            "Center of advanced european studies and research (caesar), Ludwig-Erhard-Allee 2, D-53175, Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Botkin", 
        "givenName": "Nikolai D.", 
        "id": "sg:person.014365613271.99", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014365613271.99"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institut f\u00fcr Angewandte Mathematik und Statistik der Universit\u00e4t W\u00fcrzburg Am Hubland, D-97074, W\u00fcrzburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.8379.5", 
          "name": [
            "Institut f\u00fcr Angewandte Mathematik und Statistik der Universit\u00e4t W\u00fcrzburg Am Hubland, D-97074, W\u00fcrzburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Stoer", 
        "givenName": "Josef", 
        "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/bf00938486", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009261784", 
          "https://doi.org/10.1007/bf00938486"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02592073", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000925191", 
          "https://doi.org/10.1007/bf02592073"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2005-10-06", 
    "datePublishedReg": "2005-10-06", 
    "description": "A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in Rn is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in Rm, which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00186-005-0018-4", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1053187", 
        "issn": [
          "1432-2994", 
          "1432-5217"
        ], 
        "name": "Mathematical Methods of Operations Research", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "62"
      }
    ], 
    "keywords": [
      "function", 
      "projections", 
      "procedure", 
      "simplex", 
      "method", 
      "new procedure", 
      "number", 
      "cone", 
      "point", 
      "Rn", 
      "current point", 
      "operation", 
      "gradient", 
      "RM", 
      "basic methods", 
      "set", 
      "solution", 
      "quadratic function", 
      "hull", 
      "usual constraints", 
      "minimization", 
      "algorithm", 
      "coordinates", 
      "differentiable convex function", 
      "constraints", 
      "convex functions", 
      "simplicial cone", 
      "tangent cone", 
      "basic algorithm", 
      "iteration", 
      "barycentric coordinates", 
      "convex hull", 
      "noniterative method", 
      "convex quadratic function", 
      "objective function", 
      "optimal solution", 
      "point sets"
    ], 
    "name": "Minimization of convex functions on the convex hull of a point set", 
    "pagination": "167-185", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031504787"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00186-005-0018-4"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00186-005-0018-4", 
      "https://app.dimensions.ai/details/publication/pub.1031504787"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-06-01T22:03", 
    "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_397.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00186-005-0018-4"
  }
]
 

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/s00186-005-0018-4'

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/s00186-005-0018-4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00186-005-0018-4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00186-005-0018-4'


 

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

113 TRIPLES      22 PREDICATES      64 URIs      54 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00186-005-0018-4 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Na89f5f68e66e4531a0f91387fef222f7
4 schema:citation sg:pub.10.1007/bf00938486
5 sg:pub.10.1007/bf02592073
6 schema:datePublished 2005-10-06
7 schema:datePublishedReg 2005-10-06
8 schema:description A basic algorithm for the minimization of a differentiable convex function (in particular, a strictly convex quadratic function) defined on the convex hull of m points in Rn is outlined. Each iteration of the algorithm is implemented in barycentric coordinates, the number of which is equal to m. The method is based on a new procedure for finding the projection of the gradient of the objective function onto a simplicial cone in Rm, which is the tangent cone at the current point to the simplex defined by the usual constraints on barycentric coordinates. It is shown that this projection can be computed in O(m log m) operations. For strictly convex quadratic functions, the basic method can be refined to a noniterative method terminating with the optimal solution.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N432f43066d7c4725bdef8624dca43e79
13 N888a7abab80549e8ba996f4def17ee2a
14 sg:journal.1053187
15 schema:keywords RM
16 Rn
17 algorithm
18 barycentric coordinates
19 basic algorithm
20 basic methods
21 cone
22 constraints
23 convex functions
24 convex hull
25 convex quadratic function
26 coordinates
27 current point
28 differentiable convex function
29 function
30 gradient
31 hull
32 iteration
33 method
34 minimization
35 new procedure
36 noniterative method
37 number
38 objective function
39 operation
40 optimal solution
41 point
42 point sets
43 procedure
44 projections
45 quadratic function
46 set
47 simplex
48 simplicial cone
49 solution
50 tangent cone
51 usual constraints
52 schema:name Minimization of convex functions on the convex hull of a point set
53 schema:pagination 167-185
54 schema:productId N0c9702de309e4f03a908c95db7e93217
55 Nd000a7abe3ac476c8db078170ac0f939
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031504787
57 https://doi.org/10.1007/s00186-005-0018-4
58 schema:sdDatePublished 2022-06-01T22:03
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N0e4a517891db4e31b736ab3062e4c450
61 schema:url https://doi.org/10.1007/s00186-005-0018-4
62 sgo:license sg:explorer/license/
63 sgo:sdDataset articles
64 rdf:type schema:ScholarlyArticle
65 N0c9702de309e4f03a908c95db7e93217 schema:name dimensions_id
66 schema:value pub.1031504787
67 rdf:type schema:PropertyValue
68 N0e4a517891db4e31b736ab3062e4c450 schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 N432f43066d7c4725bdef8624dca43e79 schema:volumeNumber 62
71 rdf:type schema:PublicationVolume
72 N888a7abab80549e8ba996f4def17ee2a schema:issueNumber 2
73 rdf:type schema:PublicationIssue
74 N9f1c1cef17eb49f1bdbd1a493cbc97a9 rdf:first sg:person.011465456275.61
75 rdf:rest rdf:nil
76 Na89f5f68e66e4531a0f91387fef222f7 rdf:first sg:person.014365613271.99
77 rdf:rest N9f1c1cef17eb49f1bdbd1a493cbc97a9
78 Nd000a7abe3ac476c8db078170ac0f939 schema:name doi
79 schema:value 10.1007/s00186-005-0018-4
80 rdf:type schema:PropertyValue
81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
82 schema:name Mathematical Sciences
83 rdf:type schema:DefinedTerm
84 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
85 schema:name Numerical and Computational Mathematics
86 rdf:type schema:DefinedTerm
87 sg:journal.1053187 schema:issn 1432-2994
88 1432-5217
89 schema:name Mathematical Methods of Operations Research
90 schema:publisher Springer Nature
91 rdf:type schema:Periodical
92 sg:person.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
93 schema:familyName Stoer
94 schema:givenName Josef
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
96 rdf:type schema:Person
97 sg:person.014365613271.99 schema:affiliation grid-institutes:grid.438114.b
98 schema:familyName Botkin
99 schema:givenName Nikolai D.
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014365613271.99
101 rdf:type schema:Person
102 sg:pub.10.1007/bf00938486 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009261784
103 https://doi.org/10.1007/bf00938486
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bf02592073 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000925191
106 https://doi.org/10.1007/bf02592073
107 rdf:type schema:CreativeWork
108 grid-institutes:grid.438114.b schema:alternateName Center of advanced european studies and research (caesar), Ludwig-Erhard-Allee 2, D-53175, Bonn, Germany
109 schema:name Center of advanced european studies and research (caesar), Ludwig-Erhard-Allee 2, D-53175, Bonn, Germany
110 rdf:type schema:Organization
111 grid-institutes:grid.8379.5 schema:alternateName Institut für Angewandte Mathematik und Statistik der Universität Würzburg Am Hubland, D-97074, Würzburg, Germany
112 schema:name Institut für Angewandte Mathematik und Statistik der Universität Würzburg Am Hubland, D-97074, Würzburg, Germany
113 rdf:type schema:Organization
 




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


...