Quadratically constrained quadratic programming: Some applications and a method for solution

The problem (QPQR) considered here is: minimizeQ₁ (x) subject toQ_i (x) 0,i M₁ {2,...,m},x P Rⁿ, whereQ_i (x), i M {1} M₁ are quadratic forms with positive semi-definite matrices, andP a compact nonempty polyhedron of Rⁿ. Applications of (QPQR) and a new method to solve it are presented.Letu S={u R^m;u 0, u_i= l}be fixed;then the problem:iM minimize u_iQ_i (x (u)) overP, always has an optimal solutionx (u), which is either feasible, iM i.e.u C₁ {u S;Q_i (x (u)) 0,i M₁} or unfeasible, i.e. there exists ani M₁ withu C {u S; Q_i(x(u)) 0}.Let us defineC_i C_i S_i withS_i {u S; u_i=0}, i M. A constructive method is used to prove that C_i is not empty and thatx (û) withiM û C_i characterizes an optimal solution to (QPQR). Quite attractive numerical results have been reached with this method.

---

Zusammenfassung Die vorliegende Arbeit befaßt sich mit Anwendungen und einer neuen Lösungsmethode der folgenden Aufgabe (QPQR): man minimiere eine konvexe quadratische ZielfunktionQ_i (x) unter Berücksichtigung konvexer quadratischer RestriktionenQ_i (x) 0, iM₁ {2,...,m}, und/oder linearer Restriktionen.·Für ein festesu S {u R^m;u 0, u_i=1},M {1} M₁ besitzt das Problem:iM minimiere die konvexe quadratische Zielfunktion u_i Q_i (x (u)) über dem durch die lineareniMRestriktionen von (QPQR) erzeugten, kompakten und nicht leeren PolyederP Rⁿ, immer eine Optimallösungx (u), die entweder zulässig ist:u C₁ {u S;Q₁ (x (u)) 0,i M₁} oder unzulässig ist, d.h. es existiert eini M₁ mitu C_i {u S;Q_i (x(u))0}.Es seien folgende MengenC_i C_i S_i definiert, mitS_i {u S;u_i=0}, i M. Es wird konstruktiv bewiesen, daß C_i 0 undx (û) mitû C_i eine Optimallösung voniM iM(QPQR) ist; damit ergibt sich eine Methode zur Lösung von (QPQR), die sich als sehr effizient erwiesen hat. Ein einfaches Beispiel ist angegeben, mit dem alle Schritte des Algorithmus und dessen Arbeitsweise graphisch dargestellt werden können.

---

---

An earlier version of this paper was written during the author's stay at the Institute for Operations Research, Swiss Federal Institute of Technology, Zürich.