考虑以下优化问题:
敏xx ∑(i,j,t,s)∈Ir||xixj−xtxs||2∑(i,j,t,s)∈Ir||xixj−xtxs||2
英石:x∈C;x∈C;
在哪里x=(x1,x2,...xn)x=(x1,x2,...xn) 和xj≥0j=1,2,...,nxj≥0j=1,2,...,n
这里,CC是一个凸集并且IrIr是一个多项式大小的索引集。
这个问题可以在多项式时间内解决吗?
一般来说,没有。
不失一般性,假设Ir={(1,2,3,4)}Ir={(1,2,3,4)}, 然后让F(x1,x2,x3,x4=∥x1x2−x3x4∥2F(x1,x2,x3,x4=‖x1x2−x3x4‖2. 考虑要点(1,3,0,0)(1,3,0,0)和(3,1,0,0)(3,1,0,0); 他们的中点是(2,2,0,0)(2,2,0,0). 如果FF是凸的,那么这将是真的
然而,
一般来说,非凸问题是 -hard。NPNP