Convexification of sub-structures for Quadratically Constrained Quadratic Programs
Abstract
Quadratically Constrained Quadratic Program (QCQP) is an optimization problem with quadratic objective and quadratic constraints, where the quadratic functions involved are not necessarily convex. While QCQPs are very challenging to solve, a very large number of optimization problems can be modeled as QCQPs. A key technique used to certify the quality of solutions found is viaconvexification of feasible region. While there are general-purpose convexification schemes for QCQPs such as the Reformulation-linearization technique (RLT) and the Lasserre hierarchy, like in the case of integer programming, an important area of study is to convexify commonly occurringsubstructures. Most of the work in this direction in the global optimization area has been focused on convexification of functions (i.e., finding convex and concave envelops). On the other hand, it is well known that convexification of sets can produces tighter relaxation than convexification of functions. Thusconvexification of set has a significant advantage over convexification of functions. On the other hand, there may also be some disadvantages of convexification of sets such as: (i) the resulting set may be difficult to optimize on from a practical standpoint (ii) typically a function may appear repeatedly in a formulation, so that a single convexification is sufficient; while convexification ofsets with the same function but different right-hand-sides may need re-omputing.Since there are very few results on convexification of sets, it was not possible up till now to test whether convexification of sets versus convexification of functions eventually leads to better and more efficient algorithms. Therefore, the goal of this proposal is to develop new methods for convexification of sets and to conduct extensive experiments to compare convexification of sets versus functions within branch and bound code. The proposal presents two potential classes of substructures that appear in general QCQPs, where it may be possible to convexify sets and yield tractable convex relaxations (i.e. either polyhedral or second order cone representable relaxations). The first substructure is that of one-row relaxations of QCQPs. The second substructure is a rank-1 constraint on a matrix variable with side-constraints. If the open problems relating to convexification of these substructures listed ~in this proposal can be solved, then it is expected that it will help in significantly improving the efficiency of general-purpose QCQP solvers.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- May 23, 2019
- Source ID
- N000141912323
Entities
People
- Santanu S. Dey
Organizations
- Georgia Tech Research Corporation
- Office of Naval Research
- United States Navy