Global optimality condition of non-convex quadratic programs

We know that a convex quadratic maximization (not minimization!) on a polyhedron has its global optimal value on a vertex.

Also, I have read in some papers that checking whether a vertex is globally optimal or not reduces to a simple condition. I am interested in that particular condition. Could you please help me with that -- either demonstrating or giving a reference would be great!

• Can you refer us to specific papers? Maybe this is implied by use of the term "polyhedron" rather than polytope, but presuming the constraint set is compact (i.e., bounded), then there is at least one global optimum at an extreme of the constraints (although n the case of a (linearly constrained concave Quadratic Program, that means at least one vertex of the constraints is a global optimum). Therefore, presuming yo have the computational resources ,a global optimum can be found by explicit enumeration, i.e., evaluating the objective at all vertices and choosing one with the best objective. Jun 24 '19 at 16:14
• @MarkL.Stone I don't mean enumeration. There is polynomial time solvable verification method as I see. For example the following 130 KB paper entitled Necessary and Sufficient Global Optimality Conditions for Convex Maximization Revisited: core.ac.uk/download/pdf/82490655.pdf Jun 24 '19 at 16:17
• @MarkL.Stone This paper is a very long one, but includes all the subdifferentials etc. and seems to be complicated. and it is a bit old. I am therefore curious to see the most recent, hopefully easy verification Jun 24 '19 at 16:18
• Even worse, already checking local optimality of a given feasible point of a nonconvex QP is NP-hard (Pardalos 87) Jun 24 '19 at 16:45
• It does not work with the vertex as a single object to draw any conclusion. It uses a branch-and-bound strategy, and then at some point the bounds have converged sufficiently (after possibly an exponential number of steps) Jun 24 '19 at 17:10