Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/308622 
Authors: 
Year of Publication: 
2023
Citation: 
[Journal:] Journal of Global Optimization [ISSN:] 1573-2916 [Volume:] 87 [Issue:] 1 [Publisher:] Springer US [Place:] New York, NY [Year:] 2023 [Pages:] 221-254
Publisher: 
Springer US, New York, NY
Abstract: 
Recently, Bomze et al. introduced a sparse conic relaxation of the scenario problem of a two stage stochastic version of the standard quadratic optimization problem. When compared numerically to Burer's classical reformulation, the authors showed that there seems to be almost no difference in terms of solution quality, whereas the solution time can differ by orders of magnitudes. While the authors did find a very limited special case, for which Burer's reformulation and their relaxation are equivalent, no satisfying explanation for the high quality of their bound was given. This article aims at shedding more light on this phenomenon and give a more thorough theoretical account of its inner workings. We argue that the quality of the outer approximation cannot be explained by traditional results on sparse conic relaxations based on positive semidenifnite or completely positive matrix completion, which require certain sparsity patterns characterized by chordal and block clique graphs respectively, and put certain restrictions on the type of conic constraint they seek to sparsify. In an effort to develop an alternative approach, we will provide a new type of convex reformulation of a large class of stochastic quadratically constrained quadratic optimization problems that is similar to Burer's reformulation, but lifts the variables into a comparatively lower dimensional space. The reformulation rests on a generalization of the set-completely positive matrix cone. This cone can then be approximated via inner and outer approximations in order to obtain upper and lower bounds, which potentially close the optimality gap, and hence can give a certificate of exactness for these sparse reformulations outside of traditional, known sufficient conditions. Finally, we provide some numerical experiments, where we asses the quality of the inner and outer approximations, thereby showing that the approximations may indeed close the optimality gap in interesting cases.
Subjects: 
Quadratic optimization
Copositive optimization
Matrix completion
Conic optimization
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.