计算科学 - 凸空间约束表达式的极值点 - 吾爱随笔录

计算科学凸优化凸包

2021-12-02 09:26:47

我正在寻找凸集的极值点 $S\subset [-1,1]^{n\times 3}$ 和 $r\in S$ 这样

r_{i} \geq r_{k} ⟺ i \geq k,

$\begin{equation} r_{i} \ge r_{k} \iff i\ge k, \end{equation}$ 其中第一个不等式是指字典中的不等式

R^{3}

$\mathbb{R}^3$ ，和

\sum_{i}^{n} r_{i} = 0

$\begin{equation} \sum_i^n r_i = 0 \end{equation}$ 很容易表征仅满足第一组约束的极值点。第二组已被证明更加困难，我不想在已经有解决方案的情况下浪费我的时间。

是否有任何程序包或方法可以轻松解决此问题？如果是这样，它们是什么？

1个回答

我能找到的最有信誉的来源是

我戴尔，LG Proll。一种确定凸多面体所有极值点的算法，数学规划，卷。12，第 1 期，p。81-96。

这个问题可能只有在凸多面体的情况下才能解决；有一个定理指出，凸多面体可以用有限数量的极值点和有限数量的极值射线的凸组合来表示。一般来说，不能对凸集做出这样的声明。

算法运行时间将是多面体维度的指数。枚举所有顶点 $n$ -立方体，所有 $2^n$ 必须枚举顶点。这个问题可能是 NP 难的。

其它你可能感兴趣的问题