精确全局最优化

引言单变量最优化
算法通过寻找平稳点和奇点的最优化
通过柱形代数分解的优化整数的最优化
线性最优化区域上的优化

引言

全局最优化问题可以通过精确使用 Minimize、Maximize、MinValue、MaxValue、ArgMin 和 ArgMax 求解.

以下计算 的全局最小值并获取此时的 值：
这里计算圆周半径，其中心在原点，范围限制在集合 中：
这里计算圆周半径，其中心在原点，范围限制在集合 中，而该半径为参数 和 的函数：

算法

根据问题的类型，我们可以使用几种不同的算法.

最普遍的方法是基于柱形代数分解(CAD)的算法. 它适用于当目标函数和约束条件是实代数函数时的情况. 该方法总是可以用来计算全局极值 (或极限值，如果没有达到极值的话). 如果有参数的话，极值可以以该参数的分段代数函数的形式计算. 这个方法的一个缺陷是它在变量数目上的高、双指数级的计算复杂度. 在某些不涉及参数的特殊情况下，可以使用更快的方法.

当目标函数和所有约束条件是线性的，全局极值可以通过单纯型算法精确地计算. 这种方法也可用于线性分式目标对象.

对于单变量问题，我们用等式和不等式求解方法求符合约束条件的解集以及在该集合中，目标函数的导数的不连续点和零点.

另一种求全局极值的方法是利用拉格朗日乘子法或Karush-Kuhn-Tucker（KKT）条件找到所有局部极值，然后选出最小值(最大值). 然而，对于一个完全自动的方法，还有其他复杂情况需要解决. 我们除了需要求解局部极值的必要条件，我们还需要检查目标函数的光滑性和约束条件的光滑性以及非退化性. 另外，我们还需要检查约束条件定义下的集合边界处的极值，以及如果集合是无界的情况下，无穷远点处的极值. 这一般需要在实数范围内精确地求解方程和不等式组，这可能会导致比利用 CAD 算法求解优化问题更难的 CAD 计算. 目前 Wolfram 语言只在具有限定在一个有界盒范围内的等式约束的情况下，使用拉格朗日乘子法. 该方法还要求平稳点的数目和奇点的数目是有限的. 该方法比起基于 CAD 算法的优点是它可以解决一些超越问题，只要这些问题产生的方程组是 Wolfram 语言可以解决的.

通过柱形代数分解的优化

例子

这里我们求在三次曲线 上最接近原点的点：
这里我们求在三次曲线 上最接近原点的点，该点为参数 的函数：
这个可视化的演示给我们展示了三次曲线 上最接近原点的点，以及从原点到该点的距离 . 参数 的值可以用滑块进行修改. 这个可视化的演示采用 Minimize 计算来产生最小值：     

自定义的 CAD 优化算法

柱形代数分解 (CAD) 算法在 Wolfram 语言里通过 CylindricalDecomposition 直接可用. 该算法在 "实数多项式系统" 里有更详细的描述. "在实数多项式系统" 中讲述了 CAD 算法选项的设置，尤其是 CADConstruction 选项可能影响优化函数的性能.下面介绍如何自定义 CAD 算法来求解全局优化问题.     

简化为最小化坐标函数

假设我们需要在代数约束条件 的解集上最小化一个代数函数 ，其中 是一个由变量组成的向量，而 是一个由参数组成的向量. 假设 为一个新的变量. 在约束条件 上最小化 相当于在半代数集合 上最小化坐标函数 .

如果 刚好是单个变量 的单调函数，我们就没有必要增加新的变量，因为 本身就可以被直接最小化.

CAD 的投影阶段

对变量进行投影，先对 进行操作，然后是新变量 ，然后再是参数 .

如果有代数函数，它们先被新变量代替；再增加新变量所满足的等式和不等式. 取代代数函数的变量先被投影. 这也要求在算法提升阶段进行特殊处理.

由 Hong、McCallum 和 Brown 改进的投影算子在这里可以使用，包括等式约束. 请注意，如果需要引进一个新的变量，我们至少要有一个等式约束，即 .     

CAD 的提升阶段

参数 首先被提升，构建了单元的代数函数等式和不等式描述. 如果有仅仅依赖于参数的约束条件并且你可以断定 在一个参数单元上都是相同的false，你就不需要进一步提升该单元.

当提升最小化变量 时，你首先 的最小值开始，然后继续提升(用深度优先方法提升剩余的变量) 直到你发现满足约束条件的第一个单元. 如果该单元对应于 的一个投影多项式的一个根，则该根即为 的极小值，并且对应于单元中任意点的 的坐标给我们提供了取得最小值的一个点. 如果有参数，你会获得单元中一个点的一个参数描述，它是以界定单元的多项式的根的形式给出的. 如果没有这样的参数，你可以简单地给出 CAD 算法所应用的采样点. 如果满足约束条件的第一个单元对应于一个区间 ，其中 是 上投影多项式的根，则 是 值的下确界，而下确界值没有得到. 最后，如果满足约束条件的第一个单元对应于一个区间 ，那么 是无下限的.

线性最优化

当目标函数和所有约束条件都为线性时，全局极值完全可以用单纯型算法精确地计算.

这里求解一个有10个变量的随机线性最小化问题：
目标函数是线性函数的一个分式并且约束条件是线性（线性分式程序）的最优化问题可以简化为线性最优化问题. 这里我们求解一个有10个变量的随机线性分式最小化问题：

单变量最优化

对于单变量问题，等式和不等式求解方法被用来寻找约束解集以及在该集合内的目标函数的导数的不连续点和零点.     

这里求解一个具有超越目标函数的单变量最优化问题：
这里图示表示一个求得的最小值：
这里 Wolfram 语言注意到目标函数和约束函数是周期性的：
可以超越函数的 Root 的形式给出解：
当输入涉及特殊函数时，数值积分可用于证明解的完整性：

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

当约束包含等式和不等式明确指定边界框时会使用拉格朗日乘子.下面是一个在约束条件的奇点取得最小值的例子：
对同样的目标函数，我们发现最大值是在约束条件定义的集合的边界上：
在这个例子里没有平稳点：

以下是一组具有相同约束条件的三维例子. 根据不同的目标函数，最大值在以下点取得：目标函数在约束条件的解集上的一个平稳点，限制目标函数在约束条件的解集的边界上的平稳点，以及在约束条件的解集的边界上.

这里是在约束条件的解集上，目标函数的平稳点处取得最大值：
这里是在限制在约束解集的边界上的平稳点，目标函数取得最大值：
这里在约束条件解集的边界上取得最大值：
拉格朗日乘子方法对涉及超越函数的一些最优化问题是适用的：
当约束包含带有有界解集的单个等式或不等式时，也会使用拉格朗日乘子：

整数的最优化

整数线性最优化

一个整数线性最优化问题是这样一个最优化问题，其中目标函数是线性的，约束条件是线性并且有界的，而且变量在整数范围内取值.

为了求解一个整数线性最优化问题，Wolfram 语言首先求解等式约束条件，把问题约化为一个只包含不等式约束的问题. 然后它使用格规约（lattice reduction）技术把该不等式系统转换为更简单的形式. 最后，它采用分支定界方法求解简化了的最优化问题.

这里求解一个随机生成的有7个变量的整数线性最优化问题：

实数最优化与整数求解相结合

假设一个函数 需要在约束条件 的整数解集上最小化. 设 是在 的实数解集上 的最小值. 如果存在满足 的整数点，那么 是在 的整数解集上 的最小值. 否则你要尝试找到 的整数解. 以此类推. 如果你能求解实数最优化问题和所有搜寻整数解的问题，并且你在固定的尝试次数里，能找到一个整数解的话，这种尝试式的工作方法是适用的. (默认情况下 Wolfram 语言尝试 10 个候选的极值. 这可以通过 IntegerOptimumCandidates 系统选项来改变.)

这里在三次式 下的点中寻找有整数坐标的一个点来最大化 ：

区域上的优化

区域可用于指定约束. 用于求解区域上优化问题的方法依赖于哪种区域描述类型更易于获得.

以下使用区域的隐式描述：
带入目标函数的区域参数：