它是一个具有线性不等式约束的二次规划，可以通过活动集方法有效地求解。我在我的优化课程中将实现此方法作为家庭作业，并且假设您有一个求解器来解决您需要在每次迭代中求解的线性系统，我的学生最多不会花费几个小时。

我建议只遵循 Nocedal-Wright 中的描述（Nocedal 和 Wright：“数值优化”）。该算法非常简单，您可能不会花费更多时间来实现它，而不是习惯其他库的接口。更好的是，如果其他答案和评论之一出现了免费的 QP 求解器，那么将活动集方法包裹在它周围是非常简单的。

如果我正确阅读了您的描述，您想解决：

$$\begin{align} & \min_{x} \|x - p\|^{2}_{2} \\ \textrm{s.t.} & n_{i} \cdot x \geq \delta_{i}, i = 1,\ldots, N, \end{align}$$

假设你有$N$超平面。正如您所指出的，这个程序是一个凸二次程序（QP）。

如果您了解 Python，则可以尝试在 SciPy 和 OpenOpt 中使用 BSD 许可的约束 QP（或非线性规划）求解器。

由于这个问题是一个凸 QP，它也可以被重新表述为一个半定规划 (SDP)。DSDP 具有类似 BSD 的许可证，因此您也可以尝试使用该求解器（但请阅读许可证以确保；IANAL）。

遗憾的是，优化软件本身就是为了赚钱，所以任何好的软件要么是商业的，要么是“免费”许可证有很多限制（GPL、学术用途、非商业用途、个人用途等）

如果有一种快速算法可以利用您的特定问题结构，我不会感到惊讶。

不是一个很好的解决方案，但我现在正在做的事情：

由于问题在$R^3$，在正确的解中最多可以有 3 个活动平面约束（不等式转为等式）。再多的话，至少其中一个是多余的。因此，我从$n$不平等（$\tbinom{n}{3}$+$\tbinom{n}{2}$+$\tbinom{n}{1}$+ 1) 并找到产生一个满足所有其他不等式约束并且最接近目标点的点（或者实际上，我将所有内容转换为目标点为原点，并找到满足的最小范数的候选点所有约束）。

给定最多三个平面约束（平面约束的数量为$d$)，我将它们逐行堆叠以产生一个$d$X$3$矩阵$A$并且类似地产生一个$d$X$1$向量$\delta$. 我构建系统$A x = \delta$，并使用正规方程以最小二乘法求解。例如：$x = (A^TA)^+A^T\delta$. 我发现伪逆$A^TA$使用基于四元数的 3x3 对称矩阵的谱分解（参见clicky）。那是，$(A^TA) = Q D Q^T$, 对于正交矩阵$Q$和一个对角矩阵$D$， 所以$(A^TA)^+ = Q D^+ Q^T$. $D^+_{i,i} = 1/D_{i,i}$如果$D_{i,i} > 0$， 和$0$否则。

要检查一个点是否满足所有平面不等式，我只需一次检查所有平面。

...

这会产生一个$O(n^4)$算法：$O(n^3)$3架飞机的组合生产$O(n^3)$需要检查的点。每项检查都需要针对所有$O(n)$点。

它不是特别聪明，而且对于大型$n$它会太慢，但它的编码和测试相对简单，并且能够利用我现有的四元数和 matrix3 代码。

有没有什么更聪明的事情我可以做而不需要更复杂的数学工具？我没有将军$n$X$n$矩阵库仅利用四元数、3x3 矩阵、4x4 矩阵和 3d/4d 向量。