Solving Two-Trust-Region Subproblems Using Semidefinite Optimization with Eigenvector Branching View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-06-30

AUTHORS

Kurt M. Anstreicher

ABSTRACT

Semidefinite programming (SDP) problems typically utilize a constraint of the form X⪰xxT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X\succeq xx^T$$\end{document} to obtain a convex relaxation of the condition X=xxT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X=xx^T$$\end{document}, where x∈Rn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in \mathbb {R}^n$$\end{document}. In this paper, we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xxT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X-xx^T$$\end{document}. This branching technique is related to previous work of Saxeena et al. (Math Prog Ser B 124:383–411, 2010, https://doi.org/10.1007/s10107-010-0371-9) who used such an eigenvector to derive a disjunctive cut. We obtain excellent computational results applying the new branching technique to difficult instances of the two-trust-region subproblem. More... »

PAGES

1-17

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10957-022-02064-5

DOI

http://dx.doi.org/10.1007/s10957-022-02064-5

DIMENSIONS

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


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": "Department of Business Analytics, University of Iowa, 52242, Iowa City, IA, USA", 
          "id": "http://www.grid.ac/institutes/grid.214572.7", 
          "name": [
            "Department of Business Analytics, University of Iowa, 52242, Iowa City, IA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Anstreicher", 
        "givenName": "Kurt M.", 
        "id": "sg:person.012502164657.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012502164657.89"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02614438", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019631042", 
          "https://doi.org/10.1007/bf02614438"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-010-0371-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018790702", 
          "https://doi.org/10.1007/s10107-010-0371-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-014-0836-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027927883", 
          "https://doi.org/10.1007/s10107-014-0836-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009739827008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040596560", 
          "https://doi.org/10.1023/a:1009739827008"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02573959", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035527611", 
          "https://doi.org/10.1007/bf02573959"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00138693", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048968214", 
          "https://doi.org/10.1007/bf00138693"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-06-30", 
    "datePublishedReg": "2022-06-30", 
    "description": "Semidefinite programming (SDP) problems typically utilize a constraint of the form X\u2ab0xxT\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X\\succeq xx^T$$\\end{document} to obtain a convex relaxation of the condition X=xxT\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X=xx^T$$\\end{document}, where x\u2208Rn\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$x\\in \\mathbb {R}^n$$\\end{document}. In this paper, we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xxT\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$X-xx^T$$\\end{document}. This branching technique is related to previous work of Saxeena et\u00a0al.\u00a0(Math Prog Ser B 124:383\u2013411, 2010, https://doi.org/10.1007/s10107-010-0371-9) who used such an eigenvector to derive a disjunctive cut. We obtain excellent computational results applying the new branching technique to difficult instances of the two-trust-region subproblem.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10957-022-02064-5", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1044187", 
        "issn": [
          "0022-3239", 
          "1573-2878"
        ], 
        "name": "Journal of Optimization Theory and Applications", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }
    ], 
    "keywords": [
      "semidefinite programming problem", 
      "branching technique", 
      "excellent computational results", 
      "convex relaxation", 
      "semidefinite optimization", 
      "programming problem", 
      "disjunctive cuts", 
      "computational results", 
      "difficult instances", 
      "conditions x", 
      "branching method", 
      "eigenvectors", 
      "subproblems", 
      "previous work", 
      "optimization", 
      "problem", 
      "constraints", 
      "SDP", 
      "relaxation", 
      "technique", 
      "instances", 
      "form", 
      "work", 
      "et", 
      "al", 
      "results", 
      "paper", 
      "cut", 
      "branching", 
      "method"
    ], 
    "name": "Solving Two-Trust-Region Subproblems Using Semidefinite Optimization with Eigenvector Branching", 
    "pagination": "1-17", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1149110151"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10957-022-02064-5"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10957-022-02064-5", 
      "https://app.dimensions.ai/details/publication/pub.1149110151"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:49", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_928.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10957-022-02064-5"
  }
]
 

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/s10957-022-02064-5'

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/s10957-022-02064-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02064-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02064-5'


 

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

