 |
数值非线性全局最优化
引言
约束非线性最优化的数值算法大致可以分为 基于梯度的方法 和 直接搜索方法. 基于梯度的方法使用一阶导数 (梯度) 或二阶导数（黑塞（Hessians）矩阵）. 例如，序列二次规划方法(SQP)、增广拉格朗日方法和（非线性）内点法. 直接搜索方法不使用导数信息. 例如，Nelder-Mead、遗传算法和差分进化，以及模拟退火. 直接搜索方法往往收敛速度较慢，但可以对函数和约束条件中噪声存在的限制更为宽松.
通常情况下，算法只建立问题的局部模型. 此外，许多这种算法总是寻求目标函数，或者由目标函数和约束条件合成的一个优值函数的某种减小，来确保迭代过程的收敛. 如果收敛的话，这种算法只找到局部最优解，因此被称为 局部最优化算法. 在 Mathematica 里，局部最优化问题可以用 FindMinimum 求解.
然而，全局优化算法 通常通过既允许减小也允许增大目标函数/优值函数来试图求全局最优解. 通常这种算法的计算代价更高. 全局最优化问题可以用 Minimize 精确求解或者用 NMinimize 数值化地求解.
利用 Minimize，能够产生一个精确的解
| In[1]:= |
| Out[1]= |  |
| In[2]:= |
| Out[2]= |  |
| In[3]:= |
| Out[3]= |  |
NMinimize 函数
NMinimize 和 NMaximize 执行好几种算法用以求约束全局最优解. 这些方法具有足够的灵活性，以处理不可微或连续，并且不容易被局部最优解捕捉的函数.
寻找一个全局最优解的问题可具有任意难度，即使在没有约束的情况下，所以我们使用的方法可能会失败. 在通常情况下，多次使用不同的初始条件最优化，并采用其中最好的结果来，对于最优化该函数是有益的.
| In[46]:= |
| Out[46]= |  |
| In[47]:= |
| Out[47]= |  |
NMinimize 和 NMaximize 的约束条件可以是一个列表，或者是等式、不等式和定义域的划定的逻辑组合. 等式和不等式可能是非线性的. 由于近似数字处理上的局限，任何强不等式将被转换为弱不等式. 划定一个变量的定义域时用 Element ，例如，Element[x, Integers] 或者 x
Integers. 变量必须或者是整数或者是实数，并且除非特别说明，否则将被假定为实数. 当点离开可行域时，约束条件通过增加罚函数进行强化.
| In[3]:= |
| Out[3]= |  |
| In[4]:= |
| Out[4]= |  |
为了让 NMinimize 工作，需要从一个长方形的初始区域内开始. 这和其他数值方法中需要提供一个初始点或几个初始点类似. 初始区域是通过给每个变量一个有限的上界和下界来确定的. 这通过在约束条件中包括 
，或者在变量中包括 
完成. 如果两者都被提供，则变量中的边界用于初始区域，而约束条件就作为约束条件来使用. 如果对于一个变量 x 没有指定初始区域，我们将采用默认初始区域 
. 不同变量可以有用不同方式定义的初始区域.
| In[5]:= |
| Out[5]= |  |
| In[6]:= |
| Out[6]= |  |
| In[7]:= |
| Out[7]= |  |
| In[48]:= |
| Out[48]= |  |
| In[50]:= |
| Out[50]= |  |
NMinimize 和 NMaximize 有好几个优化方法可采用，包括: Automatic、
、
、
和 
. 优化方法由 Method 选项控制，选项可以取作为一个字符串的方法，也可以取一个列表，该列表的第一个元素是作为一个字符串的方法而其他元素都是基于具体方法的选项. 所有基于具体方法的选项，左边也必须作为字符串给出.
| In[51]:= |
| Out[53]= |  |
| In[54]:= |
| Out[54]= |  |
| In[55]:= |
| Out[55]= |  |
使用默认的方法，NMinimize 根据问题的类型选择使用的方法. 如果目标函数和约束条件是线性的，则采用LinearProgramming. 如果有整数变量，或者如果目标函数的头部不是一个数值函数的话，则采用差分进化算法. 对于所有其他类型的问题，则采用Nelder-Mead，但是如果Nelder-Mead 运行不佳的话，就切换到差分进化算法.
因为 NMinimize 所采用的方法不可能改善每次迭代的结果，所以我们只在数次迭代后检查收敛度.
约束全局最优化的数值算法
Nelder-Mead
Nelder-Mead方法是一个直接搜索方法. 对于一个具有 
个变量的函数，该算法保持一个 
个点的点集，这些点形成 
维空间的多面体的顶点. 这种方法通常被称为 "单纯" 方法，它不应与众所周知的线性规划的单纯型法混为一谈.
在每次迭代中，
个点 
形成一个多面体. 点的排列顺序使得 
然后产生一个新的点以取代最差点 
设 
为包含最好的 
个点的多面体的中心，
. 一个试验点 
由穿过中心的最差点反射产生， 
，其中 
是一个参数.
如果新的点 
既不是一个新的最差点也不是一个新的最佳点，
, 则由 
取代 
.
如果新的点 
优于最佳点，
，则反射非常成功并可以进一步执行到 
，其中 
是扩大多面体的一个参数. 如果扩大成功，
，则由 
取代 
；否则扩大失败，并由 
取代 
.
如果新的点 
劣于第二差点，
，则认为多面体过于庞大，需要收缩. 由
定义一个新的尝试点，其中 
是一个参数. 如果 
，收缩是成功的，且由 
取代 
. 否则就进行进一步的收缩.
如果在新的和旧的多面体里的最佳函数值的差，以及在新的最佳点和旧的最佳点的距离小于AccuracyGoal 和 PrecisionGoal 所提供的容差， 这个过程则被认为是收敛的.
严格地说，Nelder-Mead不是一个真正的全局最优化算法，然而在实践中对于没有许多局部极小值的问题，往往有不错的工作效率.
选项名 | 默认值 | |
| "ContractRatio" | 0.5 | 用于收缩的比例 |
| "ExpandRatio" | 2.0 | 用于扩大的比例 |
| "InitialPoints" | Automatic | 初始点集合 |
| "PenaltyFunction" | Automatic | 应用于约束条件以惩罚无效点的函数 |
| "PostProcess" | Automatic | 是否采用局部搜索方法进行后处理 |
| "RandomSeed" | 0 | 随机数生成器的初始值 |
| "ReflectRatio" | 1.0 | 用于反射的比例 |
| "ShrinkRatio" | 0.5 | 用于收缩的比例 |
| "Tolerance" | 0.001 | 接受对约束违反程度的宽限 |
| In[82]:= |
| Out[82]= |  |
| In[83]:= |
| Out[83]= |  |
差分进化
该算法保持了一个 
个点的集合，
，其中通常 
，这里 
是变量的数目.
在算法的每次迭代过程中，都产生一个新的 
个点的集合. 第 
个新的点通过从旧的集合选择三个随机点 
、
和 
，并且形成 
来产生，其中 
是一个实数尺度因子. 然后从 
和 
构建一个新的点 
，其中以概率 
从 
选择第 
个坐标， 其它则从 
选择坐标. 如果 
，那么就由 
取代集合中的 
. 概率 
通过
选项控制.
如果在新的和旧的集合里最佳函数值的差，以及在新的最佳点和旧的最佳点的距离小于AccuracyGoal 和 PrecisionGoal 所提供的容差， 这个过程则被认为是收敛的.
差分进化方法在计算上是昂贵的，但是相对来说也较为稳健，而且对于有较多局部极小值的问题来说工作性能较好.
选项名 | 默认值 | |
| "CrossProbability" | 0.5 | 从  获取一个基因的概率 |
| "InitialPoints" | Automatic | 初始点的集合 |
| "PenaltyFunction" | Automatic | 用于约束条件以惩罚无效点的函数 |
| "PostProcess" | Automatic | 是否用局部搜索方法进行后处理 |
| "RandomSeed" | 0 | 随机数生成器的初始值 |
| "ScalingFactor" | 0.6 | 应用于创建一个相伴向量的差异向量的尺度 |
| "SearchPoints" | Automatic | 用于进化的群体大小 |
| "Tolerance" | 0.001 | 接受对约束违反程度的宽限 |
| In[125]:= |
| Out[125]= |  |
| In[126]:= |
| In[127]:= |
| In[130]:= |
| Out[130]= |  |
| In[131]:= |
| Out[131]= |  |
模拟退火算法
模拟退火算法是一个简单的随机函数最小化算法. 这是从退火的物理过程得到启发的. 退火时，金属物体被加热到很高的温度并且慢慢冷却. 这个过程使金属的原子结构最终形成于一个较低的能量状态，从而成为更强硬的金属. 利用优化术语，退火使结构脱离局部最小值，探索并达到一个更好的，可望是全局的的最小值.
在每次迭代里，一个新的点，
，在当前点
的附近产生. 临近区域的半径随每次迭代下降. 到目前为止，找到的最佳点，
，也被追踪.
如果 
，则 
取代 
和 
. 否则，
以概率 
取代 
. 这里 
是由 
定义的函数，
是当前的迭代，
是目标函数值的改变量，而 
是上一次迭代中的目标函数值. 
的默认函数是 
.
正如 
方法，
使用多个初始点，并且从每个初始点出发找到一个最优值.
对于每个初始点，如此反复执行直至达到最大迭代次数，该方法要么收敛到一个点，要么在由 
所提供的迭代次数里连续停留在同一点.
选项名 | 默认值 | |
| "BoltzmannExponent" | Automatic | 概率函数的指数 |
| "InitialPoints" | Automatic | 初始点集 |
| "LevelIterations" | 50 | 停留在某一给定点的最大迭代次数 |
| "PenaltyFunction" | Automatic | 用于约束条件以惩罚无效点的函数 |
| "PerturbationScale" | 1.0 | 随机跳转的尺度 |
| "PostProcess" | Automatic | 是否利用局部搜索方法进行后处理 |
| "RandomSeed" | 0 | 随机数字生成器的初始值 |
| "SearchPoints" | Automatic | 初始点的数目 |
| "Tolerance" | 0.001 | 接受对约束违反程度的宽限 |
| In[62]:= |
| Out[62]= |  |
| In[63]:= |
| Out[65]= |  |
| In[68]:= |
| Out[68]= |  |
| In[69]:= |
| Out[69]= |  |
| In[70]:= |
| Out[70]= |  |
随机搜索
随机搜索算法的工作方式是先产生一族随机初始点，然后从每个初始点用一个局部优化方法收敛到一个局部极小值. 最佳局部极小值被选为问题的解.
可能的局部搜索方法有 Automatic 和 
. 默认的方法是 Automatic，它使用 FindMinimum 把非约束的方法用于一个加了惩罚项的系统，而惩罚项是因约束而添加的. 当 Method 被设置为 
时，则采用非线性内点方法.
运行很快，但其规模和搜索空间维度的匹配不是很好. 它也受到许多和 FindMinimum 相同的局限. 它不适合离散问题和那些导数或者secants不能提供多少有用信息的问题.
选项名 | 默认值 | |
| "InitialPoints" | Automatic | 初始点的集合 |
| "Method" | Automatic | 用于最小化的方法 |
| "PenaltyFunction" | Automatic | 应用于约束条件以惩罚无效点的函数 |
| "PostProcess" | Automatic | 是否采用局部搜索方法进行后处理 |
| "RandomSeed" | 0 | 随机数字生成器的初始值 |
| "SearchPoints" | Automatic | 用于启动局部搜索的点的数目 |
| "Tolerance" | 0.001 | 接受对约束违反程度的宽限 |
| In[71]:= |
| Out[71]= |  |
| In[72]:= |
| Out[72]= |  |
| In[75]:= |
| Out[75]= |  |
| In[76]:= |
| Out[80]= |  |
| In[81]:= |
| Out[81]= |  |
