Maximizing a Convex Quadratic Function Subject to Linear Constraints.

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