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.

IEEE International Conference on Acoustics Speech and Signal ProcessingMar 22, 20049 citations

Error Estimates in the Optimization of Degree Two Polynomials on a Discrete Hypercube

M. Marshall

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 \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.

SIAM Journal on OptimizationJan 1, 20055 citations

A Characterization of Binary Quadratic Optimization Problems

최혜지

Jan 1, 20180 citations

Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis

A. I. Pakhomchik, Vladimir Voloshinov, V. M. Vinokur +1 more

There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using the generic solvers for mixed-integer linear programming problems (MILP), but they require transforming expressions with Boolean functions to linear equations or inequalities. Here, we present two methods of such a transformation which applies to any Boolean function defined by explicit rules giving values of the Boolean function for all combinations of its Boolean variables. The first method represents the Boolean function as a linear equation in the original binary variables and, possibly, binary ancillaries, which become additional variables of the MILP problem being composed. The second method represents the Boolean function as a set of linear inequalities in the original binary variables and one additional continuous variable (representing the value of the function). The choice between the first or second method is a trade-off between the number of binary variables and number of linear constraints in the emerging MP problem. The advantage of the proposed approach is that both methods reduce important cryptanalysis problems, such as the preimaging of hash functions or breaking symmetric ciphers as the MILP problems, which are solved by the generic MILP solvers. Furthermore, the first method enables to reduce the binary linear equations to quadratic unconstrained binary optimization (QUBO), by the quantum annealer, e.g., D-Wave.There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using the generic solvers for mixed-integer linear programming problems (MILP), but they require transforming expressions with Boolean functions to linear equations or inequalities. Here, we present two methods of such a transformation which applies to any Boolean function defined by explicit rules giving values of the Boolean function for all combinations of its Boolean variables. The first method represents the Boolean function as a linear equation in the original binary variables and, possibly, binary ancillaries, which become additional variables of the MILP problem being composed. The second method represents the Boolean function as a set of linear inequalities in the original binary variables and one additional continuous variable (representing the value of the function). The choice between the first or second method is a trade-off between the number of binary variables and number of linear constraints in the emerging MP problem. The advantage of the proposed approach is that both methods reduce important cryptanalysis problems, such as the preimaging of hash functions or breaking symmetric ciphers as the MILP problems, which are solved by the generic MILP solvers. Furthermore, the first method enables to reduce the binary linear equations to quadratic unconstrained binary optimization (QUBO), by the quantum annealer, e.g., D-Wave.

AlgorithmsJan 21, 202223 citations

Bilinear programming methods for nonconvex quadratic problems

Springer eBooksOct 5, 20051 citation

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.