105 TRIPLES      21 PREDICATES      58 URIs      44 LITERALS      4 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10957-022-02064-5 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N594d2333224f4d28a14e582e50a26d03
4 schema:citation sg:pub.10.1007/bf00138693
5 sg:pub.10.1007/bf02573959
6 sg:pub.10.1007/bf02614438
7 sg:pub.10.1007/s10107-010-0371-9
8 sg:pub.10.1007/s10107-014-0836-3
9 sg:pub.10.1023/a:1009739827008
10 schema:datePublished 2022-06-30
11 schema:datePublishedReg 2022-06-30
12 schema:description Semidefinite programming (SDP) problems typically utilize a constraint of the form X⪰xxT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X\succeq xx^T$$\end{document} to obtain a convex relaxation of the condition X=xxT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X=xx^T$$\end{document}, where x∈Rn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in \mathbb {R}^n$$\end{document}. In this paper, we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xxT\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$X-xx^T$$\end{document}. This branching technique is related to previous work of Saxeena et al. (Math Prog Ser B 124:383–411, 2010, https://doi.org/10.1007/s10107-010-0371-9) who used such an eigenvector to derive a disjunctive cut. We obtain excellent computational results applying the new branching technique to difficult instances of the two-trust-region subproblem.
13 schema:genre article
14 schema:isAccessibleForFree false
15 schema:isPartOf sg:journal.1044187
16 schema:keywords SDP
17 al
18 branching
19 branching method
20 branching technique
21 computational results
22 conditions x
23 constraints
24 convex relaxation
25 cut
26 difficult instances
27 disjunctive cuts
28 eigenvectors
29 et
30 excellent computational results
31 form
32 instances
33 method
34 optimization
35 paper
36 previous work
37 problem
38 programming problem
39 relaxation
40 results
41 semidefinite optimization
42 semidefinite programming problem
43 subproblems
44 technique
45 work
46 schema:name Solving Two-Trust-Region Subproblems Using Semidefinite Optimization with Eigenvector Branching
47 schema:pagination 1-17
48 schema:productId N47be3b221b0842e7b65dc442c0ba0a9b
49 N672ad754fc814b8d954cb19fec89cab5
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1149110151
51 https://doi.org/10.1007/s10957-022-02064-5
52 schema:sdDatePublished 2022-10-01T06:49
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher N599b71fe07484fefa474f074da3cc269
55 schema:url https://doi.org/10.1007/s10957-022-02064-5
56 sgo:license sg:explorer/license/
57 sgo:sdDataset articles
58 rdf:type schema:ScholarlyArticle
59 N47be3b221b0842e7b65dc442c0ba0a9b schema:name doi
60 schema:value 10.1007/s10957-022-02064-5
61 rdf:type schema:PropertyValue
62 N594d2333224f4d28a14e582e50a26d03 rdf:first sg:person.012502164657.89
63 rdf:rest rdf:nil
64 N599b71fe07484fefa474f074da3cc269 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N672ad754fc814b8d954cb19fec89cab5 schema:name dimensions_id
67 schema:value pub.1149110151
68 rdf:type schema:PropertyValue
69 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
70 schema:name Mathematical Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
73 schema:name Numerical and Computational Mathematics
74 rdf:type schema:DefinedTerm
75 sg:journal.1044187 schema:issn 0022-3239
76 1573-2878
77 schema:name Journal of Optimization Theory and Applications
78 schema:publisher Springer Nature
79 rdf:type schema:Periodical
80 sg:person.012502164657.89 schema:affiliation grid-institutes:grid.214572.7
81 schema:familyName Anstreicher
82 schema:givenName Kurt M.
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012502164657.89
84 rdf:type schema:Person
85 sg:pub.10.1007/bf00138693 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048968214
86 https://doi.org/10.1007/bf00138693
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/bf02573959 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035527611
89 https://doi.org/10.1007/bf02573959
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/bf02614438 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019631042
92 https://doi.org/10.1007/bf02614438
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/s10107-010-0371-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018790702
95 https://doi.org/10.1007/s10107-010-0371-9
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/s10107-014-0836-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027927883
98 https://doi.org/10.1007/s10107-014-0836-3
99 rdf:type schema:CreativeWork
100 sg:pub.10.1023/a:1009739827008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040596560
101 https://doi.org/10.1023/a:1009739827008
102 rdf:type schema:CreativeWork
103 grid-institutes:grid.214572.7 schema:alternateName Department of Business Analytics, University of Iowa, 52242, Iowa City, IA, USA
104 schema:name Department of Business Analytics, University of Iowa, 52242, Iowa City, IA, USA
105 rdf:type schema:Organization
 




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


...