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!

  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jun 24 '19 at 16:14
  • $\begingroup$ @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 $\endgroup$ – independentvariable Jun 24 '19 at 16:17
  • $\begingroup$ @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 $\endgroup$ – independentvariable Jun 24 '19 at 16:18
  • 4
    $\begingroup$ Even worse, already checking local optimality of a given feasible point of a nonconvex QP is NP-hard (Pardalos 87) $\endgroup$ – Johan Löfberg Jun 24 '19 at 16:45
  • 4
    $\begingroup$ 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) $\endgroup$ – Johan Löfberg Jun 24 '19 at 17:10

In addition to the references already given in the comments, this paper (DOI link) demonstrates that exact solutions to some non-convex quadratic programs are given by semi-definite programming, and whenever the SDP relaxation is tight we can actually solve the SDP via SOCP!

In general the SDP relaxation will of course not be tight, but as shown by Nemirovski et. al. (DOI link) we can provide some constant factor guarantees when the sufficient condition does not hold.

  • $\begingroup$ What do you mean by "solving the SDP via SOCP"? $\endgroup$ – JakobS Jul 1 '19 at 8:05
  • 1
    $\begingroup$ If the QCQP admits a unique solution and the SDP relaxation is tight then it admits a rank-1 solution, so it suffices to enforce the 2x2 minor constraints, which are SOCP representable. $\endgroup$ – Ryan Cory-Wright Jul 1 '19 at 13:29

With the exception of special cases, this problem is NP-hard. One interesting case is that minimizing a convex or concave function over a simplex can be solved in polynomial time. In other special cases it is also possible to linearise the problem through reformulations. In the general case however this would be solved by relaxing the objective and using branch and bound to find the global optimum.

It is interesting to note that there are two parts to NP-hardness in optimisation: (i) finding a solution, and (ii) verifying the solution. Because verifying the solution cannot be done in polynomial time, even if we have a solution it is still NP-hard to prove that it is globally optimal.

We see this a lot in practice as well. In global optimisation finding a solution is the easy part - the difficult part is to prove/disprove that it is globally optimal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.