规范对偶理论及其在优化问题中的应用

# 规范对偶理论及其在优化问题中的应用 ## 1. 规范对偶理论基础 规范对偶理论在非凸分析和全局优化问题中具有重要作用。首先定义了 $U_{\Lambda}(\varsigma)$： \[U_{\Lambda}(\varsigma) = \text{sta} \{\langle\Lambda(x); \varsigma\rangle - U(x) : \forall x \in U_a\}\] 它可以在对偶可行空间 $V_k^*$ 上很好地表述。基于此，规范对偶问题可表述为： \[\max\{P_d(\varsigma) = -U_{\Lambda}(\varsigma) : \varsigma \in V_k^*\}\] ## 2. 二次约束下的二次最小化问题 ### 2.1 问题描述 设 $U(x) = x^Tf - \frac{1}{2}x^TAx$ 和 $g(x) = \frac{1}{2}x^TCx - \lambda$ 为二次函数，其中 $A$ 和 $C$ 是 $R^{n\times n}$ 中的对称矩阵，$f \in R^n$ 是给定向量，$\lambda \in R$ 是给定常数。则原问题为： \[\min\left\{\frac{1}{2}x^TAx - f^Tx : \frac{1}{2}x^TCx \leq \lambda, x \in R^n\right\}\] ### 2.2 扩展拉格朗日函数 由于只有一个约束 $g(x) = \frac{1}{2}x^TCx - \lambda$，扩展拉格朗日函数为： \[\Xi(x, \varsigma) = \frac{1}{2}x^T (A + \varsigma C)x - f^Tx - \varsigma\lambda\] ### 2.3 对偶可行空间与对偶问题 对偶可行空间为： \[V_k^* = \{\varsigma \in R | \varsigma \geq 0, \det(A + \varsigma C) \neq 0\}\] 规范对偶问题为： \[\max\left\{P_d(\varsigma) = -\frac{1}{2}f^T (A + \varsigma C)^{-1}f - \lambda\varsigma : \varsigma \in V_k^*\right\}\] ### 2.4 最优解判定 若矩阵 $C$ 正定，$\bar{\varsigma} \in V_a^*$ 是 $P_d(\varsigma)$ 的临界点： - 当 $A + \bar{\varsigma}C$ 正定时，$\bar{x} = (A + \bar{\varsigma}C)^{-1}f$ 是原问题的全局最小解。 - 当 $A + \bar{\varsigma}C$ 负定时，$\bar{x} = (A + \bar{\varsigma}C)^{-1}f$ 是原问题的局部最小解。 ### 2.5 二维空间示例 在二维空间中，设 $a_{11} = 3$，$a_{12} = a_{21} = 0.5$，$a_{22} = -2.0$，$c_{11} = 1$，$c_{12} = c_{21} = 0$，$c_{22} = 0.5$，$f = \{1, 1.5\}$，$\lambda = 2$。此时，对偶问题有四个临界点：$\bar{\varsigma}_1 = 5.22 > \bar{\varsigma}_2 = 3.32 > \bar{\varsigma}_3 = -2.58 > \bar{\varsigma}_4 = -3.97$。根据三态性理论，$x_1 = \{-0.22, 2.81\}$ 是全局最小解，$x_4 = \{-1.90, -0.85\}$ 是局部最小解，$x_2 = \{0.59, -2.70\}$ 是局部最小解，$x_3 = \{2.0, 0.15\}$ 是局部最大解。且有 $P(x_1) = -12.44 < P(x_2) = -4.91 < P(x_3) = 4.03 < P(x_4) = 9.53$。 以下是该问题的求解流程： ```mermaid graph TD; A[定义原问题] --> B[构建扩展拉格朗日函数]; B --> C[确定对偶可行空间]; C --> D[构建对偶问题]; D --> E[求解对偶问题的临界点]; E --> F[根据临界点性质判断原问题最优解]; ``` ## 3. 盒约束下的二次最小化问题 ### 3.1 问题描述 原问题是在盒约束下寻找非凸二次函数的全局最小解： \[\min\left\{\frac{1}{2}x^TAx - f^Tx : c_l \leq x \leq c_u\right\}\] 其中 $x \in R^n$，$c_l$ 和 $c_u$ 是 $R^n$ 中的给定向量。这类问题在偏微分方程、离散最优控制问题等领域经常出现。 ### 3.2 约束的规范形式 为求解该问题，将约束改写为规范形式。不妨假设 $c_l = -1$，$c_u = 1$，则问题变为： \[\min\left\{\frac{1}{2}x^TAx - f^Tx : x_i^2 \leq 1, i = 1, \ldots, n\right\}\] ### 3.3 对偶可行空间与对偶问题 约束 $\Lambda(x) = \{g_i(x)\} = \{x_i^2 - 1\} \leq 0 \in R^n$ 是向量值二次函数，规范对偶变量 $\varsigma = \{\varsigma_i\}$ 是 $R^n$ 中的向量。对偶可行空间为