# 二次計画の複雑さ

\$ f（x、y）= x ^ 2-y ^ 2-4xy \$

s.t.

\$ x = a + b \$

\$ y = a-b \$

\$x+y>3,sqrt{xy}\$

\$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).

ベストアンサー