This paper considers the distribution of values $Q(x)$, $x \in \{ -1,1\}^n$, where Q is a quadratic form in n variables with real coefficients. Error estimates are established for approximations of the maximum and minimum values of Q on $\{ -1,1\}^n$ which can be obtained by semidefinite programming. Bounds are given involving the sum of the absolute values of the off-diagonal entries. Other bounds are given which are useful in the case of extreme skewness. Used in conjunction with earlier bounds of Nesterov in [Optim. Methods Softw., 9 (1998), pp. 141--160], these new bounds lead to improvements on the bound given by the trace. The trigonometric description of the maximum and minimum given in [Optim. Methods Softw., 9 (1998), pp. 141--160], which is based on the rounding argument introduced by Goemans and Williamson in [J. Assoc. Comput. Mach., 6 (1995), pp. 1115--1145], is a major tool in obtaining these bounds.
This paper considers the distribution of values Q(x), x∈{−1,1}n, where Q is a quadratic form in n variables with real coefficients. Error estimates are established for approximations of the maximum and minimum values of Q on {−1,1}n which can be obtained by semidefinite programming. Bounds are given involving the sum of the absolute values of the off-diagonal entries. Other bounds are given which are useful in the case of extreme skewness. Used in conjunction with earlier bounds of Nesterov in [Optim. Methods Softw., 9 (1998), pp. 141--160], these new bounds lead to improvements on the bound given by the trace. The trigonometric description of the maximum and minimum given in [Optim. Methods Softw., 9 (1998), pp. 141--160], which is based on the rounding argument introduced by Goemans and Williamson in [J. Assoc. Comput. Mach., 6 (1995), pp. 1115--1145], is a major tool in obtaining these bounds.
In this paper we study the approximation algorithms for a class of discrete quadratic optimization problems in the Hermitian complex form. A special case of the problem that we study corresponds to the max-3-cut model used in a recent paper of Goemans and Williamson J. Comput. System Sci., 68 (2004), pp. 442-470]. We first develop a closed-formformula to compute the probability of a complex-valued normally distributed bivariate random vector to be in a given angular region. This formula allows us to compute the expected value of a randomized (with a specific rounding rule) solution based on the optimal solution of the complex semidefinite programming relaxation problem. In particular, we present an [m2(1−cosm2π)/8π]-approximation algorithm, and then study the limit of that model, in which the problem remains NP-hard. We show that if the objective is to maximize a positive semidefinite Hermitian form, then the randomization-rounding procedure guarantees a worst-case performance ratio of π/4≈0.7854, which is better than the ratio of 2/π≈0.6366 for its counterpart in the real case due to Nesterov. Furthermore, if the objective matrix is real-valued positive semidefinite with nonpositive off-diagonal elements, then the performance ratio improves to 0.9349.
In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.
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.
We study how well functions over the boolean hypercube of the form fk(x)=(∣x∣−k)(∣x∣−k−1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in ℓ∞-norm as well as in ℓ1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on ℓ1-approximation of fk; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from his work; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.
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.
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.