数值优化：二次规划与 active set 方法

"该资源是一份关于数值优化的讲义，涵盖了二次规划、有效集方法以及序列二次规划法。由Che-Rung Lee撰写，日期为2011年4月27日。主要内容包括二次规划的通用形式、拉格朗日乘子法、Karush-Kuhn-Tucker (KKT) 条件及其矩阵形式，特别是对于具有等式约束的情况。" 二次规划是一种优化问题，目标是最小化一个二次函数，同时满足一系列线性约束条件。其一般形式如下： $$ \min_{\vec{x}} \quad g(\vec{x}) = \frac{1}{2}\vec{x}^T G \vec{x} + \vec{c}^T \vec{x} $$ 其中，$G$ 是一个对称矩阵，代表了目标函数的二次项系数，$\vec{c}$ 是线性项系数，$\vec{x}$ 是决策变量。约束条件可以分为等式约束 $ \vec{a}_i^T \vec{x} = b_i $（$i \in E$）和不等式约束 $ \vec{a}_i^T \vec{x} \geq b_i $（$i \in I$）。这里的 $\vec{a}_i$ 是约束向量，$b_i$ 是对应的常数值。 拉格朗日乘子法是用来处理带约束优化问题的一种工具，通过引入拉格朗日乘子 $\vec{\lambda}$ 将原问题转换为无约束的优化问题。拉格朗日函数定义为： $$ L(\vec{x}, \vec{\lambda}) = \frac{1}{2}\vec{x}^T G \vec{x} + \vec{c}^T \vec{x} - \vec{\lambda}^T (\vec{A}\vec{x} - \vec{b}) $$ 其中，$\vec{A}$ 是约束矩阵，$\vec{b}$ 是约束右边的常数值。 Karush-Kuhn-Tucker (KKT) 条件是解决带有等式和不等式约束的凸优化问题的必要条件。这些条件包括： 1. 拉格朗日函数的梯度等于零：$\nabla L(\vec{x}, \vec{\lambda}) = 0$。 2. 等式约束：$\vec{a}_i^T \vec{x} = b_i$ 对于所有 $i \in E$。 3. 不等式约束的边界：$\lambda_i \geq 0$ 对于所有 $i \in I$。 4. 非负乘子的互补松弛条件：$\lambda_i (\vec{a}_i^T \vec{x} - b_i) = 0$ 对于所有 $i \in I$。 在存在满秩的约束矩阵 $\vec{A}$ 的等式约束情况下，KKT 矩阵是一个方程组的形式，它表示为： $$ \begin{bmatrix} G & -\vec{A}^T \\ \vec{A} & 0 \end{bmatrix} \begin{bmatrix} \vec{x} \\ \vec{\lambda} \end{bmatrix} = \begin{bmatrix} -\vec{c} \\ \vec{b} \end{bmatrix} $$ 这个矩阵是KKT条件的矩阵表达，当$G$是对称且正定时，如果解满足KKT条件，则该解是原优化问题的全局最优解。 序列二次规划法（Sequential Quadratic Programming, SQP）是一种求解非线性优化问题的迭代算法，特别是在二次规划问题中应用广泛。SQP方法通过在每一步迭代中近似原问题为一个二次模型，并解决相应的二次规划子问题，逐步逼近最优解。这种方法在实际工程和科学计算中非常实用，尤其适用于大型优化问题。