I'm trying to learn the complexity of a quadratic program in the form of:



given only $x*y$





$x,y,a,b >0$

  1. What I want to learn is that, is there a polynomial time algorithm for this quadratic progamming definiton by any means such as ellipsoid method, simplex method, interior point method? I assume that stochastic optimization technics can only provide good approximations (it can even not be possible if the problem is NP-Hard). There are many complexity results which vary according to an even smallest problem definition and it becomes confusing as I dig further. For example a result from Pardalos et.al states "Quadratic programming with one negative eigenvalue is NP-hard". But there is also Nesterov & Nemirovski's result: polynomial-time interior-point methods for nonlinear convex programming". In theory, convexity of the definition can make it tractable again. So what is the situation for this exact definition?

  2. I know that for the large problem sizes (for example a large bit size like 50) , even though the underlying method is efficient there can be issues related to asymptotical efficiency, mostly because of rounding errors. Can advanced methods like interior point get an exact solution for a large problem size or can we only expect an approximation?

  3. Confining all the variables to integers makes this one an integer non-linear program. As known, almost all integer programs are NP-Hard. Does this definition also suffer from this fact, or any advanced method (not necessarily limited to those mentioned above) can also find a global integer optimum? Also I would like to learn if there's an efficient exact real-world solver for this type of problem? Due to the hardness assumptions mentioned for both non-linear and integer programming, I assume that the integer version is much beyond tractibility (perhaps NP-Hard).

  • $\begingroup$ With $\sqrt{xy}$ in the constraints, why should this even be a QP? $\endgroup$ – Rodrigo de Azevedo Feb 14 '18 at 9:15
  • $\begingroup$ We can assume an integer for x+y and that resumes QP, right? (or perhaps I'm missing something) $\endgroup$ – msalperen Feb 14 '18 at 9:49
  • $\begingroup$ I mean we can assume a constant integer for that inequality constraint, for instance x+y>100 during the runtime. $\endgroup$ – msalperen Feb 14 '18 at 10:10
  • 1
    $\begingroup$ What does the line "given only $x*y$" mean??? Does it mean that the value of the product $xy$ is specified as another constraint? If yes, why is this not given as a constraint? If no, then the constraint system is homogeneous, so that the objective value can be brought arbitrarily close to 0 or minus infinity. $\endgroup$ – Gamow Feb 14 '18 at 13:19
  • 1
    $\begingroup$ @RodrigodeAzevedo Well, $x+y>3\sqrt{xy}$ is equivalent to $x+y>0$ and $x^2-7xy+y^2>0$ (just square the two sides). $\endgroup$ – Emil Jeřábek Feb 14 '18 at 14:17

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.