20、蒙特卡罗优化方法详解

蒙特卡罗优化方法详解

一、蒙特卡罗优化方法概述

在优化问题中，我们常常需要寻找定义在某个域 $\Omega$ 上的目标函数 $f$ 的极值，以及这些极值出现的点 $x \in \Omega$。极值分为最大值和最小值，出现极值的点则被称为最优点（最大化点或最小化点）。

若定义域是欧几里得空间的子集，且假设 $f$ 可微，这时可以使用梯度下降（或上升）方法来寻找局部最小值（或最大值）。但能否找到全局极值取决于搜索的起始点，因为每个局部最小值（最大值）都有其对应的吸引域，要找到全局极值就需要从正确的吸引域开始搜索，这其中存在一定的运气成分。

另一方面，若 $\Omega$ 是一个离散且可能很大的有限集，此时不存在下坡/上坡的方向信息，搜索只能依赖目标值。在搜索过程中，选择下一个尝试的点通常最好随机决定。这种下一个尝试点或起始点随机确定且可能依赖当前位置的搜索过程，在数学上是一个有限马尔可夫链。虽然马尔可夫链理论的全部资源可用于解决该问题，但在不知道具体目标函数性质的情况下，只能做出一些一般性的断言。

二、随机搜索方法的优缺点

随机搜索方法有诸多优点：
-效果显著：常常能取得超乎预期的效果。
-鲁棒性强：在不同的环境和条件下都能稳定工作。
-易于实现：相较于分支限界法等，实现起来更加简单。
-便于并行化：可以简单而有效地进行并行处理。

不过，随机搜索方法也存在一些缺点：
-计算密集