I'm considering quadratic programming problems of the form:
$$ \max x^tQx+Bx$$
subject to the linear constraint
$$ Ax \le b $$ I read that if is the case that
$$ x^tQx + Bx \ge 0 \ \forall x$$ or $$ x^tQx + Bx \le 0 \ \forall x$$
Then the objective can be declared as positive semidefinite and negative semidefinite respectively.
Furthermore if positive semidefinite, the solution to the program can be recovered in polynomial time.
https://en.wikipedia.org/wiki/Quadratic_programming#Complexity
I don't think I understand what they mean. Consider the following 0-1 Integer Program
$$ \max \left(x_1 - \frac{1}{2}\right)^2 + \left(x_2 - \frac{1}{2}\right)^2 + \left(x_3 - \frac{1}{2}\right)^2 ... \left(x_n - \frac{1}{2}\right)^2 $$
$$ Ax \le b $$
This amounts to "find the point furthest away from the center of n-dimensional unit cube subject to linear constraints."
The Hessian of our objective function is
$$ \begin{pmatrix} 2 \ 0 \ ... \ 0 \\ 0 \ 2 \ ... \ 0 \\ \vdots \ \vdots \ \ddots \ \vdots \\ 0 \ 0 \ ... \ 2\end{pmatrix}$$
Which is clearly positive semi-definite. (Again our objective function is a sum of squares so it is always greater than or equal to 0).
But if this could be solved in polynomial time, then the decision problem of 0-1 integer programming, does there exist a solution A to the problem instance of 0-1 integr programming Q, could be solved in polynomial time lets say P(n).
Then it follows that in P(n)log(n) (by binary search on the max value of objective function) we could solve 0-1 integer programming, P=NP... the world collapses and I get a million bucks and move to Antarctica.
Obviously, thats ridiculous. So what mistake did I make in that analysis?
Leaving aside the issue of your reduction from a 0,1 to a continuous problem, which I didn't quite follow but seems highly suspicious, there is a far more basic issue. The quadratic minimization problem is polynomially solvable if $Q$ is positive semidefinite, but here you have a maximization problem.