您最初的问题陈述含糊不清，因为您没有描述如何对凸集$D$进行编码。

问题立即简化为

$\max \| p \|^{2}$

受制于

$p \in D$。

我们将通过减少 0-1 整数线性规划的可行性来证明这个问题是 NP-Hard 的。

0-1 整数线性规划可行性问题是一个众所周知的 NP 完全问题：“给定整数矩阵和，是否存在一个 0-1 向量使得？” $A$$b$$x$$Ax=b$

考虑变量的变化。那么我们最初的问题就变成了“对于是否有一个向量具有，使得？很容易看出，这种转换产生了一个新的大小多项式实例，其大小与原始问题的大小相同。 $y_{i}=2x_{i}-1$$y$$y_{i}=\pm 1$$i=1, 2, \ldots, n$$\hat{A}y=\hat{b}$

现在，假设我们可以解决

$\max \| y \|^{2}$

受制于

$\hat{A}y=\hat{b}$

$-1 \leq y_{i} \leq 1$，对于。$i=1, 2, \ldots, n$

在多项式时间内。当且仅有一个所有条目都是的解决方案时，最佳值为。这个优化问题的可行集显然是凸的。找到最优的多项式时间算法将为我们提供用于原始 0-1 ILP 可行性问题的多项式时间算法。 $n$$y$$\pm 1$$y$

这表明，总的来说，问题

$\max \| p \|^{2}$

受制于

$p \in D$

是 NP-Hard，即使被限制为凸的。 $D$

证明完全问题在多项式时间内简化为您的问题。非凸优化的一个典型例子是Murty 和 Kabadi 从子集总和减少到非凸优化。对于您的具体问题，您将不得不制定类似类型的减少。您可能能够利用在二次约束二次程序上完成的工作。$\mathcal{NP}$