多级（分层）优化：理论、方法与应用

### 多级（分层）优化：理论、方法与应用 #### 1. 多级优化基础概念 在多级优化中，我们会遇到一些重要的定义和定理。首先定义集合 \(K\) 为 \(K = \{(x, f_1, f_2, d) | (x = 0 \text{ 且 } f_2 > 0) \text{ 或 } (f_1 > 0 \text{ 且 } d \geq0)\}\)，然后定义通常的锥序 “\(<_K\)” 为 \(a <_K b \Leftrightarrow b - a \in K\)。有定理表明，如果 \(\phi(x, y)\) 是关于 “\(<_K\)” 的非支配点，那么 \((x, y)\) 是关于 “\(\prec\)” 的非支配点。这意味着找到关于 “\(<_K\)” 的非支配点，该点可能是双层规划的最优解。 #### 2. 多元分区方法 多元分区方法是解决非线性单级数学规划问题的一种有效途径。考虑如下多元优化问题： \(\min f(x)\) \(\text{s.t. } x \in D\) 其中 \(D \subset R^n (n > 1)\) 是一个鲁棒集，\(f(x)\) 是 \(D\) 上的连续函数。 ##### 2.1 集合分区的定义 对于给定集合 \(S\)，集合 \(\Delta_1, \ldots, \Delta_p\) 被称为 \(S\) 的一个分区，需满足以下条件： 1. \(\Delta_i \subseteq S\) 非空，\(i = 1, \ldots, p\)。 2. \(\Delta_i \cap \Delta_j = \varnothing\)，\(i \neq j\) 且 \(i, j = 1, \ldots, p\)。 3. \(\bigcup_{i = 1}^{p} \Delta_i = S\)。 ##### 2.2 多级优化问题的表述 基于上述分区，问题 (6.6) 的多级优化表述可以写成： \(\min_{y_{\sigma_1} \in D_{\sigma_1}} \left\{\min_{y_{\sigma_2} \in D_{\sigma_2}} \cdots \left\{\min_{y_{\sigma_p} \in D_{\sigma_p}} f(\Delta_1, \ldots, \Delta_p)\right\}\right\}\) 其中 \(\sigma = (\sigma_1, \ldots, \sigma_p)\) 是集合 \(\{1, \ldots, p\}\) 的一个排列，\(D_{\sigma_i}\) 是对应于集合 \(\Delta_i\) 的变量 \(y_{\sigma_i}\) 的可行域。 ##### 2.3 双层优化问题的特殊情况 当 \(\{I^-, I^+\}\) 是问题 (6.6) 索引集 \(I = \{1, \ldots, n\}\) 的一个分区时，双层优化表述为： \(\min_{y^- \in D_{S^-}} g(S^-)\) 其中 \(g(S^-)\) 是问题 \(\min_{y^+ \in D_{S^+}} f(y^-, S^+)\) 的最优值。 ##### 2.4 多元分区方法的步骤 多元分区方法包含以下步骤： - **策略 I**：对于每个 \(i = 1, \ldots, p\)，通过求解问题 (6.9)（其中 \(S^- = \overline{\Delta_i} = S \setminus \Delta_{\sigma_i}\)），得到对应于 \(S^+ = \Delta_{\sigma_i}\) 的改进点 \(\tilde{y}_{\sigma_i}\)。 - **策略 II**：对于每个 \(i = 1, \ldots, p\)，记 \(\overline{\Delta}^-_i = \{\tilde{y}_{\sigma_j} | j < i, j = 1, \ldots, p\}\)，\(\overline{\Delta}^+_i = \{y_{\sigma_j} | j > i, j = 1, \ldots, p\}\)，\(S^- = \overline{\Delta}^-_i \cup \overline{\Delta}^+_i\)。通过求解问题 (6.9) 得到对应于 \(S^+ = \Delta_{\sigma_i}\) 的改进点 \(\tilde{y}_{\sigma_i}\)。 - **改进点**：基于改进的探索点 \(\tilde{y} = (\tilde{y}_{\sigma_1}, \ldots, \tilde{y}_{\sigma_p})\)，使用搜索和决策方案得到改进的可行点 \(y^*_{\sigma}\)。 下面是多元分区方法的流程图： ```mermaid graph TD; A[开始] --> B[选择策略 I 或 II]; B --> C{策略 I}; C -- 是 --> D[求解问题 (6.9)，S^- = \overline{\Delta_i}]; C -- 否 --> E[求解问题 (6.9)，S^- = \overline{\Delta}^-_i \cup \overline{\Delta}^+_i]; D --> F[得到改进点 \tilde{y}_{\sigma_i}]; ```