Solving quadratic programs to high precision using scaled iterative refinement View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-02-06

AUTHORS

Tobias Weber, Sebastian Sager, Ambros Gleixner

ABSTRACT

Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library. More... »

PAGES

1-35

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s12532-019-00154-6

DOI

http://dx.doi.org/10.1007/s12532-019-00154-6

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Otto-von-Guericke University Magdeburg", 
          "id": "https://www.grid.ac/institutes/grid.5807.a", 
          "name": [
            "Institute of Mathematical Optimization, Otto von Guericke University, Universit\u00e4tsplatz 2, 02-204, 39106, Magdeburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Weber", 
        "givenName": "Tobias", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Otto-von-Guericke University Magdeburg", 
          "id": "https://www.grid.ac/institutes/grid.5807.a", 
          "name": [
            "Institute of Mathematical Optimization, Otto von Guericke University, Universit\u00e4tsplatz 2, 02-204, 39106, Magdeburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sager", 
        "givenName": "Sebastian", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Zuse Institute Berlin", 
          "id": "https://www.grid.ac/institutes/grid.425649.8", 
          "name": [
            "Department of Mathematical Optimization, Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gleixner", 
        "givenName": "Ambros", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/336154.336191", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001378117"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2442829.2442858", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005956417"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/380995.380999", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018232547"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0092976", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018634553", 
          "https://doi.org/10.1007/bfb0092976"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/103162.103163", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1020479097"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s12532-014-0071-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021731378", 
          "https://doi.org/10.1007/s12532-014-0071-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/10556789908805768", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023330000"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/130940384", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062871368"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s1064827598345667", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062884673"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.2016.0692", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064707318"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/1909468", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069638593"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/16m1079002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1100278631"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-02-06", 
    "datePublishedReg": "2019-02-06", 
    "description": "Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and M\u00e9sz\u00e1ros benchmark library.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s12532-019-00154-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1053027", 
        "issn": [
          "1867-2949", 
          "1867-2957"
        ], 
        "name": "Mathematical Programming Computation", 
        "type": "Periodical"
      }
    ], 
    "name": "Solving quadratic programs to high precision using scaled iterative refinement", 
    "pagination": "1-35", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "e42b7f299ff1ab9d529cf54e36333b208bfa25f3f71a2f39403e520cc2716b2e"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s12532-019-00154-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1111949697"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s12532-019-00154-6", 
      "https://app.dimensions.ai/details/publication/pub.1111949697"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T09:02", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000331_0000000331/records_105436_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs12532-019-00154-6"
  }
]
 

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/s12532-019-00154-6'

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/s12532-019-00154-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12532-019-00154-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12532-019-00154-6'


 

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

