
Accession Number : AD0778654
Title : Maximizing a Convex Quadratic Function Subject to Linear Constraints.
Descriptive Note : Management science research rept. Sep 72Jul 73,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas,Egon ; Burdet,ClaudeAlain
Report Date : JUL 1973
Pagination or Media Count : 42
Abstract : In the paper the authors discuss a new method for solving linearly constrained, nonconvex quadratic programs in which the maximand is convex (or the minimand is concave). The approach is based on the adaptation and generalization of the concept of outer polars, first developed in the context of integer programming; but the paper is intended to be selfcontained. The authors first construct a generalized polar set for arbitrary (linearly constrained) quadratic programs. The convexity assumption on the maximand is introduced and a second generalized polar is defined. The properties of these generalized polars are used to generate a cutting plane (the polar cut), akin to the intersection cuts used in integer programming. The polar cut is then compared to other cuts proposed in the literature (Hoang Tuy, Ritter, Konno). Next, the authors describe a constraintactivating algorithm, which does not use cutting planes, but constructs a polytope containing the feasible set and contained in its generalized polar, and such that a global maximum, if one exists, is attained at a vertex of this polytope. Finally, the constraintactivating algorithm is illustrated on a numerical example. (Modified author abstract)
Descriptors : *Quadratic programming, Convex sets, Theorems, Algorithms, Integer programming
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE