 |
精确全局最优化
引言
精确全局最优化问题可以通过使用 Minimize 和 Maximize 得到精确的求解.
| In[1]:= |
| Out[1]= |  |
| In[2]:= |
| Out[2]= |  |
算法
最普遍的方法是基于柱形代数分解(CAD)的算法. 它适用于当目标函数和约束条件是实代数函数时的情况. 该方法总是可以用来计算全局极值 (或极限值，如果没有达到极值的话). 如果有参数的话，极值可以以该参数的分段代数函数的形式计算. 这个方法的一个缺陷是它在变量数目上的高、双指数级的计算复杂度. 在某些不涉及参数的特殊情况下，可以使用更快的方法.
当目标函数和所有约束条件对于有理数系数是线性的情况下，全局极值可以通过单纯型算法精确地计算.
对于单变量问题，我们用等式和不等式求解方法求符合约束条件的解集以及在该集合中，目标函数的导数的不连续点和零点.
另一种求全局极值的方法是利用拉格朗日乘子法或Karush-Kuhn-Tucker（KKT）条件找到所有局部极值，然后选出最小值(最大值). 然而，对于一个完全自动的方法，还有其他复杂情况需要解决. 我们除了需要求解局部极值的必要条件，我们还需要检查目标函数的光滑性和约束条件的光滑性以及非退化性. 另外，我们还需要检查约束条件定义下的集合边界处的极值，以及如果集合是无界的情况下，无穷远点处的极值. 这一般需要在实数范围内精确地求解方程和不等式组，这可能会导致比利用CAD算法求解优化问题更难的CAD计算. 目前 Mathematica 只在具有限定在一个有界盒范围内的等式约束的情况下，使用拉格朗日乘子法. 该方法还要求平稳点的数目和奇点的数目是有限的. 该方法比起基于CAD算法的优点是它可以解决一些超越问题，只要这些问题产生的方程组是 Mathematica 可以解决的.
通过柱形代数分解的优化
例子
| In[3]:= |
| Out[3]= |  |
| In[4]:= |
| Out[4]= |  |
| In[5]:= |
| Out[13]= |  |
自定义的 CAD 优化算法
柱形代数分解 (CAD) 算法在 Mathematica 里通过 CylindricalDecomposition 直接可用. 该算法在 "实数多项式系统" 里有更详细的描述. 下面介绍如何自定义 CAD 算法来求解全局优化问题.
简化为最小化坐标函数
假设我们需要在代数约束条件 
的解集上最小化一个代数函数 
，其中 
是一个由变量组成的向量，而 
是一个由参数组成的向量. 假设 
为一个新的变量. 在约束条件 
上最小化 
相当于在半代数集合
上最小化坐标函数 
.
如果 
刚好是单个变量 
的单调函数，我们就没有必要增加新的变量，因为 
本身就可以被直接最小化.
CAD的投影阶段
对变量进行投影，先对 
进行操作，然后是新变量 
，然后再是参数 
.
如果有代数函数，它们先被新变量代替；再增加新变量所满足的等式和不等式. 取代代数函数的变量先被投影. 这也要求在算法提升阶段进行特殊处理.
由 Hong、McCallum 和 Brown 改进的投影算子在这里可以使用，包括等式约束. 请注意，如果需要引进一个新的变量，我们至少要有一个等式约束，即 
.
CAD的提升阶段
参数 
首先被提升，构建了单元的代数函数等式和不等式描述. 如果有仅仅依赖于参数的约束条件并且你可以断定 
在一个参数单元上都是相同的false，你就不需要进一步提升该单元.
当提升最小化变量 
时，你首先 
的最小值开始，然后继续提升(用深度优先方法提升剩余的变量) 直到你发现满足约束条件的第一个单元. 如果该单元对应于 
的一个投影多项式的一个根，则该根即为 
的极小值，并且对应于单元中任意点的 
的坐标给我们提供了取得最小值的一个点. 如果有参数，你会获得单元中一个点的一个参数描述，它是以界定单元的多项式的根的形式给出的. 如果没有这样的参数，你可以简单地给出 CAD 算法所应用的采样点. 如果满足约束条件的第一个单元对应于一个区间 
，其中 
是 
上投影多项式的根，则 
是
值的下确界，而下确界值没有得到. 最后，如果满足约束条件的第一个单元对应于一个区间 
，那么 
是无下限的.
严格不等式约束
如果没有参数，所有约束条件都是严格的不等式，而你只需要极值，那么可以用该算法的一个非常简单的形式. (如果已知 
，其中 
是约束条件的解集，你可以安全地使不等式约束成为严格的.) 在这种情况下许多低维单元可以被忽略；因此，投影可能只包括主项系数、结式和判别式. 在提升阶段，只需要构建全维数单元；因此，没有必要进行代数数的计算.
| Experimental`Infimum[{f,cons},{x,y,...}] | |
| 寻找在满足约束条件 cons 的点集上 f 的下确界值 | |
| Experimental`Supremum[{f,cons},{x,y,...}] | |
| 寻找在满足约束条件 cons 的点集上 f 的上确界值. | |
| In[14]:= |
| Out[14]= |  |
线性优化
当目标函数和所有约束条件都为线性时，全局极值完全可以用单纯型算法精确地计算.
| In[15]:= |
| Out[22]= |  |
| In[23]:= |
| Out[31]= |  |
单变量最优化
对于单变量问题，等式和不等式求解方法被用来寻找约束解集以及在该集合内的目标函数的导数的不连续点和零点.
| In[32]:= |
| Out[32]= |  |
| In[33]:= |
| Out[33]= |  |
| In[34]:= |
| Out[34]= |  |
通过寻找平稳点和奇点的最优化
| In[35]:= |
| Out[35]= |  |
| In[36]:= |
| Out[36]= |  |
| In[37]:= |
| Out[37]= |  |
| In[38]:= |
| Out[38]= |  |
| In[39]:= |
| Out[39]= |  |
以下是一组具有相同约束条件的三维例子. 根据不同的目标函数，最大值在以下点取得：目标函数在约束条件的解集上的一个平稳点，限制目标函数在约束条件的解集的边界上的平稳点，以及在约束条件的解集的边界上.
| In[40]:= |
| Out[40]= |  |
| In[41]:= |
| Out[41]= |  |
| In[42]:= |
| Out[42]= |  |
| In[43]:= |
| Out[43]= |  |
| In[44]:= |
| Out[44]= |  |
| In[45]:= |
| Out[45]= |  |
| In[47]:= |
| Out[47]= |  |
整数的最优化
整数线性规划
一个整数线性规划问题是这样一个最优化问题，其中目标函数是线性的，约束条件是线性并且有界的，而且变量在整数范围内取值.
为了求解一个整数线性规划问题， Mathematica 首先求解等式约束条件，把问题约化为一个只包含不等式约束的问题. 然后它使用格规约（lattice reduction）技术把该不等式系统转换为更简单的形式. 最后，它采用分支定界方法求解简化了的最优化问题.
| In[48]:= |
| Out[58]= |  |
在实数范围内结合了整数解查找的最优化
假设一个函数 
需要在约束条件 
的整数解集上最小化. 设 
是在 
的实数解集上 
的最小值. 如果存在满足 
的整数点，那么 
是在 
的整数解集上 
的最小值. 否则你要尝试找到 
的整数解. 以此类推. 如果你能求解实数最优化问题和所有搜寻整数解的问题，并且你在固定的尝试次数里，能找到一个整数解的话，这种尝试式的工作方法是适用的. (默认情况下 Mathematica 尝试 10 个候选的极值. 这可以通过 
系统选项来改变.)
| In[59]:= |
| Out[59]= |  |
| In[60]:= |
| Out[60]= |  |
