Global optimization of a quadratic function subject to a bounded mixed integer constraint set
This paper deals with the NP-hard problem of finding a global solution to a mixed integer nonconvex quadratic program. A branch and bound algorithm is presented which requires the solution of linear programming subproblems at each node. The method is based on underestimation of the objective function and relaxation of the integer restriction. Two piecewise affine underestimating functions are developed for the function \(x^ tQx+c^ tx\) over a rectangular set \(\ell \leq x\leq L\). Noting that \(x^ ty=x^ tQx+c^ tx\) for \(y=Qx+c\), bounds \(m\leq y\leq M\) are given by \(m_ i=\min \{Q_ ix+c_ i:\ell \leq x\leq L\}\) and \(M_ i=\max \{Q_ ix+c_ i:\ell \leq x\leq L\}\), where \(Q_ i\) denotes the ith row of Q. Taking the convex envelope of \(x^ ty\) over \(\ell \leq x\leq L\), \(m\leq y\leq M\), and projecting gives an affine underestimate for \(x^ tQx+c^ tx\). Alternatively, substituting \(y_ i=Q_ ix+c_ i\) into the expression for the convex envelope yields a piecewise affine and convex underestimate. For the pure 0-1 integer case, the latter underestimate reduces to a reformulation of a quadratic binary program due to \textit{F. Glover} [Management Sci. 22 (1975), 455-460 (1976; Zbl 0318.90044)]. Overestimating functions based on concave envelopes are also derived. These are useful in establishing error bounds on the approximations and thereby ensuring finite convergence for a given tolerance.
- Global optimization techniques for solving the general quadratic integer programming problem
- scientific article; zbMATH DE number 3902395
- Branch-and-bound method for the minimization problem for a nonconvex quadratic function under convex quadratic constraints
- Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint
- An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
- A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- An algorithm for indefinite integer quadratic programming
- Constrained global optimization: algorithms and applications
- scientific article; zbMATH DE number 4077256 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- Improved algorithm for mixed-integer quadratic programs and a computational study
- Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
- Jointly Constrained Biconvex Programming
- Jointly constrained bilinear programs and related problems: An overview
- The Indefinite Quadratic Programming Problem
- The perfectly matchable subgraph polytope of a bipartite graph
- The perfectly matchable subgraph polytope of an arbitrary graph
- Generalized bilinear programming. I: Models, applications and linear programming relaxation
- A new reformulation-linearization technique for bilinear programming problems
- Global optimization of a quadratic functional with quadratic equality constraints
- Global optimization techniques for solving the general quadratic integer programming problem
- On global integer extrema of real-valued box-constrained multivariate quadratic functions
- A relaxation method for nonconvex quadratically constrained quadratic programs
- A reformulation-convexification approach for solving nonconvex quadratic programming problems
- A feasible active set method with reoptimization for convex quadratic mixed-integer programming
- Global optimality conditions for mixed integer quadratic programming problems
- Convex quadratic underestimation and Branch and Bound for univariate global optimization with one nonconvex constraint
- Two-stage quadratic integer programs with stochastic right-hand sides
- scientific article; zbMATH DE number 1054662 (Why is no real title available?)
- scientific article; zbMATH DE number 2167564 (Why is no real title available?)
- Box-constrained mixed-integer polynomial optimization using separable underestimators
- Optimization of a quadratic function with a circulant matrix
This page was built for publication: Global optimization of a quadratic function subject to a bounded mixed integer constraint set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2640438)
