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

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
Full Text: