The quadratic maximization problem with rank constraint means where n and m are two given positive integers with n ≤ m, Q is a given real symmetric matrix, is the unit sphere in and stands for the Euclidean inner product. In this note, motivated by Briët, Filho and Vallentin's and Ye's excellent works [J. Briët, F. Filho, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.; Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226], we first derive the relative approximation ratio for the above problem with arbitrary symmetric matrix Q. While Q was supposed to be positive semidefinite in [J. Briët, F. Filhom, and F. Vallentin, The positive semidefinite Grothendieck problem with rank constraint, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 6198, 2010, pp. 31–42.]. Secondly, we extend such a relative approximation ratio to a generalization of the above optimization problem. Finally, a slightly improved relative approximation ratio for the optimization problem considered in [Y. Ye, Approximating quadratic programming with bound and quadratic constraints, Math. Program. 84 (1999), pp. 219–226] is presented.
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.
This paper considers the following type of quadratic programming problem. Given an arbitrary matrix A, whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ such that x/sup T/Ax is maximized. Our approximation algorithm for this problem uses the canonical semidefinite relaxation and returns a solution whose ratio to the optimum is in /spl Omega/(1/ logn). This quadratic programming problem can be seen as an extension to that of maximizing x/sup T/Ay (where y's components are also /spl plusmn/1). Grothendieck's inequality states that the ratio of the optimum value of the latter problem to the optimum of its canonical semidefinite relaxation is bounded below by a constant. The study of this type of quadratic program arose from a desire to approximate the maximum correlation in correlation clustering. Nothing substantive was known about this problem; we present an /spl Omega/ (1/logn) approximation, based on our quadratic programming algorithm. We can also guarantee that our quadratic programming algorithm returns a solution to the MAXCUT problem that has a significant advantage over a random assignment.
In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.
Let
(QP) be an integer quadratic program that consists in minimizing a quadratic function subject to linear constraints. A such problem belongs to the class of
NP-Hard problems. Standard solvers that use a Branch and Bound algorithm can efficiently solve
(QP) in the specific case where its objective function is convex. Thus, to solve
(QP), we choose to reformulate it into an equivalent problem with a convex objective function. Two reformulations are possible: either we reformulate
(QP) into a linear program, or we reformulate it into a convex quadratic program. \par In the first part of this dissertation, we present several linearizations of
(QP), i.e. reformulations into an equivalent program with a linear objective function. Many linearization methods for the quadratic binary programs are known. A natural approach when considering
(QP) is therefore to reformulate it into a quadratic binary program. This can be done by the binary decomposition of each integer variable and then the linearization of each new product of two binary variables. However, this method, that we denote by \texttt{BBL (Binary Binary Linearization)}, leads to a linear program with a large number of variables and constraints. We then present a new approach, \texttt{BIL (Binary Integer Linearization)}, that consists in reformulating
(QP) into a particular quadratic integer program where each quadratic term is the product of an integer variable by a binary variable. As in the \texttt{BBL} approach, the binary variables come from the binary decomposition of the initial integer variables. Then, we linearize the obtained program by replacing each quadratic term by a new real variable and a set of inequalities. As the number of quadratic terms is lower than in the \texttt{BBL} approach, the number of additional variables is reduced. Hence, the obtained integer linear program is significantly smaller in the \texttt{BIL} approach. Moreover, contrary to what one might think, the \texttt{BIL} approach provides a better bound obtained by continuous relaxation than the \texttt{BBL} approach. Each reformulation leads to an integer linear program that is equivalent to
(QP) and that we improve by adding valid inequalities. \par In a second part, we present several quadratic convex reformulations of
(QP), i.e. we reformulate
(QP) into an equivalent program, with a quadratic convex objective function. We first introduce a simple approach to convexify
(QP) that consists in expressing linearly the squares of integer variables using their unary decompositions, and then to convexify with the smallest eigenvalue of the Hessian matrix of
(QP). We call this approach \texttt{NC (Naive Convexification)}. Then, we introduce a new convex reformulation scheme that perturbs the objective function of
(QP) with the linear expression of the products of integer variables, and the equality constraints of
(QP). Then, we show that we can compute, within this scheme, an optimal reformulation of
(QP) in terms of bound obtained by continuous relaxation : the \texttt{IQCR (Integer Quadratic Convex Reformulation)} approach. This reformulation is based on the optimal dual solution of a semi-definite relaxation of
(QP). Moreover, we show that the method \texttt{IQCR} is easily adaptable to mixed-integer programming. This adaptation, that we call \texttt{IQCRs}, also allows us to integrate the inequality constraints of
(QP) into the perturbation of the objective function of our convex reformulation scheme. Then, we present an interesting restriction of the method \texttt{IQCR}, called \texttt{CQCR (Compact Quadratic Convex Reformulation)}. The difference between this last approach and \texttt{IQCR} is that \texttt{CQCR} only uses the linear expression of the integer variable squares to perturb the objective function, while \texttt{IQCR} uses all the products. The interest is that \texttt{CQCR} produces a reformulated problem with a reduced size in comparison with the \texttt{IQCR} approach, what could be profitable experimentally. Finally, we apply these
3 methods \texttt{NC}, \texttt{CQCR} and \texttt{IQCR} to binary quadratic programming. We show that \texttt{NC} and \texttt{CQCR} are equivalent to existing binary convex reformulations. An interesting result is that \texttt{IQCR} is an improvement of existing convexifications for binary quadratic programming.\par In a third part, we design a specific Branch and Bound algorithm based on a projection property of the \texttt{IQCR} approach.\par Finally, we compare the four obtained linearizations and the three obtained quadratic convex reformulations from the computational point of view. For integer programming, computational experiences are carried out with two classes of instances of
(QP), the first having one equality constraint, and the other having one inequality constraint. The results show that most of the considered instances with up to
40 variables can be solved in one hour of CPU time by the \texttt{IQCR} and \texttt{CQCR} approaches. We then test \texttt{IQCR} on binary quadratic programming. The results corroborate that our approach \texttt{IQCR} improves existing convexifications.
This repository contains the source code, computational experiments, analysis, and benchmarks accompanying the paper A Direct SDP-Based Framework for Certified Bounds for Constrained Quadratic Binary Optimization Problems. The repository implements a direct semidefinite programming (SDP) approach for constrained quadratic binary optimization, designed to obtain strong bounds for exact optimization. The SDP relaxation is strengthened using quadratized linear constraints and triangle (hypermetric) inequalities. To address the numerical infeasibility of SDP solutions obtained from numerical solvers such as MOSEK, the framework includes a correction procedure that converts approximate SDP solutions into mathematically certified bounds suitable for use in Branch-and-Bound algorithms. The repository also implements an adaptation of the Goemans–Williamson randomized hyperplane rounding scheme to constrained binary optimization, together with problem-specific feasibility restoration. Computational experiments are provided for the Sparsest k-Subgraph and Maximum Independent Set problems. The work presented in this repository was funded and developed under the QBIQ project (project no. 644), funded by the Slovenian Research and Innovation Agency (ARIS) through the Applied Projects programme. The code and accompanying data are intended to facilitate reproducibility of the computational results and provide a foundation for further research on exact SDP-based methods for constrained quadratic binary optimization.