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.


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?

  • $\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 '15 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 '15 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 '15 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 '15 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 '15 at 19:46

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.


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.