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 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.
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.
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.
The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.
We investigate various solution approaches for the uncon-strained minimization of a pseudo-boolean function. Moreprecisely, we assume that the original function is expressedas a real-valued polynomial in 0-1 variables, of degree threeor more, and we consider a generic family of two-step ap-proaches for its minimization. First, a quadratic reformu-lation step aims at transforming the minimization probleminto an equivalent constrained or unconstrained quadratic0-1 minimization problem (where “equivalent” means herethat a minimizer of the original function can be easily de-duced from a minimizer of the reformulation). Second, anoptimization step handles the obtained equivalent quadraticproblem.We provide a unified presentation of several quadratic re-formulation schemes proposed in the literature, e.g., (An-thony et al. 2017; Buchheim and Rinaldi 2007; Rodr ́ıguez-Heck 2018; Rosenberg 1975), and we review several meth-ods that can be applied in the optimization step, includinga standard linearization procedure (Fortet 1959) and moreelaborate convex quadratic reformulations, as in (Billionnetand Elloumi 2007; Billionnet, Elloumi, and Lambert 2012,2016; Elloumi, Lambert, and Lazare 2021). We discuss theimpact of the reformulation scheme on the efficiency of theoptimization step and we illustrate our discussion with somecomputational results on different classes of instances.
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 research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.