序列二次规划
序列二次规划是求解非线性约束优化问题的重要数值方法。我将从问题背景出发，逐步解释其核心思想和算法流程。
- 问题形式
考虑一般形式的非线性约束优化问题：
\[ \begin{aligned} \min \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & c_i(\mathbf{x}) = 0, \quad i \in \mathcal{E}, \\ & c_i(\mathbf{x}) \geq 0, \quad i \in \mathcal{I}, \end{aligned} \]
其中，\(f(\mathbf{x})\) 是目标函数，\(c_i(\mathbf{x})\) 是约束函数，\(\mathcal{E}\) 是等式约束的指标集，\(\mathcal{I}\) 是不等式约束的指标集。这是一个非常通用的模型，但求解难度很大。
-
核心思想：序列逼近
序列二次规划的基本思想是：在每一步迭代中，构造一个近似的二次规划子问题，通过求解这个相对简单的子问题来获得一个搜索方向，然后沿着这个方向进行线性搜索，逐步逼近原问题的最优解。这是一种“序列逼近”或“局部近似”的策略。 -
子问题的构造：拉格朗日函数的二次近似
为了构造子问题，我们首先引入拉格朗日函数：
\[ L(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i c_i(\mathbf{x}) \]
其中，\(\mathbf{\lambda}\) 是拉格朗日乘子向量。在某个迭代点 \((\mathbf{x}_k, \mathbf{\lambda}_k)\)，我们构造如下二次规划子问题：
\[ \begin{aligned} \min_{\mathbf{p}} \quad & \frac{1}{2} \mathbf{p}^T \nabla_{\mathbf{xx}}^2 L(\mathbf{x}_k, \mathbf{\lambda}_k) \mathbf{p} + \nabla f(\mathbf{x}_k)^T \mathbf{p} \\ \text{s.t.} \quad & c_i(\mathbf{x}_k) + \nabla c_i(\mathbf{x}_k)^T \mathbf{p} = 0, \quad i \in \mathcal{E}, \\ & c_i(\mathbf{x}_k) + \nabla c_i(\mathbf{x}_k)^T \mathbf{p} \geq 0, \quad i \in \mathcal{I}. \end{aligned} \]
这个子问题的设计原理是：
- 目标函数：是拉格朗日函数在 \(\mathbf{x}_k\) 处的二阶泰勒近似（忽略常数项）。
- 约束条件：是原约束函数在 \(\mathbf{x}_k\) 处的一阶泰勒近似（线性化）。
求解这个子问题，我们得到的是一个搜索方向 \(\mathbf{p}_k\)，它被认为是指向原问题改进解的一个良好方向。
- 迭代步骤与线性搜索
获得搜索方向 \(\mathbf{p}_k\) 后，迭代点更新为：
\[ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k \]
其中，\(\alpha_k \in (0, 1]\) 是步长。步长通常通过线性搜索来确定，以确保某种效益函数的充分下降（例如，增广拉格朗日函数或罚函数）。同时，拉格朗日乘子也会更新，通常直接使用子问题求解得到的最优乘子 \(\mathbf{\lambda}_{k+1}\)。
-
Hessian矩阵的近似与算法变体
在子问题中，精确计算拉格朗日函数的Hessian矩阵 \(\nabla_{\mathbf{xx}}^2 L(\mathbf{x}_k, \mathbf{\lambda}_k)\) 可能计算量很大。因此，在实际算法中，常使用拟牛顿法（如BFGS方法或其受限内存版本L-BFGS）来构造一个正定矩阵 \(B_k\) 来近似这个Hessian矩阵。这使得序列二次规划方法能够高效处理大规模问题。 -
总结与特点
序列二次规划方法结合了牛顿法的快速局部收敛性和处理约束条件的天然能力。它被认为是求解中小规模、光滑非线性规划问题最有效的方法之一。其核心在于通过迭代求解一系列二次规划子问题，来系统地逼近原约束优化问题的最优解。