多项式可解性

计算科学 优化 非线性规划 凸优化
2021-12-25 03:53:47

考虑以下优化问题:

x (i,j,t,s)Ir||xixjxtxs||2

英石:xC;

在哪里x=(x1,x2,...xn)xj0j=1,2,...,n

这里,C是一个凸集并且Ir是一个多项式大小的索引集。

这个问题可以在多项式时间内解决吗?

1个回答

一般来说,没有。

不失一般性,假设Ir={(1,2,3,4)}, 然后让F(x1,x2,x3,x4=x1x2x3x42. 考虑要点(1,3,0,0)(3,1,0,0); 他们的中点是(2,2,0,0). 如果F是凸的,那么这将是真的

F(2,2,0,0)12F(1,3,0,0)+12F(1,3,0,0).

然而,

16129+129.

一般来说,非凸问题是 -hard。NP