The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice ${\bf Z}^n$, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.
The technique of semidefinite programming (SDP) relaxation can be used to obtain a nontrivial bound on the optimal value of a nonconvex quadratically constrained quadratic program (QCQP). We explore concave quadratic inequalities that hold for any vector in the integer lattice Zn, and show that adding these inequalities to a mixed-integer nonconvex QCQP can improve the SDP-based bound on the optimal value. This scheme is tested using several numerical problem instances of the max-cut problem and the integer least squares problem.
ABSTRACT Quadratically constrained quadratic programming (QCQP) problems appear in a wide range of engineering fields, including computer science, communication engineering, and finance. A key difficulty in solving these problems lies in efficiently finding global solutions, especially for large-scale and nonconvex instances. To address this, Wen & Yin (2013) proposed a method that reformulates semidefinite programming (SDP) relaxations of QCQPs into a nonlinear and nonconvex low-rank problem. This reformulated problem can be efficiently solved using a curvilinear search method combined with Barzilai-Borwein (BB) steps, known as the CSBB algorithm. In this study, we compare two approaches for solving QCQPs: the conventional convex SDP relaxation and the nonconvex low-rank reformulation introduced by Wen and Yin. We propose a set of general QCQP models that are compatible with the low-rank framework and conduct a series of numerical experiments to evaluate their performance. This study evaluates performance using several classes of NP-hard problems, including Binary Integer Quadratic (BIQ) problems, Max-Cut problems, Boolean Least Squares (BLS) problems, and 0-1 Quadratic Knapsack Problems (QKP). The results demonstrate that the low-rank approach offers competitive performance and shows strong potential for solving large-scale QCQPs more efficiently than traditional convex methods.
Abstract. It is well known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a comprehensive study on discrete positive semidefinite matrices, we introduce a generic approach to derive mixed-integer SDP (MISDP) formulations of binary quadratically constrained quadratic programs and binary quadratic matrix programs. Applying a problem-specific approach, we derive more compact MISDP formulations of several problems, such as the quadratic assignment problem, the graph partition problem, and the integer matrix completion problem. We also show that several structured problems allow for novel compact MISDP formulations through the notion of association schemes. Complementary to the recent advances on algorithmic aspects related to MISDP, this work opens new perspectives on solution approaches for the here considered problems.
We present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions due to Yarotsky, formulating this (simple) approximation using mixed-integer programming (MIP). Notably, the number of constraints, binary variables, and auxiliary continuous variables used in this formulation grows logarithmically in the approximation error. Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. Further, we show that our formulation represents feasible points via a Gray code. We close with computational results on problems with quadratic objectives and/or constraints, showing that our proposed method i) across the board outperforms existing MIP relaxations from the literature, and ii) on hard instances produces better bounds than exact solvers within a fixed time budget.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.
We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and k-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .