刘琬纯，何洪津

(杭州电子科技大学理学院，浙江 杭州 310018)

0 引 言

二次规划(Quadratic Programs, QP)是一类经典的数学优化模型，在工程、管理和经济等领域有着广泛的应用。在过去的几十年中，二次规划，尤其是凸二次规划的相关理论和算法得到了较完善的发展，但大规模二次规划的高效算法设计仍值得深入研究。近十年来，交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)在压缩感知、机器学习和图像处理等领域取得了诸多成功应用，在各领域掀起了交替方向乘子法的研究热潮。文献[1]给出了求解二次规划问题的交替方向乘子法。随后，有学者分析了交替方向乘子法求解二次规划时具有线性收敛速率[2]；文献[3-4]进一步分析了交替方向乘子法求解严格凸二次规划时的最优化参数选择策略。不难发现，按照文献[1]提出的交替方向乘子法框架，其线性等式约束的子问题可归结为一个增大规模的线性方程组。当线性方程组系数矩阵无特殊结构时，文献[1]中的处理方式降低了交替方向乘子法的执行效率。另外，现有交替方向乘子法解二次规划的相关文献主要讨论仅含等式和简单约束，或仅含不等式约束这两种情形。然而，现实生活中的案例可能同时具有等式、不等式和简单凸集约束条件。因此，本文针对一般的混合约束凸二次规划问题，设计新的交替方向乘子法，使得其子问题保持与原问题同规模，并且具有封闭解，从而达到提升计算效率的目的。

1 问题描述

考虑二次规划问题：

s.t.Ax=b,Dx≤d,x∈

(1)

式中，P∈n×n为对称半正定矩阵，q∈n,A∈m×n,b∈m,D∈r×n,d∈r,⊂n为简单凸集。……