半定规划是一类凸优化问题,其目标是在满足仿射约束、且一个或多个对称矩阵为半正定矩阵的条件下,最小化或最大化线性目标函数。它将线性规划中的非负标量变量替换为特征值必须非负的矩阵变量,从而推广了线性规划。这一变化在保持凸性的同时,大幅拓展了模型能够表达的关系范围。
半定规划的重要性既体现在直接建模上,也体现在松弛方法上:用一个易于求解、能够给出严格界限的问题,替代原本难以求解的优化问题。其应用包括组合优化、控制系统设计、多项式非负性、统计估计和量子信息。其数学理论融合了矩阵几何、锥对偶理论和数值算法;实际求解效果则在很大程度上取决于矩阵规模、稀疏性、条件性以及所需的精度。
数学表述与矩阵不等式
令 表示实对称 矩阵构成的向量空间。若矩阵 满足
则称其为半正定矩阵,记作 。若对每个非零的 ,上述不等式都严格成立,则称其为正定矩阵,记作 。这些定义将半定规划与二次型和正定矩阵联系起来。根据谱定理,矩阵半正定等价于其所有特征值均非负。
带等式约束的标准原问题形式为
其中 ,,且
这是对称矩阵上的迹内积; 表示矩阵的迹。尽管 有 个元素,但由于对称性,独立的标量变量只有 个。
一种等价的建模形式采用线性矩阵不等式,简称 LMI:
这里的优化变量是标量 ,而每个 都是给定的对称矩阵。“线性”指的是矩阵对变量的仿射依赖关系,而不是将矩阵的各个元素与零逐一比较。例如,
等价于 、 且 。因此,这个看似非线性的行列式条件描述的是一个凸区域。
将矩阵变量限制为对角矩阵,就能得到线性规划: 恰好意味着 。多个半正定约束可以合并为一个分块对角矩阵,不过在计算中,保留各个独立的块通常更为有利。也可以使用复厄米矩阵,此时需将转置替换为共轭转置。若 为厄米矩阵,则
建模中的一个核心恒等关系涉及舒尔补。当 时,
例如,
利用这类恒等关系,可以将二次表达式和涉及矩阵逆的不等式表示为更高维的仿射矩阵约束。这些关系仅在所述正定性条件下适用;若矩阵块是奇异的,则还需满足额外的值域条件。
半正定锥的几何结构
集合 是一个闭凸锥。若 且 ,则 。因此,将这个锥与仿射等式所定义的集合相交,便得到凸的可行集。在这样的集合上,线性目标的任何局部极小值都是全局极小值。这使半定规划区别于另一类优化问题:后者在半正定约束之外,还包含指定矩阵秩等非凸要求。
这个锥的边界是弯曲且分层的。其内部由正定矩阵组成,边界则由奇异的半正定矩阵组成。与线性规划所依托的非负正交锥不同,当 时, 不是多面锥:它无法用有限个线性标量不等式来描述。它的极射线由秩一矩阵 生成。事实上,谱分解可将每个半正定矩阵表示为这类矩阵的非负线性组合。
一种有用的等价表示是
因此,每个半正定矩阵都是一个格拉姆矩阵:它的元素可写成向量之间的内积 。这一解释说明了为什么半定松弛经常用向量构型来替代标量的正负号、二元赋值或两两乘积。它也赋予了矩阵的秩以几何意义: 的秩就是实现这种构型所需的最低维数。
锥的各个面对应于对其中矩阵的值域施加的限制。若 是一个 维线性子空间,且 的列向量构成 的一组标准正交基,则相应面中的矩阵具有如下形式:
可行集可能完全位于某个真面中,因此,即使问题存在有意义的解,每个可行矩阵仍可能都是奇异的。识别出这个较小的面,可以同时降低问题的维数和数值求解难度。
这种几何结构还给出了极点秩的界。对于具有 个独立仿射等式约束的半定规划,秩为 的极点可行矩阵满足
这一结论可通过维数论证来理解:将对称扰动限制在该矩阵的值域内,这些扰动构成一个维数为 的空间。如果扰动方向的数量多于独立约束的数量,就存在保持约束不变的非零扰动;沿该方向以足够小的正、负步长扰动后,矩阵仍然半正定,这与其为极点相矛盾。这个界并不意味着每个半定规划都能在某个极点处取得最优值,但它有助于解释为什么低秩最优解经常出现。
对偶性、最优性与病态情形
对于标准形式的原问题,定义线性映射
其对偶问题为
变量 称为对偶松弛矩阵。这一形式源于拉格朗日对偶以及半正定锥的自对偶性:一个对称矩阵与所有半正定矩阵的内积均非负,当且仅当该矩阵本身也是半正定矩阵。
对于任意原问题可行解 和对偶问题可行解 ,都有
这就是弱对偶性。它直接给出了一种实用的验证依据:对偶可行点给出最小值的下界,原问题可行点则给出上界。如果两者之间的间隙为零,那么这两个点都是最优解。与仅有一个目标函数值相比,一对原问题与对偶问题的可行解能够提供可核验的解质量度量。
强对偶性则需要谨慎处理。一个标准的充分条件是斯莱特条件,也称严格可行性。如果原问题存在满足 的可行解,且其最优值有限,那么对偶问题也能达到同一最优值。交换原问题与对偶问题后,相应结论同样成立。当两者均严格可行时,通常的卡鲁什—库恩—塔克条件通过原问题可行性、对偶可行性以及下式来刻画最优性:
对于半正定矩阵 和 ,这一互补条件等价于 ,即两者的值域相互正交。
如果缺乏适当的正则性,半定规划可能出现非零对偶间隙、最优值无法达到或弱不可行等情形。弱不可行是指仿射约束集与锥不相交,但两者之间的距离为零。一个简单的例子是如下矩阵族:
其中没有任何一个矩阵是半正定的,因为半正定矩阵中若某个对角元素为零,其所在行和列就必须全为零。然而,
因此,这一矩阵族不断趋近半正定锥,却始终无法到达其中。
这些现象的部分原因在于,闭半正定锥的线性像未必是闭集。在可行域具有多面体几何结构的普通有限维线性规划中,并不存在直接对应的现象。面约化通过找出包含可行集的最小锥面,并在该锥面上重新表述问题,来处理隐藏的退化性。仅凭数值求解器给出的小残差,并不能将可达到的解与所有病态的极限情形区分开来。
历史发展与计算复杂性
半定规划并非源于某一种统一的表述,而是由几个原本相互独立的研究领域逐渐汇合而成。矩阵的正定性与半正定性早已出现在力学、稳定性理论以及矩和非负多项式的研究中。在控制理论中,亚历山大·李雅普诺夫于十九世纪末开展的研究,将微分方程的稳定性与正定二次型联系起来。到了二十世纪,矩阵不等式已成为稳定性与系统分析中反复使用的数学语言。
组合数学方面的一个重要里程碑,是拉斯洛·洛瓦兹于1979年引入图的 theta 函数。这个参数最初是为给出香农容量的界而提出的,可以表述为半定规划,并将几何向量表示与图论中的量联系起来。它表明,对于原本计算困难的离散问题,矩阵优化能够给出较强且可高效计算的界。
算法上的转折点来自内点法。纳伦德拉·卡马卡于1984年提出的算法,重新激发了人们对线性规划多项式时间内点法的兴趣。随后,尤里·涅斯捷罗夫和阿尔卡季·涅米罗夫斯基建立了自协调障碍函数的一般理论,并于1994年作了系统阐述;这一理论涵盖了半正定锥。他们的工作从理论上解释了为何基于牛顿法的算法能够处理矩阵不等式,并具有复杂性保证。
二十世纪九十年代,应用与软件的发展使半定规划受到更广泛的关注。其中,米歇尔·戈曼斯和戴维·威廉森于1995年提出的最大割近似算法尤其具有影响力。利文·范登贝赫和斯蒂芬·博伊德于1996年发表的综述,有助于确立半定规划作为横跨优化与工程领域的通用框架的地位。此后,专用求解器和建模系统的出现,使人们无需从头实现矩阵锥算法,就能为应用问题建立模型。
不过,讨论复杂性时仍须明确计算设定。在适当的有界性、正则性和数据假设下,可以在关于相关输入参数和精度指标的多项式复杂性内求得近似解。对于标准的短步障碍法,迭代次数的界涉及
其中,对于单个 半正定锥,有 ,而 表示经适当缩放的目标精度。这是迭代次数的估计,而非总算术运算成本:每次迭代都可能涉及大量矩阵运算。
精确可行性和精确最优性问题比近似优化更为微妙。有理数输入数据未必产生有理数最优解,而接近不可行或病态的问题可能需要很高的计算精度。因此,说半定规划“可在多项式时间内求解”,通常需要附带关于近似、编码和正则性的限定条件。这既不意味着任意精确半定可行性问题都与有理数线性规划具有完全相同的计算性质,也不意味着每个以数值形式给出的半定规划都容易计算。
内点算法与数值认证
对于精度要求较高的半定规划,内点法仍是核心方法。用于保证正定性的基本障碍函数为
其中 表示行列式。当某个特征值从正侧趋近于零时,障碍函数趋于无穷大。因此,依次求解一系列加入障碍惩罚项的问题,可以在保持中间迭代点位于锥内部的同时,逐步逼近位于边界上的最优解。
障碍函数的微分结构具有显式表达式:
这些表达式使牛顿法成为自然的选择,但也揭示了计算成本的来源。在许多实现中,矩阵分解以及约束耦合方程组的构造与求解占据了主要的计算开销。如何组织这些计算,是一个数值线性代数问题,而不只是统计决策变量个数的问题。
原始—对偶算法近似沿着一条中心路径前进,这条路径由可行性条件和扰动后的互补关系共同定义:
在精确的中心路径上,
使 趋于零即可缩小对偶间隙。由于矩阵乘法不满足交换律,构造稳定且对称的牛顿方程需要专门的变换。广泛使用的方法包括 Nesterov–Todd 缩放和其他对称化的原始—对偶方向。预测—校正步将估计得到的仿射缩放方向与维持中心性的校正项相结合,从而提高迭代效率。
计算成本在很大程度上取决于矩阵结构以及仿射约束的数量 。仅存储一个稠密对称矩阵所需的空间就与 成正比,而稠密矩阵分解的成本通常与 成正比。构造并分解以约束变量为未知量的舒尔方程组,开销可能更大。因此,一个包含许多小型独立矩阵块的问题,可能比总维数相同、但仅含单个矩阵块的问题容易求解得多。
求解器通常会监测原始等式约束残差、对偶等式约束残差、锥约束违反程度以及经过尺度调整的对偶间隙。在浮点运算中,被判定为半正定的矩阵可能因舍入误差而出现微小的负特征值;而如果可行性误差很大,即使对偶间隙很小也没有意义。尺度调整、条件数以及近乎相关的约束,都会影响对这些量的解读。
对于需要数学证书的应用,有时可以将数值输出转换为精确的对象,或具有严格误差界的对象。相关技术包括有理数重构、区间界,以及先对候选矩阵进行显式修正,再实施带有严格保证的正定性或半正定性检验。这类后处理与获得一个看似可信的数值最优解是两回事。求解器的终止消息只是基于容差作出的判断,本身并不构成严格证明。
大规模方法、低秩模型与稀疏结构
对于大规模问题,内点法的内存需求和矩阵分解成本可能高得难以承受。一阶方法减少了每次迭代的计算量,但通常以更慢的高精度收敛速度为代价。算子分裂方法,包括交替方向乘子法,将仿射约束与锥约束分开处理。投影到半正定锥的基本运算为
其中 。即使这一步也可能代价高昂,因为它需要矩阵的谱信息。
低秩分解用 代替 ,其中 。目标函数变为 ,等式约束则变为
这将存储量从 量级降至 量级,但分解后的问题不再是凸问题。这一方法尤其与塞缪尔·布雷尔和雷纳托·蒙泰罗在 21 世纪初的研究工作密切相关。
在一些重要条件下,分解可以保留良好的优化性质。对于某些光滑、紧致的约束集,关于一般位置下目标函数的研究结果表明,足够大的分解秩可以消除非全局最优的二阶临界点。这一理论中会出现涉及 的阈值条件。这些结论都有适用条件,并非对任意分解形式的半定规划都成立的普遍保证;秩不足、约束奇异以及特殊的目标矩阵都可能改变优化景观。此外,低秩的原始问题候选解并不会自动给出对偶最优性证书。
稀疏性提供了另一条提升可扩展性的途径。数据的总体稀疏模式可以用图表示,图中的边标记数据所用到的矩阵位置。对于弦图,即每个长度至少为四的环都有弦的图,可以通过最大团对应的主子矩阵来刻画半正定补全。这使得某些大规模矩阵约束可以替换为较小的团约束,并辅以重叠部分的一致性条件。
一个关键区别在于:部分元素已指定且允许半正定补全的矩阵,与所有元素均已指定且要求稀疏模式之外的元素为零的矩阵,并不相同。二者的锥描述相互关联,但不能互换。弦图转换还可能引入填充边、额外变量和额外等式。其收益取决于团的大小和分隔集的结构,而不仅仅是非零元素的数量。
其他方法包括在迹有界的半正定集合上使用条件梯度法、采用增广拉格朗日法,以及以矩阵—向量乘积代替显式稠密矩阵的算法。谱预言机有时可以用极端特征值对应的特征向量计算来代替完整的特征值分解。具体采用哪种方法,取决于首要目标是获得高精度证书、中等精度的界,还是大规模近似解。
组合优化与近似保证
许多离散优化问题都可以用秩为一的半正定矩阵来表示。若 ,则矩阵 满足
反过来,这些性质也意味着该矩阵可以用符号向量来表示。去掉秩约束,就得到一个凸的半正定规划。这体现了整数规划的一种通用策略:将变量的乘积提升为矩阵元素,并放松确保这些元素源自同一组变量的非凸条件。
对于加权最大割问题,设 为边权。一个符号向量定义了一个割,其权值为
其半正定松弛为
每个割都对应一个可行矩阵,因此半正定规划的最优值是最大割权值的上界。通过格拉姆表示,松弛后的变量可以表示为单位向量 ,且满足 。
Goemans–Williamson 舍入法随机选取一个经过原点的超平面,并根据各个 所在的一侧将顶点划分为两组。若两个向量的夹角为 ,则它们被分开的概率为 ,而对应边在松弛目标中的贡献为 。比较这两个表达式,可得到期望意义下的近似比
因此,舍入所得割的期望权值至少为最优值的这一比例。这一保证源于几何概率计算,而不只是因为半正定规划给出的数值界接近最优值。
Lovász θ 函数是另一个基本例子。对于图 ,其一种表述为
其中 为全一矩阵。它满足
从而将图的独立数与其补图的色数联系起来。对于五环图,有 。
松弛的质量因问题而异,差别可能很大。有些表述在特定图类上是精确的;另一些则存在较大的整数间隙,即松弛最优值与最优离散解的目标值仍相距甚远。更强的半正定规划层次体系会加入涉及更多变量的一致性约束,但也会增大问题规模。在分支定界法中,半正定规划给出的界有助于对子问题进行剪枝,而对偶可行解则能够在不依赖任何舍入过程的情况下为界提供证明。
多项式优化与平方和
半定规划将全局多项式优化与代数证书联系起来。如果实多项式 满足
则称多项式 为平方和。任何平方和在全局上都非负。对于次数不超过 的多项式,令 包含总次数不超过 的所有单项式。则有
比较两边的系数可得到关于 的线性方程,因此,检验是否存在平方和表示是一个半定规划问题。
一般而言,非负性与可表示为多项式平方和并不等价。大卫·希尔伯特在1888年给出的分类确定了两者等价的特殊齐次情形:二次型、二元型和三元四次型。不属于这些情形的一个经典反例是莫茨金多项式
它是非负的,却不能表示为实多项式的平方和。因此,固定次数的平方和检验未能通过,并不能证明多项式会取负值。
对于定义在
上的优化问题,可以用恒等式
来证明 是 的最小值的一个下界,其中各个 都是平方和。对它们的次数施加上界,就得到一个半定规划。逐步提高次数,可得到一系列可能越来越紧的下界。在相关二次模满足阿基米德条件时,任何在 上严格为正的多项式都具有这样的证书,从而保证这一层级的渐近收敛。仅有紧致性并不意味着所选约束表示自动满足阿基米德条件,不过,对于有界集合,可以通过添加适当的冗余球约束来获得这一性质。
对偶视角采用截断矩序列。矩序列 在形式上表示单项式 的积分。矩矩阵的元素为
如果这些数来自某个非负测度,那么 ,因为任意多项式平方的积分都是非负的。局部化矩阵用于编码支撑条件 。某些秩条件或平坦性条件允许从中提取有限支撑测度,进而得到候选的全局最小点。
让·拉塞尔的矩层级方法,以及巴勃罗·帕里洛针对平方和证书提出的半定方法,约于2000—2001年发展起来,使这一联系成为实用的计算框架。其主要局限在于组合式增长:对于 个变量, 包含 个单项式。利用对称性、稀疏性和适配的多项式基,可以大幅缩减特定问题的规模,但无法消除全局多项式优化的一般性困难。
在控制、统计与量子信息中的应用
在控制理论中,半定规划将许多稳定性条件和性能条件转化为可通过计算检验的矩阵不等式。对于连续时间线性系统
矩阵 为赫尔维茨矩阵,即所有特征值的实部均为负,当且仅当存在 ,使得
此时,函数 沿每条非零轨迹递减。这就是众多控制应用所依赖的二次型李雅普诺夫稳定性证书。
在实际计算中,严格不等式通常通过引入裕量来实现。例如,在齐次性允许通过缩放化为相应形式时,可采用
。对于由有限个系统矩阵的凸包描述的不确定动力学系统,如果存在一个共同的 ,使其在所有顶点处都满足这些不等式,就能证明整个凸包内的系统均稳定。这种共同二次型证书是稳定性的充分条件,但可能较为保守。控制器综合则更为复杂:未知控制器与未知李雅普诺夫矩阵相乘,可能产生双线性矩阵不等式;除非能通过有效的等价变换消除双线性,否则这类问题并不是半定规划。
在统计学中,半正定性体现了协方差矩阵必须满足的基本相容性。因此,根据不完整或含噪声的成对信息估计协方差矩阵时,可能需要在半正定锥上进行优化。最近相关矩阵问题还要求对角线元素均为一。以弗罗贝尼乌斯范数衡量拟合误差的目标函数是凸函数,但不是矩阵元素的线性函数;若需要严格的半定规划表示,可以将其转化为锥上图形式。并非所有凸协方差估计问题都是半定规划:例如,含有对数行列式的目标函数自然会导向更广泛的一类凸矩阵优化问题。
半定约束也出现在低秩恢复中。对于矩形矩阵 ,其核范数,即所有奇异值之和,可表示为
因此,核范数最小化可以写成半定规划,也由此将矩阵补全与秩的凸替代函数联系起来。其应用涵盖恢复仅有部分元素可观测的矩阵、识别低维结构等,不过在大规模实现中,通常会采用专门算法,而非通用的半定规划求解器。
在量子力学中,密度矩阵是迹为一的复厄米半正定矩阵。测量概率是这些矩阵的线性函数,因此半定规划成为对量子态和测量进行优化的自然工具。对于先验概率为 、密度矩阵为 的二元量子态判别问题,最优成功概率可通过下式求得:
这里, 描述二结果测量中的一个结果。更深入的应用利用半定松弛,为与纠缠有关的量以及量子关联求界。物理态的约束天然具有半定形式,但精确可分性等附加要求未必能用简单的有限规模半定规划来描述。