非线性规划中的确定性全局优化算法基础题 我们先来理解什么是 确定性全局优化算法 。在非线性规划中，很多目标函数和约束都是非凸的，这意味着可能存在多个局部最优解。局部优化算法（如梯度法、牛顿法、SQP等）通常只能找到初始点附近的局部最优解，而不能保证找到整个可行域内最好的那个解（即全局最优解）。确定性全局优化算法的目标，就是在不依赖随机性的情况下，通过系统的、数学上严谨的搜索策略，保证找到问题的全局最优解（或在可容忍误差内逼近它）。 题目描述 考虑一个经典的非线性规划测试问题： Branin函数 （通常在无约束全局优化中测试，我们为其添加简单的边界约束以构成一个有界域约束问题）。 优化问题： \[ \min_ {x_ 1, x_ 2} f(x_ 1, x_ 2) = a(x_ 2 - b x_ 1^2 + c x_ 1 - r)^2 + s(1-t)\cos(x_ 1) + s \] 其中常数取经典值： \( a=1, b=5.1/(4\pi^2), c=5/\pi, r=6, s=10, t=1/(8\pi) \)。 约束条件： \[ -5 \leq x_ 1 \leq 10, \quad 0 \leq x_ 2 \leq 15 \] 这是一个有多个局部极小点的非线性函数，我们的任务是找到其在整个矩形定义域内的全局最小值点。 解题思路与循序渐进讲解 确定性全局优化算法的核心思想是 分支定界 。其基本原理是：将整个可行域（初始区域）不断分割成更小的子区域（ 分支 ），并在每个子区域上计算目标函数值的下界（ 定界 ），通过比较和更新全局上界来删除不可能包含全局最优解的子区域，从而逐步缩小搜索范围，直到满足精度要求。 对于我们的Branin函数问题，我们将使用一种经典的确定性全局优化方法： 基于区间算术和分支定界的算法 。 步骤1：理解分支定界框架 分支定界包含几个关键组件： 初始区域 ：就是我们的约束盒 \( B^{(0)} = [ -5, 10] \times [ 0, 15 ] \)。 区域列表 \( L \)：存储待处理的子区域（及其下界）。 全局上界 \( \overline{f} \)：当前找到的最小的可行点函数值。初始化时，可以通过在区域中心或顶点采样得到一个。 下界函数 \( LB(B) \)：对于任意一个子区域 \( B \)，我们需要一个方法计算出目标函数 \( f(x) \) 在 \( B \) 上的一个 下界 。这个下界必须是通过确定性计算（不依赖抽样）且可靠的，即 \( f(x) \geq LB(B) \) 对所有 \( x \in B \) 成立。如果对于某个区域 \( B \)，其下界 \( LB(B) > \overline{f} \)，那么这个区域内不可能存在比当前已知更好的点，可以安全删除（剪枝）。 分支规则 ：当一个区域无法被剪枝时，我们选择它并将其分割成两个或多个更小的子区域，放入区域列表 \( L \)。 步骤2：关键工具——区间算术计算下界 计算下界 \( LB(B) \) 的经典确定性方法是使用 区间算术 。 区间算术 ：不是对单个数值进行运算，而是对区间进行运算。它提供了一种计算函数在区间上取值范围的方法，并保证结果区间一定包含该函数在该区间上所有可能的取值。 对于我们的问题 ：区域 \( B \) 是一个区间向量，例如 \( X_ 1 = [ l_ 1, u_ 1], X_ 2 = [ l_ 2, u_ 2 ] \)。 如何计算 \( f(X_ 1, X_ 2) \) 的区间值 ： 我们将 \( f(x_ 1, x_ 2) \) 的表达式用区间运算规则重写。基本规则如： \([ a, b] + [ c, d] = [ a+c, b+d ]\) \([ a, b] - [ c, d] = [ a-d, b-c ]\) \([ a, b] \times [ c, d] = [ \min(ac, ad, bc, bd), \max(ac, ad, bc, bd) ]\) 对于单调函数（如 \( \cos \)），可以直接应用到区间端点：\( \cos([ l, u]) = [ \cos(u), \cos(l)] \) 如果区间 \([ l, u ]\) 包含在余弦函数的单调递减区间内（需要根据具体区间判断单调性，或计算所有端点值取最小最大）。 计算示例 ： 假设我们取一个子区域 \( B: X_ 1 = [ -5, -4], X_ 2 = [ 0, 1 ] \)。 计算 \( b X_ 1^2 \)。先算 \( X_ 1^2 \)：区间 \([ -5, -4]\) 的平方是 \([ 16, 25]\)（因为负数的平方是正数）。然后乘以常数 \( b \approx 0.129 \) 得到约 \([ 2.064, 3.225 ]\)。 计算 \( c X_ 1 \)， \( c \approx 1.591 \)， \( c \times [ -5, -4] \approx [ -7.955, -6.364 ]\)。 计算 \( x_ 2 - b x_ 1^2 + c x_ 1 - r \)： \([ 0, 1] - [ 2.064, 3.225] + [ -7.955, -6.364 ] - 6 \)。 先算 \( [ 0,1] - [ 2.064,3.225] = [ 0-3.225, 1-2.064] = [ -3.225, -1.064 ] \)。 再加 \([ -7.955, -6.364]\)：得到 \([ -11.18, -7.428 ]\)。 再减 6：得到 \([ -17.18, -13.428 ]\)。 平方项 \( a(…)^2 \)：先对区间 \([ -17.18, -13.428]\) 平方。由于整个区间为负，其平方为 \([ (13.428)^2, (17.18)^2 ] \approx [ 180.3, 295.0 ]\)。乘以 \( a=1 \) 不变。 计算 \( s(1-t)\cos(x_ 1) \)：\( s(1-t) \approx 10 \times 0.920 = 9.20 \)。计算 \( \cos(X_ 1) = \cos([ -5, -4]) \)。注意 \( -5 \) 弧度约 -286.5°，\( -4 \) 弧度约 -229.2°。在这个弧度区间，余弦函数不是单调的。我们需要计算端点值：\( \cos(-5) \approx 0.284, \cos(-4) \approx -0.654 \)。所以 \( \cos(X_ 1) \) 的区间约为 \([ -0.654, 0.284]\)。乘以 9.20 得到约 \([ -6.017, 2.613 ]\)。 最后加上常数 \( s=10 \)：第一部分区间 \([ 180.3, 295.0]\)，第二部分区间 \([ -6.017, 2.613 ]\)，常数10。 先将前两部分相加：\([ 180.3, 295.0] + [ -6.017, 2.613] = [ 174.283, 297.613 ]\)。 再加10：最终 \( F(B) = [ 184.283, 307.613 ]\)。 这个区间 \( F(B) \) 的意义是：对于该区域 \( B \) 内的 任何一点 \((x_ 1, x_ 2)\)，其函数值 \( f(x_ 1, x_ 2) \) 必定在 \([ 184.283, 307.613 ]\) 之内。 因此，我们可以取该区间的 左端点 作为区域 \( B \) 的 下界 ：\( LB(B) = 184.283\)。 步骤3：算法流程 初始化 ： 设置初始区域列表 \( L = \{ B^{(0)} \} \)。 在初始区域中心或顶点采样，计算一个函数值作为初始全局上界 \( \overline{f} \)（例如，在 (2.5, 7.5) 采样）。假设我们采样得到 \( \overline{f} = 60 \)（实际上Branin的全局最小值约0.398）。 设置容忍误差 \( \epsilon > 0 \)，例如 \( \epsilon = 0.01 \)。 设置一个记录当前最佳点 \( x^* \)。 迭代主循环 （当 \( L \) 非空时）： a. 选择区域 ：从 \( L \) 中选择一个下界最小的区域 \( B_ {current} \)（这是最有可能包含最优解的区域）。 b. 分支 ：将 \( B_ {current} \) 沿其最长边一分为二。例如，如果宽度 \( X_ 1 \) 大于 \( X_ 2 \) 的宽度，则对 \( X_ 1 \) 区间取中点分割。 c. 处理子区域 ：对于每个新生成的子区域 \( B_ {sub} \)： i. 使用区间算术计算 \( f \) 在 \( B_ {sub} \) 上的区间值 \( F(B_ {sub}) \)，得到下界 \( LB(B_ {sub}) \)。 ii. 可行性剪枝 ：由于我们只有边界约束，且区域本身就在边界内，所以总是可行。若有复杂约束，也需用区间算术判断是否存在可行点。 iii. 下界剪枝 ：如果 \( LB(B_ {sub}) > \overline{f} \)，则丢弃 \( B_ {sub} \)。 iv. 如果未被剪枝： * 可以将 \( B_ {sub} \) 加入到区域列表 \( L \) 中。 * 可选：在 \( B_ {sub} \) 的中心点计算精确函数值 \( f_ {mid} \)。如果 \( f_ {mid} < \overline{f} \)，则更新 \( \overline{f} = f_ {mid} \)，并更新 \( x^* \) 为中心点。同时，可以用这个新的、更小的 \( \overline{f} \) 去检查列表 \( L \) 中的其他区域，进行 全局剪枝 （删除那些下界大于新 \( \overline{f} \) 的区域）。 d. 收敛判断 ：计算整个未剪枝区域集合中下界的最小值 \( LB_ {min} = \min_ {B \in L} LB(B) \)。如果 \( \overline{f} - LB_ {min} \leq \epsilon \)，则停止迭代。此时，全局最优值一定在区间 \( [ LB_ {min}, \overline{f}] \) 内，且 \( x^* \) 是 \( \epsilon \)-全局最优解。 步骤4：应用到Branin函数 对于Branin函数，已知其有三个全局最小值点（函数值约为0.397887），分别位于 \( (-\pi, 12.275), (\pi, 2.275), (9.42478, 2.475) \) 附近。我们的算法会： 从整个区域开始，区间算术给出的下界可能非常宽松（比如是一个很大的负数，因为余弦项的影响）。但随着区域不断被分割变小，区间算术计算出的函数值范围会越来越紧。 算法会系统地搜索整个矩形区域。那些包含局部极小点但函数值较大的区域（例如靠近 (3, 3) 的局部极小点，值约20），随着算法找到全局最小值点（更新 \( \overline{f} \approx 0.398 \)），这些区域的下界会逐渐被计算出来。一旦某个区域的下界 \( LB > 0.398 \)，它就会被剪枝。 最终，算法会将搜索集中在包含三个全局最优点的小区域附近。当这些小区域的最大宽度（尺寸）和函数值范围都小于预设精度 \( \epsilon \) 时，算法终止。 步骤5：总结与特点 确定性 ：整个过程中不涉及任何随机抽样，每一步操作（区间运算、分支、比较）都是确定的。 全局收敛性 ：在计算精度允许（如无限精度算术、无限时间）下，算法保证收敛到全局最优解。 计算成本 ：主要成本在于区间运算和需要处理的子区域数量。对于高维问题，可能会产生“维数灾难”，因为分支数量呈指数增长。因此，这类算法通常适用于维度较低（例如 n < 20）的问题。 核心依赖 ：下界估计的紧致性至关重要。紧致的下界可以加速剪枝。除了基本的区间算术，还有更高级的技术如 利用凸松弛、多项式界、泰勒模型 等来获得更紧的下界。 通过这个基于区间算术和分支定界的确定性全局优化算法，我们能够系统、可靠地找到Branin函数在给定矩形区域内的全局最小值点，避免了陷入局部最优的风险。这种思想是许多更复杂确定性全局优化算法（如αBB方法、分支定界结合凸松弛等）的基础。