Interplay of non-convex quadratically constrained problems with adjustable robust optimization
- PDF / 628,975 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 7 Downloads / 176 Views
Interplay of non-convex quadratically constrained problems with adjustable robust optimization Immanuel Bomze1 · Markus Gabl1 Received: 21 March 2019 / Revised: 24 July 2020 © The Author(s) 2020
Abstract In this paper we explore convex reformulation strategies for non-convex quadratically constrained optimization problems (QCQPs). First we investigate such reformulations using Pataki’s rank theorem iteratively. We show that the result can be used in conjunction with conic optimization duality in order to obtain a geometric condition for the S-procedure to be exact. Based upon known results on the S-procedure, this approach allows for some insight into the geometry of the joint numerical range of the quadratic forms. Then we investigate a reformulation strategy introduced in recent literature for bilinear optimization problems which is based on adjustable robust optimization theory. We show that, via a similar strategy, one can leverage exact reformulation results of QCQPs in order to derive lower bounds for more complicated quadratic optimization problems. Finally, we investigate the use of reformulation strategies in order to derive characterizations of set-copositive matrix cones. Empirical evidence based upon first numerical experiments shows encouraging results. Keywords Robust optimization · Quadratic optimization · Conic optimization · S-Lemma · Copositivity
1 Introduction and outline In this text we explore the connections between robust optimization and quadratically constrained quadratic optimization. For the sake of this introduction we briefly review the most important concepts in these areas and then give an outline on the aims of this text.
B
Markus Gabl [email protected] Immanuel Bomze [email protected]
1
ISOR/VCOR/VGSCO and ds:univie, University of Vienna, Vienna, Austria
123
I. Bomze, M. Gabl
1.1 Quadratically constrained quadratic optimization A quadratically constrained quadratic optimization problem (QCQP) consists of minimizing a quadratic function subject to quadratic constraints, formally given by inf x∈K xT Qx + qT x + ω : xT Ai x + aiT x ≤ bi , i ∈ [1 : m] , where Q, Ai are real, symmetric matrices of order n, K ⊆ Rn is a cone, q, ai are real vectors, bi are real numbers and [1 : k] := {1, . . . , k}. General QCQPs are hard, and form a large and quite versatile class of optimization problems. Neither the objective function nor the feasible set of a QCQP need to be convex, the latter may even be disconnected. One way to (approximately) solve QCQPs is to look for convex relaxations which in the best case yield exact reformulations. An important strategy for achieving such reformulations is to lift the space of variables, thereby linearizing the quadratic terms and convexifying the feasible set, such that its extreme points correspond to rank-one matrices, which will decompose into vectors feasible to the original problem: Theorem 1 Let F := x ∈ K : xT Ai x + aiT x ≤ bi , i ∈ [1 : m] ⊆ Rn be a feasible set of a QCQP and denote by G(F) := clconv (x, xxT ) :
Data Loading...
