0
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ It might be the case that my mistake is that positive semidefinite objectives can only be minimized, and not necessarily maximized $\endgroup$ Aug 4, 2015 at 18:26
  • $\begingroup$ Your mistake is bringing $\{0,1\}$ into it. That changes everything. The Wikipedia article does not address that, it refers only to the continuous case. $\endgroup$ Aug 4, 2015 at 19:39
  • $\begingroup$ @MichaelGrant a 0-1 integer program can be rewritten as does there exist an integer vector satisfying constraints Ax<=b. 0 <= x <= 1, this becomes the quadratic program max: (x -1/2)^2, Ax <= b. A rapid solution to the latter allows you to solve the originally with only log(obj value) more queries $\endgroup$ Aug 4, 2015 at 19:42
  • $\begingroup$ Again, that is simply not the model being addressed in the Wikipedia article. The article deals only with continuous variables. $\endgroup$ Aug 4, 2015 at 19:43
  • $\begingroup$ But that's fine, since I have changed the problem into a purely continuous one by the transformations highlighted $\endgroup$ Aug 4, 2015 at 19:46

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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