10
$\begingroup$

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!

Improve this question
$\endgroup$
10
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 17:10

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What do you mean by "solving the SDP via SOCP"? $\endgroup$
    – JakobS
    Jul 1, 2019 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, 2019 at 13:29
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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