问题标签 [simplex]

从用户的“猜测”顶点初始化单纯形以用于 Nelder-Mead 单纯形搜索的最佳方法是什么？

我正在尝试使用 Apache Commons 解决优化问题。我在这里找到了 Commons Math 2 的“Hello World”示例。但是，我想使用 Commons Math 3.2，但找不到任何关于如何使用这部分代码的示例：

具体来说，我不知道什么是 optData 以及我将约束放在哪里。如果有人向我指出如何使用 org.apache.commons.math3.optim 库的“Hello World”示例，我将不胜感激。

我一直在按照 Nathan Reed在 Programmers.StackExchange 上的要求阅读这篇文章。 经过一番阅读，我偶然发现了一个我真的不明白的段落。谁能用更简单的语言向我解释这一段？（英语不是我的母语）如果你想阅读原文，你可以在“ ”下找到它。Moving from interpolation to summation

单纯形噪声使用来自每个角的贡献的直接总和，其中贡献是梯度斜坡的外推和径向对称衰减函数的乘积。在信号处理方面，这是一个信号重建内核。仔细选择径向衰减，以便每个角的影响在穿过边界到下一个单纯形之前达到零。这意味着单纯形内的点只会受到该特定单纯形角的贡献的影响。

我已经尝试实现 Simplex Noise 大约一个月了，我确实理解使用 Simplices 来减少所需的计算量以及梯度方面的安全功率的想法。但是，将其实现为任何语言似乎都是不可能的任务。

在我找到的每一个、每一个、每一个代码、我阅读的资源中，无处不在，代码似乎有一个 G 和一个 P 表。通过一些谷歌搜索和四处询问，我了解到它们是一个排列和梯度表。他们在做什么？为什么我们需要它们？

我目前的想法是排列表只包含随机值，因此不必在运行时计算它们。

例子：

• http://cabbynode.net/2012/06/10/perlin-simplex-noise-for-c-and-xna/
• http://www.6by9.net/simplex-noise-for-c-and-python/
• http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
• http://www.csee.umbc.edu/~olano/s2002c36/ch02.pdf

我试图解决这个线性规划问题：

max cx : Ax <= b, x >= 0

这是这个不错的LPP 求解器的片段：

其中第三个参数是'c'，第四个是'A'，第六个是'b'。第五给出方向'<='。

我也试过这些：

http://algs4.cs.princeton.edu/65reductions/Simplex.java.html

和

我不能在这里写它，因为我的声誉太低（http: slash slash lpsolve dot sourceforge dot net slash 5.5 slash）

第一个抛出“给定的 LPP 是无限的”错误。最后两个给出了这个结果：

原始的：{0.0, 0.1, 0.1, 0.0, 0.0, 0.3, 0.0, 0.0, 0.0, 0.0, 0.0, 0.3}

和价值：0.8。

我将这些用于其他各种示例并得到了相同的结果。

什么是正确的解决方案？我错过了什么？

给定两个（低维，可能是二维的）单纯复形 P 和 Q，是否有一种有效的算法来构造 P'，P 的子集由 P 中的所有点组成，这些点与 Q 中的某个点 q 最接近？

例如，如果 P 和 Q 是非退化相交线段，则 P' 将是它们的交点；如果它们不相交，则 P' 将是一个点或段。如果 P 是线段而 Q 是三角形，则 P' 将是 Q 到 P 上的投影。如果 P 是三角形并且 Q 是与 P 相交的线，则 P' 将由多个入射线段组成，从内部和/或三角形的外部。

一些图片示例：（带有点相交的那个是不正确的）

一般来说，P' 似乎由 Q 在 P 的每个面（任何维度）上的投影组成，但该描述包括大量以高维面为主的面，我不清楚如何处理有效地。

考虑以下线性规划算法，用 Ax <= b 最小化 [c,x]。

(1) 从可行点 x_0 开始

(2) 给定一个可行点 x_k，找到最大的 alpha 使得 x_k - alpha.c 是可接受的（直截了当，看看 A.x0 与 Ac 的分量的比率）

(3) 取法线单位向量n到我们刚刚到达的超平面，指向内。在平面 [c,.] 上投影 n，给出 r = n - [n,c]/[c,c].c，然后寻找 x_k - alpha.c + beta.r 允许的最大 beta。设置 x_{k+1} = x_k - alpha.c + 1/2*beta.r

如果 x_{k+1} 在公差范围内与 x_k 足够接近，则返回它，否则转到（2）

基本思想是跟随梯度直到撞到墙壁。然后，不是像单纯形算法那样跟随单纯形的外壳，而是将解决方案踢回到单纯形内部，在一个解决方案不差的平面上，在法向量的方向上。解决方案在该方向上的起点和下一个约束之间移动。它并不比以前更糟，但现在它更“在”单纯形“内部”，它有机会向最佳状态迈进一大步。

• 尽管碰到多个超平面的交点的概率为 0，但如果一个在一定容差内足够接近多个超平面，则可以取法线的平均值。

• 这可以通过在函数级别上遵循测地线来推广到任何凸目标函数。特别是对于二次规划，将解旋转到单纯形的内部。

问题：

• 该算法是否有名称或属于线性规划算法的类别？

• 它有我忽略的明显缺陷吗？

我一直在研究一个程序来解决使用修正单纯形法的任何最大化 LPP。我有一个问题，因为我试图输入一个序列来解决非基本变量的问题。我的代码如下：

gauss 和 getpiv 命令是为在该程序中工作而编写的程序，这些工作正常。然而，在执行此过程时，Maple 返回消息“错误，（在 matmax 中）无法执行 seq”如果有人可以就如何解决这个问题给我任何帮助，我们将不胜感激。

我正在尝试编写一个程序来解决饮食问题http://www.phpsimplex.com/en/diet_problem.htm

使用 SIMPLEX 算法。我的任务还需要计算算法的效率。

我从 wiki http://en.wikipedia.org/wiki/Simplex_algorithm了解到，在最坏的情况下它具有指数时间。但它没有显示确切的大 O 符号，或者我如何计算它。

对于上述饮食问题，我如何计算 Simplex 算法的效率有什么建议吗？

我创建了以下最大化目标函数的单纯形算法。我希望相反的事情发生。在此示例中，有两个变量，算法必须计算出将这两个变量（13.0 和 23.0）乘以什么，以便在约束集中获得最大可能的结果。我希望算法找出可能的最低结果。

我的代码：

如果您需要更多信息，请询问。任何帮助表示感谢。