107 TRIPLES      21 PREDICATES      36 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s12532-019-00154-6 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nb294f9bf6a234e26a33e6660be29c43f
4 schema:citation sg:pub.10.1007/bfb0092976
5 sg:pub.10.1007/s12532-014-0071-1
6 https://doi.org/10.1080/10556789908805768
7 https://doi.org/10.1137/130940384
8 https://doi.org/10.1137/16m1079002
9 https://doi.org/10.1137/s1064827598345667
10 https://doi.org/10.1145/103162.103163
11 https://doi.org/10.1145/2442829.2442858
12 https://doi.org/10.1145/336154.336191
13 https://doi.org/10.1145/380995.380999
14 https://doi.org/10.1287/ijoc.2016.0692
15 https://doi.org/10.2307/1909468
16 schema:datePublished 2019-02-06
17 schema:datePublishedReg 2019-02-06
18 schema:description Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and Mészáros benchmark library.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree false
22 schema:isPartOf sg:journal.1053027
23 schema:name Solving quadratic programs to high precision using scaled iterative refinement
24 schema:pagination 1-35
25 schema:productId N53e4251ab774461d83f9d074fdab287f
26 N9aa691cbe01a498994df4f5907b72471
27 Nf6a7f631e19343acb114fef051292baa
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1111949697
29 https://doi.org/10.1007/s12532-019-00154-6
30 schema:sdDatePublished 2019-04-11T09:02
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher Naad53042b07f42978193cb18e06e196a
33 schema:url https://link.springer.com/10.1007%2Fs12532-019-00154-6
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N3b7fae58f753405387139f925913af51 schema:affiliation https://www.grid.ac/institutes/grid.5807.a
38 schema:familyName Weber
39 schema:givenName Tobias
40 rdf:type schema:Person
41 N53e4251ab774461d83f9d074fdab287f schema:name dimensions_id
42 schema:value pub.1111949697
43 rdf:type schema:PropertyValue
44 N9aa691cbe01a498994df4f5907b72471 schema:name readcube_id
45 schema:value e42b7f299ff1ab9d529cf54e36333b208bfa25f3f71a2f39403e520cc2716b2e
46 rdf:type schema:PropertyValue
47 Na28ebb08f44c49e7a24706ea5c4007fd schema:affiliation https://www.grid.ac/institutes/grid.5807.a
48 schema:familyName Sager
49 schema:givenName Sebastian
50 rdf:type schema:Person
51 Naad53042b07f42978193cb18e06e196a schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 Nb294f9bf6a234e26a33e6660be29c43f rdf:first N3b7fae58f753405387139f925913af51
54 rdf:rest Nd5022e0a6eab456db23a3345a8f37b62
55 Nc0032faf868d45cbb4af8c988bc80c11 schema:affiliation https://www.grid.ac/institutes/grid.425649.8
56 schema:familyName Gleixner
57 schema:givenName Ambros
58 rdf:type schema:Person
59 Nd5022e0a6eab456db23a3345a8f37b62 rdf:first Na28ebb08f44c49e7a24706ea5c4007fd
60 rdf:rest Nefbb5e4ffbfb4b589a8e2969f7eeb612
61 Nefbb5e4ffbfb4b589a8e2969f7eeb612 rdf:first Nc0032faf868d45cbb4af8c988bc80c11
62 rdf:rest rdf:nil
63 Nf6a7f631e19343acb114fef051292baa schema:name doi
64 schema:value 10.1007/s12532-019-00154-6
65 rdf:type schema:PropertyValue
66 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
67 schema:name Mathematical Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
70 schema:name Numerical and Computational Mathematics
71 rdf:type schema:DefinedTerm
72 sg:journal.1053027 schema:issn 1867-2949
73 1867-2957
74 schema:name Mathematical Programming Computation
75 rdf:type schema:Periodical
76 sg:pub.10.1007/bfb0092976 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018634553
77 https://doi.org/10.1007/bfb0092976
78 rdf:type schema:CreativeWork
79 sg:pub.10.1007/s12532-014-0071-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021731378
80 https://doi.org/10.1007/s12532-014-0071-1
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1080/10556789908805768 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023330000
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1137/130940384 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062871368
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1137/16m1079002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1100278631
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1137/s1064827598345667 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062884673
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1145/103162.103163 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020479097
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1145/2442829.2442858 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005956417
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1145/336154.336191 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001378117
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1145/380995.380999 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018232547
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1287/ijoc.2016.0692 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707318
99 rdf:type schema:CreativeWork
100 https://doi.org/10.2307/1909468 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069638593
101 rdf:type schema:CreativeWork
102 https://www.grid.ac/institutes/grid.425649.8 schema:alternateName Zuse Institute Berlin
103 schema:name Department of Mathematical Optimization, Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany
104 rdf:type schema:Organization
105 https://www.grid.ac/institutes/grid.5807.a schema:alternateName Otto-von-Guericke University Magdeburg
106 schema:name Institute of Mathematical Optimization, Otto von Guericke University, Universitätsplatz 2, 02-204, 39106, Magdeburg, Germany
107 rdf:type schema:Organization
 




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


...