Nonconvex Quadratic Programming via Generalized Polars

Author:
  • EBEgon Balas
    Egon Balas
Publisher website
Google Scholar
Abstract
A new approach is proposed to linearly constrained nonconvex quadratic programming. The approach is based on generalized polar sets, and is akin to the convex analysis approach to integer programming. We construct a generalized polar of the Kuhn–Tucker polyhedron associated with a quadratic program. This generalized polar is a convex polyhedral cone whose interior contains no complementary feasible solution better than the best known one. This and other properties are used to generate cutting planes similar to the outer polar cuts used in 0-1 programming. An algorithm is then proposed, which does not use cutting planes, but constructs a polytope containing the feasible set and contained in the polar of the latter. This is done by starting with a simplex defined by a subset of the problem constraints, and successively activating other problem constraints, until the resulting polytope is contained in the polar of the feasible set. When this is achieved, the best complementary solution found in the process is optimal, or none exists.