1
$\begingroup$

  1. If $$\min x'Qx + Rx$$ $$Ax\leq b$$ $$x\in\mathbb Z^n$$ is a quadratic program with $x'Qx$ is convex is there a polynomial time algorithm for this if $A$ is totally unimodular?

  2. In particular if we ask that the smallest $x'Qx$ that touches on a vertex of $AX\leq b$ is that in $\mathcal P$?

We know that it is in $\mathcal P$ if $Q=0$. We also know for trivial reasons it will always first touch a vertex point.

Is it the same for convex case?

If not in what cases can be find minimum $x'Qx$ that first touch a vertex point in $\mathcal P$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This sort of problems are NP-hard even if $A=0$. For instance integer least squares https://web.stanford.edu/~boyd/papers/pdf/int_least_squares.pdf

Your other question (the optimal vertex) is just as hard - consider binary least squares (ie. the restrict to the unit cube).

Improve this answer
$\endgroup$
1
  • $\begingroup$ However it seems that if the compact polytope is far away from the origin (the binary cube is close to origin) in a generic position the first point an ellipsoid with center close to origin would hit as it grows in volume would be a vertex point. Also I have a convex objective here. $\endgroup$
    – Turbo
    Commented May 4, 2018 at 12:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .