Wolfram Mathematica Documentation Center
DOCUMENTATION CENTER SEARCH
New to Mathematica? Find your learning path »
虚拟全书 > 数学和算法 > 约束最优化 > 精确全局最优化 >
MATHEMATICA 教程|相关教程 »

精确全局最优化

引言

精确全局最优化问题可以通过使用 Minimize 和 Maximize 得到精确的求解.
这里计算圆周半径，其中心在原点，范围限制在集合 中.
In[1]:=
Click for copyable input
Out[1]=
这里计算圆周半径，其中心在原点，范围限制在集合 中，而该半径为参数 和 的函数.
In[2]:=
Click for copyable input
Out[2]=

算法

根据问题的类型，我们可以使用几种不同的算法.
最普遍的方法是基于柱形代数分解(CAD)的算法. 它适用于当目标函数和约束条件是实代数函数时的情况. 该方法总是可以用来计算全局极值 (或极限值，如果没有达到极值的话). 如果有参数的话，极值可以以该参数的分段代数函数的形式计算. 这个方法的一个缺陷是它在变量数目上的高、双指数级的计算复杂度. 在某些不涉及参数的特殊情况下，可以使用更快的方法.
当目标函数和所有约束条件对于有理数系数是线性的情况下，全局极值可以通过单纯型算法精确地计算.
对于单变量问题，我们用等式和不等式求解方法求符合约束条件的解集以及在该集合中，目标函数的导数的不连续点和零点.
另一种求全局极值的方法是利用拉格朗日乘子法或Karush-Kuhn-Tucker（KKT）条件找到所有局部极值，然后选出最小值(最大值). 然而，对于一个完全自动的方法，还有其他复杂情况需要解决. 我们除了需要求解局部极值的必要条件，我们还需要检查目标函数的光滑性和约束条件的光滑性以及非退化性. 另外，我们还需要检查约束条件定义下的集合边界处的极值，以及如果集合是无界的情况下，无穷远点处的极值. 这一般需要在实数范围内精确地求解方程和不等式组，这可能会导致比利用CAD算法求解优化问题更难的CAD计算. 目前 Mathematica 只在具有限定在一个有界盒范围内的等式约束的情况下，使用拉格朗日乘子法. 该方法还要求平稳点的数目和奇点的数目是有限的. 该方法比起基于CAD算法的优点是它可以解决一些超越问题，只要这些问题产生的方程组是 Mathematica 可以解决的.

通过柱形代数分解的优化

例子

这里我们求在三次曲线 上最接近原点的点.
In[3]:=
Click for copyable input
Out[3]=
这里我们求在三次曲线 上最接近原点的点，该点为参数 的函数.
In[4]:=
Click for copyable input
Out[4]=
这个可视化的演示给我们展示了三次曲线 上最接近原点的点，以及从原点到该点的距离 . 参数 的值可以用滑块进行修改. 这个可视化的演示采用 Minimize 计算来产生最小值.     
In[5]:=
Click for copyable input
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 的上确界值.

寻找极值.

这里寻找以原点为中心，包含以曲面 为界的集合的最小球体. 如果以相同的输入调用完全的 Maximize， 则运算时间超过在10分钟.     
In[14]:=
Click for copyable input
Out[14]=

线性优化

当目标函数和所有约束条件都为线性时，全局极值完全可以用单纯型算法精确地计算.
这里求解一个有10个变量的随机线性最小化问题.
In[15]:=
Click for copyable input
Out[22]=
目标函数是线性函数的一个分式并且约束条件是线性（线性分式程序）的最优化问题可以简化为线性最优化问题. 这里我们求解一个有10个变量的随机线性分式最小化问题.
In[23]:=
Click for copyable input
Out[31]=

单变量最优化

对于单变量问题，等式和不等式求解方法被用来寻找约束解集以及在该集合内的目标函数的导数的不连续点和零点.     
这里求解一个具有超越目标函数的单变量最优化问题.
In[32]:=
Click for copyable input
Out[32]=
这里图示表示一个求得的最小值.
In[33]:=
Click for copyable input
Out[33]=
这里 Mathematica 注意到目标函数和约束函数是周期性的.
In[34]:=
Click for copyable input
Out[34]=

通过寻找平稳点和奇点的最优化

下面是一个在约束条件的奇点取得最小值的例子.     
In[35]:=
Click for copyable input
Out[35]=
In[36]:=
Click for copyable input
Out[36]=
对同样的目标函数，我们发现最大值是在约束条件定义的集合的边界上.
In[37]:=
Click for copyable input
Out[37]=
In[38]:=
Click for copyable input
Out[38]=
在这个例子里没有平稳点.
In[39]:=
Click for copyable input
Out[39]=
以下是一组具有相同约束条件的三维例子. 根据不同的目标函数，最大值在以下点取得：目标函数在约束条件的解集上的一个平稳点，限制目标函数在约束条件的解集的边界上的平稳点，以及在约束条件的解集的边界上.
这里是在约束条件的解集上，目标函数的平稳点处取得最大值.
In[40]:=
Click for copyable input
Out[40]=
In[41]:=
Click for copyable input
Out[41]=
这里是在限制在约束解集的边界上的平稳点，目标函数取得最大值.     
In[42]:=
Click for copyable input
Out[42]=
In[43]:=
Click for copyable input
Out[43]=
这里在约束条件解集的边界上取得最大值.
In[44]:=
Click for copyable input
Out[44]=
In[45]:=
Click for copyable input
Out[45]=
拉格朗日乘子方法对涉及超越函数的一些最优化问题是适用的.
In[46]:=
Click for copyable input
Out[46]=
In[47]:=
Click for copyable input
Out[47]=

整数的最优化

整数线性规划

一个整数线性规划问题是这样一个最优化问题，其中目标函数是线性的，约束条件是线性并且有界的，而且变量在整数范围内取值.
为了求解一个整数线性规划问题， Mathematica 首先求解等式约束条件，把问题约化为一个只包含不等式约束的问题. 然后它使用格规约（lattice reduction）技术把该不等式系统转换为更简单的形式. 最后，它采用分支定界方法求解简化了的最优化问题.
这里求解一个随机生成的有7个变量的整数线性规划问题.     
In[48]:=
Click for copyable input
Out[58]=

在实数范围内结合了整数解查找的最优化

假设一个函数 需要在约束条件 的整数解集上最小化. 设 是在 的实数解集上 的最小值. 如果存在满足 的整数点，那么 是在 的整数解集上 的最小值. 否则你要尝试找到 的整数解. 以此类推. 如果你能求解实数最优化问题和所有搜寻整数解的问题，并且你在固定的尝试次数里，能找到一个整数解的话，这种尝试式的工作方法是适用的. (默认情况下 Mathematica 尝试 10 个候选的极值. 这可以通过 系统选项来改变.)
这里在三次式 下的点中寻找有整数坐标的一个点来最大化 .
In[59]:=
Click for copyable input
Out[59]=
In[60]:=
Click for copyable input
Out[60]=
Ask a question about this page  |  Suggest an improvement  |  Leave a message for the team
格式:   HTML  |  CDF