Global optimization of a quadratic function subject to a bounded mixed integer constraint set (Q2640438)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Global optimization of a quadratic function subject to a bounded mixed integer constraint set
scientific article

    Statements

    Global optimization of a quadratic function subject to a bounded mixed integer constraint set (English)
    0 references
    0 references
    0 references
    0 references
    1990
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    NP-hard
    0 references
    global solution
    0 references
    mixed integer nonconvex quadratic program
    0 references
    branch and bound
    0 references
    underestimation
    0 references
    relaxation
    0 references
    0 references