使用MATLAB解决全局优化算法的非凸优化

Question

我有一个简单的无约束非凸优化问题。由于这些类型的问题具有多个局部最小值，因此我正在寻找可产生独特/全局最小值的全局优化算法。在互联网上，我遇到了全局优化算法，如遗传算法，模拟退火等，但为了求解简单的一个变量无约束的非凸优化问题，我认为使用这些高级算法似乎不是一个好主意。任何人都可以推荐一个简单的全局算法来解决这种简单的变量无约束非凸优化问题吗？我非常感谢这方面的想法。

Answer 1

由于这是一个一维问题，事情更容易。 一个简单的最速下降过程可以使用如下。 假设搜索的时间间隔是a<x<b。

从最小化你的函数f（x）开始SD。你恢复第一个最小Xm1。你应该使用一个好的步骤，不要太大。 通过加上一个正的小常数Xm1 +ε来改变这一点。然后最大化f或最小化-f，从这一点开始。你得到f的最大值，你用ε来扭曲它，并从那里开始最小化，等等。

Answer 2

“由于这些类型的问题有多个局部最小值”。这是不正确的，真实的情况是这样的：

• 也许你有一个极小

• 也许你有无限的一组局部miminums

• ，或者你可能有局部极小的数量有限

• 也许最小不能达到

• 也许PROBL EM是无限低于

另外一番景象是真的有正确的方法，其真正解决问题（数字和他们慢），但有调用方法的俚语是不是功能所必要的发现minumum值也称为“解决”。

---

1. 事实上M 1 N〜M表示任何有限n和任意无限集合M.因此，事实上，你的问题有一个维度是什么。从理论的角度来看，从集合M中抽取1000000个参数仍然是一个难题。

2. 如果有趣如何近似求解与在域已知精度的ε-问题 - 然后分裂你域变换到1/espsilon区域，样本值（evalute功能）在中间点，并选择最小

3. 方法，该方法我下面将描述精确的方法和其他方法：粒子估计，序列凸编程，替代方向，粒子群，Neidler-Mead单纯形法，mutlistart梯度/次梯度下降法或任何下降算法，如牛顿法或坐标下降法，它们分别为所有对于非凸问题都没有保证，如果函数是非凸的，它们中的一些甚至不能应用。

---

如果您在与函数值的一些精度真正解决有趣的话，我将介绍以下方法，它被称为分支定界并真正找到最低，你描述的算法我不这么认为，他们解决问题（以强烈的责任感）：

分支限界的基本思想 - 分区域为凸集，提高低/上限，你的情况是间隔。

你应该有一个例行找到上限最优的（最小）值：您可以在例如做只是通过抽样子域取最小值或使用从随机点开始的局部最优化方法。

但你也应该通过一些原则上下限：

• 整型变量的凸松弛，使他们真正的变量

• 使用拉格朗日双功能

• 使用Lipshitc上不变功能等

这是一个复杂的步骤。

如果这两个值接近 - 我们在其他情况下partion完成或细化分区。

获取有关上限和下限子子问题的信息，然后采取分钟。上限和最小值。儿童的下限。如果孩子返回更低的下限，则可以由父母升级。

---

参考文献：

更伟大的解释请看： EE364B，第18讲，教授。斯坦福大学斯蒂芬博伊德。它可以在YouTube和iTunes大学上使用。如果你是新来的这个领域，我建议你看看Stephen P. Boyd的EE263，EE364A，EE364B课程。你会爱上它