Solution of projection problems over polytopes View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1992-12

AUTHORS

Bingsheng He, Josef Stoer

ABSTRACT

In this paper, we present variants of a convergent projection and contraction algorithm [25] for solving projection problems over polytope. By using the special struture of the projection problems, an iterative algorithm with constant step-size is given, which is globally linearly convergent. These algorithms are simple to implement and each step of the method requires only a few matrix-vector multiplications. Especially, for minimums norm problems over transportation or general network polytopes onlyO(n) additions andO(n) multiplications are needed at each iteration. Numerical results for randomly generated test problems over network polytopes, up to 10000 variables, indicate that the presented algorithms are simple and efficient even for large problems. More... »

PAGES

73-90

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Institu 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": [
            "Institu f\u00fcr Angewandte Mathematik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, W\u00fcrzburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Bingsheng", 
        "id": "sg:person.014424663025.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014424663025.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institu 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": [
            "Institu f\u00fcr Angewandte Mathematik und Statistik, Universit\u00e4t W\u00fcrzburg, Am Hubland, W-8700, 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/bf00939081", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050530004", 
          "https://doi.org/10.1007/bf00939081"
        ], 
        "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"
      }, 
      {
        "id": "sg:pub.10.1007/bf00935545", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015458789", 
          "https://doi.org/10.1007/bf00935545"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01268170", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017224378", 
          "https://doi.org/10.1007/bf01268170"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02591799", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040368851", 
          "https://doi.org/10.1007/bf02591799"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01396325", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037333582", 
          "https://doi.org/10.1007/bf01396325"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01182323", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043027931", 
          "https://doi.org/10.1007/bf01182323"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02591962", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034228875", 
          "https://doi.org/10.1007/bf02591962"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00934130", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049636719", 
          "https://doi.org/10.1007/bf00934130"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01588976", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027622431", 
          "https://doi.org/10.1007/bf01588976"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1992-12", 
    "datePublishedReg": "1992-12-01", 
    "description": "In this paper, we present variants of a convergent projection and contraction algorithm [25] for solving projection problems over polytope. By using the special struture of the projection problems, an iterative algorithm with constant step-size is given, which is globally linearly convergent. These algorithms are simple to implement and each step of the method requires only a few matrix-vector multiplications. Especially, for minimums norm problems over transportation or general network polytopes onlyO(n) additions andO(n) multiplications are needed at each iteration. Numerical results for randomly generated test problems over network polytopes, up to 10000 variables, indicate that the presented algorithms are simple and efficient even for large problems.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01385498", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136759", 
        "issn": [
          "0029-599X", 
          "0945-3245"
        ], 
        "name": "Numerische Mathematik", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "61"
      }
    ], 
    "keywords": [
      "projection problem", 
      "minimum norm problem", 
      "matrix-vector multiplication", 
      "norm problem", 
      "test problems", 
      "iterative algorithm", 
      "large problems", 
      "contraction algorithm", 
      "polytope", 
      "numerical results", 
      "algorithm", 
      "problem", 
      "iteration", 
      "multiplication", 
      "convergent", 
      "solution", 
      "variables", 
      "struture", 
      "projections", 
      "step", 
      "results", 
      "transportation", 
      "variants", 
      "addition", 
      "convergent projections", 
      "method", 
      "paper"
    ], 
    "name": "Solution of projection problems over polytopes", 
    "pagination": "73-90", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047494543"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01385498"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01385498", 
      "https://app.dimensions.ai/details/publication/pub.1047494543"
    ], 
    "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_232.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01385498"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

