An algorithm for global minimization of linearly constrained concave quadratic functions. (English) Zbl 0638.90081

Kalantari, B.; Rosen, J. B.

Math. Oper. Res. 12, 544-561 (1987).

We present an algorithm for the global minimization of a quadratic function \(\psi(x,y)=x^ TQx+h^ Tx+d^ Ty\), over a polytope \(\Omega =\{(x,y)\in {\mathcal R}^{n+k}:\) \(Ax+By\leq b\), \(x\geq 0\), \(y\geq 0\}\), where \(x,h\in {\mathbb{R}}^ n\), y,d\(\in {\mathcal R}^ k\), \(b\in {\mathcal R}^ m\), and where A and B are \(m\times n\) and \(m\times k\) matrices, respectively, and Q is an \(n\times n\) symmetric positive definite matrix.
We first consider the case where \(k=0\) and construct a “tight” parallelepiped R, containing \(\Omega\) by using an arbitrary set of Q- conjugate directions and by solving 2n linear programs. We show that the convex envelope of \(\psi\) with respect to R is linear and obtain an explicit formula for it. We then describe a branch and bound algorithm in which the linearity of the convex envelope allows efficient lower bounding for the subproblems. For each subproblem we obtain the liorphically onto a corresponding lower level set of the other one. In case that \({\mathcal P}(\bar f,\bar H,\bar G)\) is equivalent with \({\mathcal P}(f,H,G)\) for all \((\bar f,\bar H,\bar G)\) in some neighborhood of \((f,H,G)\) we call \({\mathcal P}(f,H,G)\) structurally stable; the topology used takes derivatives up to order two into account. Under the assumption that M[H,G] is compact we prove that structural stability of \({\mathcal P}(f,H,G)\) implies the following three conditions:
(C1) The Mangasarian-Fromovitz constraint qualification is satisfied at every point of \(M[H,G]\).
(C2) Every Kuhn-Tucker point of \({\mathcal P}(f,H,G)\) is strongly stable in the sense of Kojima.
(C3) Different Kuhn-Tucker points have different (f-) values.
On the other hand, again in case M[H,G] is compact, we conjecture that the conditions C1, C2 and C3 imply structural stability.

MSC:

90C20	Quadratic programming
65K05	Numerical mathematical programming methods

Keywords:

global minimization; symmetric positive definite matrix; Q-conjugate directions; branch and bound; efficient lower bounding; liorphically onto a corresponding lower level set of the other one. In case that \({\mathcal P}(\bar f,\bar H,\bar G)\) is equivalent with \({\mathcal P}(f,H,G)\) for all (\=f,\=H,Ḡ) in some neighborhood of (f,H,G) we call \({\mathcal P}(f,H,G)\) structurally stable; the topology used takes derivatives up to order two into account. Under the assumption that M[H,G] is compact we prove that structural stability; Mangasarian-Fromovitz constraint qualification