We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.
We consider semidefinite relaxations of a quadratic optimization problem with polynomial constraints. This is an extension of quadratic problems with Boolean variables. Such combinatorial problems cannot, in general, be solved in polynomial time. Semidefinite relaxation has been proposed as a promising technique to give provable good bounds on certain Boolean quadratic problems in polynomial time. We formulate the extensions from Boolean variables to quarternary variables using (i) a polynomial relaxation or (ii) standard semidefinite relaxations of a linear transformation of Boolean variables. We compare the two different relaxation approaches analytically. The relaxations can all be expressed as semidefinite programs, which can be solved efficiently using e.g. interior point methods. Applications of our results include maximum likelihood estimation in communication systems, which we explore in simulations in order to compare the quality of the different relaxations with optimal solutions.
Quadratic optimization problems with complex-valued decision variables, in short called complex quadratic optimization problems, find many applications in engineering. In this dissertation, we study several instructive models of complex quadratic optimization, as well as its applications in combinatorial optimization. The tool that we use is a combination of semidefinite programming (SDP) relaxation and randomization technique, which has been well exploited in the last decade. Since most of the optimization models are NP-hard in nature, we shall design polynomial time approximation algorithms for a general model, or polynomial time exact algorithms for some restricted instances of a general model.
To enable the analysis, we first develop two basic theoretical results: one is the probability formula for a bivariate complex normal distribution vector to be in a prescribed angular region, and the other one is the rank-one decomposition theorem for complex positive semidefinite matrices. The probability formula enables us to compute the expected value of a randomized (with a specific rounding rule) solution based on an optimal solution of the SDP relaxation problem, while the rank-one decomposition theorem provides a new proof of the complex S -lemma and leads to novel deterministic rounding procedures.
With the above results in hand, we then investigate the models and applications of complex quadratic optimization via semidefinite programming in detail. We present an approximation algorithm for a convex quadratic maximization problem with discrete complex decision variables, where the approximation analysis is based on the probability formula. Besides, an approximation algorithm is proposed for a non-convex quadratic maximization problem with discrete complex decision variables. Then we study a limit of the model, i.e., a quadratic maximization problem with continuous unit module decision variables. The problem is shown to be strongly NP-hard. Approximation algorithms are described for the problem, including both convex case and non-convex case. Furthermore, if the objective matrix has a sign structure, then a stronger approximation result is shown to hold. In addition, we use the complex matrix decomposition theorem to solve complex quadratically constrained complex quadratic programming. We consider several interesting cases for which the corresponding SDP relaxation admits no gap with the true optimal value, and consequently, this yields polynomial time procedures for solving those special cases of complex quadratic optimization.
Finally, as combinatorial applications of complex quadratic optimization; we consider Max 3-Cut with fixed nodes constraints, Max 3-Dicut with weight constraints, Max 3-XOR, and so on, and present corresponding bounds on the approximation ratios.
In computer vision, many problems can be formulated as binary quadratic programs (BQPs), which are in general NP hard. Finding a solution when the problem is of large size to be of practical interest typically requires relaxation. Semidefinite relaxation usually yields tight bounds, but its computational complexity is high. In this work, we present a semidefinite programming (SDP) formulation for BQPs, with two desirable properties. First, it produces similar bounds to the standard SDP formulation. Second, compared with the conventional SDP formulation, the proposed SDP formulation leads to a considerably more efficient and scalable dual optimization approach. We then propose two solvers, namely, quasi-Newton and smoothing Newton methods, for the simplified dual problem. Both of them are significantly more efficient than standard interior-point methods. Empirically the smoothing Newton solver is faster than the quasi-Newton solver for dense or medium-sized problems, while the quasi-Newton solver is preferable for large sparse/structured problems.
ABSTRACT This paper studies semidefinite programming (SDP) relaxations for the Boolean Quadratic Programming problem with Generalized Upper Bound constraints (BQP-GUB), which arises in several application domains. We show that conventional semidefinite relaxation (SDR) does not yield tight bounds for this problem. We then analyze strengthened SDP relaxations and identify formulations that produce tight or near-tight bounds, particularly those based on reduced reformulation-linearization techniques (SDR+RRLT and SSDR+RRLT. Numerical experiments demonstrate that these approaches significantly reduce the relaxation gap compared to SDR, while highlighting the trade-off between bound quality and computational scalability.
Following the seminal work of Goemans and Williamson [1], there has been an outgrowth in the use of semidefinite programming (SDP) for designing approximation algorithms. Recall that anα-approximation algorithm for a problem P is a polynomial-time algorithm such that for every instance I of P , it delivers a solution that is within a factor of α of the optimum value [2]. It is well known that SDPs can be solved in polynomial time (up to any prescribed accuracy) via interior-point algorithms (see, e.g., Refs. [3,4]), and they have been used very successfully in the design of approximation algorithms for a host of NP-hard problems, e.g., graph partitioning, graph coloring, and quadratic optimization [1-9], just to name a few.
Many combinatorial optimization problems can be formulated as the minimization of a 0–1 quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through a two-phase general scheme. The first phase consists in reformulating the initial problem either into a compact mixed integer linear program or into a 0–1 quadratic convex program. The second phase simply consists in submitting the reformulated problem to a standard solver. The efficiency of this scheme strongly depends on the quality of the reformulation obtained in phase 1. We show that a good compact linear reformulation can be obtained by solving a continuous linear relaxation of the initial problem. We also show that a good quadratic convex reformulation can be obtained by solving a semidefinite relaxation. In both cases, the obtained reformulation profits from the quality of the underlying relaxation. Hence, the proposed scheme gets around, in a sense, the difficulty to incorporate these costly relaxations in a branch-and-bound algorithm.
We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are integer and bounded. This very general problem can model many classical problems in Combinatorial Optimization.A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP'), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP') by an implicit enumeration algorithm based on continuous convex optimization.We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP'). In the case of binary variables, we give a vision of classical linearization as a special case of Convex Quadratic Reformulation.Finally, we illustrate the generality and the computational efficiency of the Quadratic Convex Reformulation approach for several combinatorial optimization problems.