Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cybernetics and Systems Analysis

Method of obtaining estimates in quadratic extremal problems with Boolean variables

N. Z. Shor, A. S. Davydov

Published Jan 1, 1985• 8 citations
Publisher
DOI
10.1007/bf01072102

Related papers

Simple bounds for Boolean quadratic problems

Yurii E. Nesterov

•Jan 1, 2009•1 citation

Approximate maximum-likelihood estimation using semidefinite programming

J. Dahl, Bernard H. Fleury, Lieven Vandenberghe

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 Processing•Mar 22, 2004•9 citations

A Characterization of Binary Quadratic Optimization Problems

최혜지

•Jan 1, 2018•0 citations

Quadratic Optimization in 0–1 Variables

Alain Billionnet

This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.

Wiley eBooks•Jul 10, 2014•2 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.

SIAM Journal on Optimization•Jan 1, 2005•4 citations

Bilinear programming methods for nonconvex quadratic problems

Springer eBooks•Oct 5, 2005•1 citation
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.
This chapter introduces some theoretical and algorithmic aspects of quadratic optimization in bivalent variables, which is, in general, an NP-hard problem. It discusses the central problem of quadratic optimization in 0–1 variables without constraints. The chapter reviews some results in the constraint case. It also discusses a property of pseudo-Boolean functions that is relatively rare in optimization. The chapter examines a formulation of the problem of maximizing a quadratic pseudo-Boolean functions (qpBf) using a mixed integer linear program. It focuses on the optimization of a function of bivalent variables subject to some constraints. This optimization model is extremely general and the chapter limits to the problem of optimizing a quadratic pseudo-Boolean function with linear constraints. The chapter shows that the optimal value of the dual Lagrangian problem is equal to the optimal value of the continuous relaxation of the classical linearization of the initial problem.
This paper considers the distribution of values Q(x)Q(x)Q(x), x∈{−1,1}nx \in \{ -1,1\}^nx∈{−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\{ -1,1\}^n{−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.