多级（分层）优化：复杂性问题、最优性条件与算法

### 多级（分层）优化：复杂性问题、最优性条件与算法 #### 1. 引言 “层级”（hierarchy）一词源于希腊语“ιραρχια”，代表一种分级（宗教）权威体系。分层（多级）结构在许多复杂系统中广泛存在，尤其是生物学领域。生物系统具有分层的架构设计，其组织控制范围从分子尺度到宏观尺度。这些分层架构依赖关键接口连接不同尺度的结构元素。 自然界利用相似的分子成分构建出具有特定分层复合结构的不同系统。这些结构具有以下特点： - 结构按离散层次组织。 - 结构层次通过组件间的特定相互作用维系。 - 这些相互作用的层次被组织成具有特定功能的定向、独特分层复合系统。 分层结构的数学研究在多个科学领域均有涉及，如环境科学、生态学、生物学、化学工程、分类理论、数据库、网络设计、博弈论和经济学等。研究生物结构中的层级现象，既能揭示有趣的特性，也能发现因分子特性不同而产生的局限性。理解分层设计的复杂性，需要能够对这些结构进行建模、分析和优化的系统方法。 分层优化（或多级优化）可用于研究这些分层设计的特性。在分层优化中，约束域由一系列必须按预定顺序求解的优化问题隐式确定。它是数学规划的一种推广，最简单的两级（或双层）规划问题描述了一个由两级决策者组成的分层系统。 双层规划问题由两个优化问题组成，其中上层问题的约束集由下层问题隐式确定： \[ \begin{align*} \min_{x} F(x, y)\\ \text{s.t. } G(x, y) \leq 0\\ \text{其中 } y \text{ 求解 }\\ \min_{z} f(x, z)\\ \text{s.t. } g(x, z) \leq 0\\ x \in X \subset R^n, y, z \in Y \subset R^m \end{align*} \] 其中 \(X \subseteq R^n\) 和 \(Y \subseteq R^m\) 是紧集，\(G : R^n \times R^m \to R^p\)，\(g : R^n \times R^m \to R^q\)，\(F, f : R^n \times R^m \to R\) 是标量函数。设 \(\Omega = \{(x, y) | G(x, y) \leq 0, g(x, y) \leq 0, (x, y) \in R^n \times R^m\}\) 为问题的约束集，对于任意 \(x \in X\)，用 \(S(x)\) 表示下层规划问题的解集。 当目标函数和约束函数为线性时，上述问题称为双层线性规划问题。对于双层线性规划问题，已知其解位于可行集的一个极点上。若目标函数或约束函数中至少有一个是非线性的，则该问题称为非线性双层规划问题。一般来说，双层优化问题是非凸的，因此找到全局最优解并非易事。 双层规划在多个领域有广泛应用，包括经济学、网络设计、交通规划与建模、信贷分配和电力定价等。 #### 2. 复杂性问题 复杂性分析旨在揭示优化问题的内在难度，并展现许多其他优化问题及其解之间的惊人联系。 ##### 2.1 寻找全局解的复杂性 Calamai 和 Vicente 提出了一种生成双层规划问题的技术，利用该技术可生成具有指数级局部极小值的线性双层规划问题。Jeroslow 证明了线性双层规划是 NP 难问题，其结果随后被 Ben - Ayed 和 Blair 以及 Blair 证实和简化，并被 Hansen 等人加强。Hansen 等人通过考虑线性最大 - 最小优化问题的一个特殊情况的复杂性，证明了无上层约束的线性双层问题（一种更受限的最大 - 最小问题）是强 NP 难问题。对于更高层次的层级结构，Jeroslow 表明 \((k + 1)\) 级线性规划的最优值是 \(\Sigma_k\) 难的。 ##### 2.2 局部搜索方法的复杂性 在实际应用中，计算局部最优解通常比寻找全局最优解更容易。然而，从复杂性的角度来看，即使对于约束和目标具有简单结构的二次问题实例，检查可行点的局部最优性以及检查局部极小值是否严格的问题也是 NP 难的。Vicente 等人证明了在双层规划中检查局部最优性是一个 NP 难问题。 ##### 2.3 近似算法 Jeroslow 指出，对于任何常数因子 \(c\)，找到一个与最优值相差 \(c\) 倍的解仍然是 NP 难的。Deng 等人将这一结果扩展到即使对于足够小的乘法因子也不允许有加法常数的情况。 ##### 2.4 多项式可解问题 Liu 和 Spencer 为具有固定数量下层控制变量的双层线性问题引入了一种多项式时间算法。Deng 等人对上述结果给出了更简单的证明，并将其扩展到当所有下层线性规划控制的变量总数为常数时的 \(k\) 级线性规划问题。 #### 3. 最优性条件 Bard 首先基于双层规划问题的等价单层规划问题推导了其最优性条件，但 Clark 和 Westerberg 给出了这些条件的反例。Ye 等人给出了广义双层规划问题（下层问题为变分不等式的双层规划问题）的必要最优性条件。 下面定义双层问题的全局和局部最优性概念： \[ \begin{align*} \min_{x} F(x, y)\\ \text{s.t. } G(x) \leq 0\\ \text{其中 } y \text{ 求解 }\\ \min_{z} f(x, z)\\ \text{s.t. } g(x, z) \leq 0\\ x \in R^n, y, z \in R^m \end{align*} \] 其中 \(X = \{x | G(x) \leq 0\}\) 是紧集。 **定义 1**：点 \((x^*, y^*)\) 称为问题的局部最优解，当且仅当 \(x^* \in X\)，\(y^* \in S(x^*)\)，且对于所有 \(y \in S(x^*)\)，有 \(F(x^*, y^*) \leq F(x^*, y)\)，并且存在 \(\delta > 0\)，使得对于所有 \(x \in X \cap B(x^*, \delta)\)，有 \(\varphi(x^*) \leq \va