Accession Number : AD0778654

Title :   Maximizing a Convex Quadratic Function Subject to Linear Constraints.

Descriptive Note : Management science research rept. Sep 72-Jul 73,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Balas,Egon ; Burdet,Claude-Alain

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 self-contained. 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 constraint-activating 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 constraint-activating 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