全球优化实践：现状与展望

### 全球优化实践：现状与展望 #### 1. 引言 非线性在自然和人造物体、结构及过程的发展中起着至关重要的作用。因此，非线性描述模型在定量科学研究中具有关键意义。决策支持（控制、管理或优化）模型若包含非线性系统描述，往往存在多个局部和全局最优解。全球优化（GO）的目标就是在这种情况下找到非线性优化模型的“绝对最优”解。 我们考虑一般的连续全球优化（CGO）模型，其定义包含以下要素： - **决策向量 \(x\)**：实欧几里得 \(n\) 空间 \(R^n\) 中的元素。 - **显式有限边界 \(l\) 和 \(u\)**：定义了 \(R^n\) 中的一个“盒子”。 - **连续目标函数 \(f(x)\)**：\(f: R^n \to R\)。 - **连续约束函数向量 \(g(x)\)**：\(g: R^n \to R^m\)。 CGO 模型表述为： \[ \begin{align*} \min f(x) & \quad (1)\\ x \in D := \{x : l \leq x \leq u, g(x) \leq 0\} & \quad (2) \end{align*} \] 在式 (2) 中，所有向量不等式按分量解释。额外约束集 \(g\) 可以为空，从而得到盒子约束的 GO 模型。更一般的优化模型，包括等式、大于等于约束关系或约束函数值的显式下界，都可以简化为式 (1) 和式 (2) 的形式。 CGO 模型非常通用，它包含了线性规划和凸非线性规划模型，还形式上包含了纯整数和混合整数规划问题。例如，有界整数变量可以用二进制变量表示，每个二进制变量 \(y \in \{0, 1\}\) 可以等价表示为 \(y \in [0, 1]\) 和非凸约束 \(y(1 - y) \leq 0\)。 如果集合 \(D\) 非空，根据魏尔斯特拉斯定理，CGO 模型的最优解集 \(X^*\) 非空。为了数值可处理性，通常还会有以下额外要求： - \(D\) 是 \(R^n\) 中的全维子集。 - 式 (1) 和式 (2) 的全局最优解集合至多可数。 - \(f\) 和 \(g\)（按分量）在 \([l, u]\) 上是 Lipschitz 连续函数。 这些假设使得算法搜索更容易，支持理论收敛结果，并为基于有限可行搜索点估计最优值提供了充分条件。 CGO 模型涵盖了广泛的优化问题，但也包含许多难以数值求解的实例。例如，一维盒子约束的 GO 模型 \(\min \cos(x)\sin(x^2 - x), 0 \leq x \leq 10\) 和二维扩展模型 \(\min \cos(x)\sin(y^2 - x) + \cos(y)\sin(x^2 - y), 0 \leq x \leq 10, 0 \leq y \leq 10\) 就展示了模型复杂度随变量和约束数量增加而急剧上升的情况。 传统的非线性优化方法通常只搜索局部最优解，这基于一个假设，即存在一个“足够好”的初始解位于全局解的吸引域内。但实际情况并非总是如此，复杂的非线性模型可能需要全球优化策略。 #### 2. 全球优化策略 如今，有超过一百本教科书和越来越多的网站部分或全部致力于全球优化。此外，还有大量关于组合优化（CO）的文献，理论上 CO 是 GO 的一个子集。 全球优化方法主要分为两类：精确方法和启发式方法。 ##### 2.1 精确方法 - **“朴素”方法**：如网格搜索和纯随机搜索，显然是收敛的，但随着问题规模增大通常不可行。 - **分支定界方法**：包括基于区间算术的策略，以及针对 Lipschitz 全球优化和某些凸函数差（D.C.）模型的定制方法。这些方法也可应用于约束满足问题和纯整数及混合整数规划。 - **同伦方法**：旨在找到光滑 GO 模型的全局解集合。 - **隐式枚举技术**：例如凹最小化模型中的顶点枚举和组合优化中的通用动态规划。 - **随机收敛顺序采样方法**：包括自适应随机搜索、单起点和多起点方法、贝叶斯搜索策略及其组合。 以下是精确方法的总结表格： | 方法类型 | 特点 | | ---- | ---- | | “朴素”方法 | 收敛但问题规模增大时不可行 | | 分支定界方法 | 多种策略，可用于多种规划问题 | | 同伦方法 | 用于光滑 GO 模型 | | 隐式枚举技术 | 特定模型的枚举方法 | | 随机收敛顺序采样方法 | 多种搜索策略组合 | mermaid 流程图展示精确方法的分类： ```mermaid graph LR classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; A(精确方法):::process --> B(“朴素”方法):::process A --> C(分支定界方法):::process A --> D(同伦方法):::process A --> E(隐式枚举技术):::process A --> F(随机收敛顺序采样方法):::process ``` ##### 2.2 启发式方法 - **蚁群优化**：基于个体