132 TRIPLES      22 PREDICATES      63 URIs      45 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01385498 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nf0f24e88fdb84da1b3f8f90fbcc4d462
4 schema:citation sg:pub.10.1007/bf00934130
5 sg:pub.10.1007/bf00935545
6 sg:pub.10.1007/bf00939081
7 sg:pub.10.1007/bf01182323
8 sg:pub.10.1007/bf01268170
9 sg:pub.10.1007/bf01396325
10 sg:pub.10.1007/bf01588976
11 sg:pub.10.1007/bf02591799
12 sg:pub.10.1007/bf02591962
13 sg:pub.10.1007/bf02592073
14 schema:datePublished 1992-12
15 schema:datePublishedReg 1992-12-01
16 schema:description In this paper, we present variants of a convergent projection and contraction algorithm [25] for solving projection problems over polytope. By using the special struture of the projection problems, an iterative algorithm with constant step-size is given, which is globally linearly convergent. These algorithms are simple to implement and each step of the method requires only a few matrix-vector multiplications. Especially, for minimums norm problems over transportation or general network polytopes onlyO(n) additions andO(n) multiplications are needed at each iteration. Numerical results for randomly generated test problems over network polytopes, up to 10000 variables, indicate that the presented algorithms are simple and efficient even for large problems.
17 schema:genre article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf Naeebb72c06d647438596938cd199bf09
21 Nbde5a35f0d094342ac60be834addf718
22 sg:journal.1136759
23 schema:keywords addition
24 algorithm
25 contraction algorithm
26 convergent
27 convergent projections
28 iteration
29 iterative algorithm
30 large problems
31 matrix-vector multiplication
32 method
33 minimum norm problem
34 multiplication
35 norm problem
36 numerical results
37 paper
38 polytope
39 problem
40 projection problem
41 projections
42 results
43 solution
44 step
45 struture
46 test problems
47 transportation
48 variables
49 variants
50 schema:name Solution of projection problems over polytopes
51 schema:pagination 73-90
52 schema:productId N8f9d12d729074ba58023d0eaf5dabee3
53 Nf41a75a662154467b9e148a1ab121f77
54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047494543
55 https://doi.org/10.1007/bf01385498
56 schema:sdDatePublished 2022-06-01T22:01
57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
58 schema:sdPublisher N465bfaf269f8409c8b166e7755109534
59 schema:url https://doi.org/10.1007/bf01385498
60 sgo:license sg:explorer/license/
61 sgo:sdDataset articles
62 rdf:type schema:ScholarlyArticle
63 N41070ea0de134df49966187385e12fd1 rdf:first sg:person.011465456275.61
64 rdf:rest rdf:nil
65 N465bfaf269f8409c8b166e7755109534 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 N8f9d12d729074ba58023d0eaf5dabee3 schema:name doi
68 schema:value 10.1007/bf01385498
69 rdf:type schema:PropertyValue
70 Naeebb72c06d647438596938cd199bf09 schema:issueNumber 1
71 rdf:type schema:PublicationIssue
72 Nbde5a35f0d094342ac60be834addf718 schema:volumeNumber 61
73 rdf:type schema:PublicationVolume
74 Nf0f24e88fdb84da1b3f8f90fbcc4d462 rdf:first sg:person.014424663025.19
75 rdf:rest N41070ea0de134df49966187385e12fd1
76 Nf41a75a662154467b9e148a1ab121f77 schema:name dimensions_id
77 schema:value pub.1047494543
78 rdf:type schema:PropertyValue
79 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
80 schema:name Mathematical Sciences
81 rdf:type schema:DefinedTerm
82 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
83 schema:name Numerical and Computational Mathematics
84 rdf:type schema:DefinedTerm
85 sg:journal.1136759 schema:issn 0029-599X
86 0945-3245
87 schema:name Numerische Mathematik
88 schema:publisher Springer Nature
89 rdf:type schema:Periodical
90 sg:person.011465456275.61 schema:affiliation grid-institutes:grid.8379.5
91 schema:familyName Stoer
92 schema:givenName Josef
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011465456275.61
94 rdf:type schema:Person
95 sg:person.014424663025.19 schema:affiliation grid-institutes:grid.8379.5
96 schema:familyName He
97 schema:givenName Bingsheng
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014424663025.19
99 rdf:type schema:Person
100 sg:pub.10.1007/bf00934130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049636719
101 https://doi.org/10.1007/bf00934130
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/bf00935545 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015458789
104 https://doi.org/10.1007/bf00935545
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/bf00939081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050530004
107 https://doi.org/10.1007/bf00939081
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/bf01182323 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043027931
110 https://doi.org/10.1007/bf01182323
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/bf01268170 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017224378
113 https://doi.org/10.1007/bf01268170
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/bf01396325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037333582
116 https://doi.org/10.1007/bf01396325
117 rdf:type schema:CreativeWork
118 sg:pub.10.1007/bf01588976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027622431
119 https://doi.org/10.1007/bf01588976
120 rdf:type schema:CreativeWork
121 sg:pub.10.1007/bf02591799 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040368851
122 https://doi.org/10.1007/bf02591799
123 rdf:type schema:CreativeWork
124 sg:pub.10.1007/bf02591962 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034228875
125 https://doi.org/10.1007/bf02591962
126 rdf:type schema:CreativeWork
127 sg:pub.10.1007/bf02592073 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000925191
128 https://doi.org/10.1007/bf02592073
129 rdf:type schema:CreativeWork
130 grid-institutes:grid.8379.5 schema:alternateName Institu für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany
131 schema:name Institu für Angewandte Mathematik und Statistik, Universität Würzburg, Am Hubland, W-8700, Würzburg, Germany
132 rdf:type schema:Organization
 




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


...