1 半定松弛的基本思想
1.1 从原问题到凸松弛的“放宽”策略
半定松弛的出发点是：许多优化问题之所以难，并不是目标函数太复杂，而是变量之间存在“非凸的代数关系”，使可行域呈现难以直接处理的几何形状。典型例子是含有二次项、乘积项或由离散变量（如0-1、±1）引入的非凸约束。半定松弛通过引入一个新的矩阵变量，把这些非凸关系中的“关键结构”用半定约束来承载，同时放宽原本严格的等价关系。放宽后得到的可行域通常更大，因此求得的代价值（取决于目标方向）往往可作为原问题的上界或下界。
这种放宽并非随意替换：它通常以“把向量的外积视作新变量”的方式出现。原问题中常见的“变量乘积”被替换为矩阵元素，随后用矩阵半定性约束来保证某些代数一致性。这样一来，原先不可凸的约束被替换为半定约束，整体就落入半定规划这一类凸优化框架。
1.2 与线性/二次松弛的关系与差异
在优化理论中，“松弛”并不新奇：线性松弛把离散约束放宽为凸包，二次松弛把非凸二次约束改写为更容易求解的形式。半定松弛可以理解为更强的一种松弛：它不只是在变量尺度上放宽约束，而是提升到矩阵尺度，利用半定性刻画“变量之间二阶相关结构”。
与仅依赖线性形式的松弛相比，半定松弛可保留更多关于二次关系的信息，因此在很多问题上能得到更紧的界（更小的松弛间隙）。与传统二次松弛相比，半定松弛在表达能力上更灵活：除了能处理某些二次型，还能将若干等式/不等式的乘积关系统一吸收到矩阵约束中，代价是模型规模与计算负担通常更高。
1.3 半定约束为何能带来可解性
半定约束的本质是对称矩阵的半正定性，即要求新矩阵变量属于一个“凸锥”。半定规划的约束结构由半定锥与仿射约束共同组成，从而整体形成凸优化问题。凸性意味着：局部最优通常等同于全局最优，并且可以使用成熟的凸优化方法求解，如内点法或第一阶方法等。
此外，半定约束带来的数值性质较好。相较于直接在非凸空间中搜索，半定松弛把难点转移为求解凸锥中的矩阵变量，这使得算法实现与收敛分析更为可控。尽管这不保证总能得到精确的原问题解，但至少提供了可行的优化求解通道。
2 数学表述与标准形式
2.1 半定约束的记号与可行域含义
半定约束通常记为 \[ X\succeq 0 \] 表示矩阵 \(X\) 为半正定。其可行域由所有满足该条件的对称矩阵构成，是一个凸锥。与之配套的仿射约束一般形如 \[ \mathrm{tr}(A_i X)=b_i \quad\text{或}\quad \mathrm{tr}(A_i X)\le b_i \] 其中 \(\mathrm{tr}\) 为迹运算，\(A_i\) 为给定对称矩阵。
半定约束的关键在于它不仅刻画“某些二次型非负”，更提供了对变量二阶关系的全局一致性：在合适构造下，半定矩阵可被解释为若干向量的外积，从而把“变量乘积结构”转化为向量几何约束。
2.2 典型目标函数与约束形式
一个常见的半定规划标准形式可写为： \[ \min_X\ \mathrm{tr}(C X) \] \[ \text{s.t.}\ \mathrm{tr}(A_i X)=b_i,\quad i=1,\dots,m, \] \[ X\succeq 0. \] 这里 \(C\) 与 \(A_i\) 是已知矩阵，\(b_i\) 是常数。之所以使用迹表达，是因为迹运算与二次型/内积之间有紧密联系：若 \(X\) 被构造成某种外积形式，则 \(\mathrm{tr}(C X)\) 对应原问题的二次或线性目标表达。
在半定松弛中，原问题通常先被改写为“某些关于 \(x\) 的二次表达”，再用矩阵 \(X\) 承载这些表达。随后通过等式约束把 \(X\) 与原变量的关系尽可能绑定；最后用 \(X\succeq 0\) 代替原先过于严格的非凸一致性条件。
2.3 何时能保证得到凸问题
当松弛步骤能将所有难点都转化为： 1) 仿射约束（等式或不等式的仿射形式），以及 2) 单一半定锥约束 \(X\succeq 0\)， 则问题整体为凸优化问题。此时目标若为线性（迹形式），约束若均为仿射，则属于半定规划的典型框架。
因此，可行性的判断并不依赖原问题是否“二次/非凸”本身，而取决于松弛后模型是否确实落在半定锥与仿射结构的交集中。只要构造合理，半定松弛通常会给出凸问题；但模型规模可能显著增长，这是工程上需要权衡的部分。
3 典型应用场景
3.1 二次优化与比值型问题
二次优化是半定松弛最常见的来源之一。若原问题包含二次型目标或二次约束，例如 \(x^\top Q x\) 或 \((a^\top x)^2\)，往往可以通过引入矩阵变量把二次项线性化在 \(X\) 上，再用半定约束承接非凸性。
比值型问题（例如形如 \(\frac{x^\top A x}{x^\top B x}\)）也常能通过变量变换或引入额外标量参数，将其转为与半定约束相关的形式。此类问题在工程设计、信号处理与统计学习中出现较多。半定松弛在这些场景中常用于得到界或近似解，并对原问题的难点（通常来自分式与非凸区域）提供可解替代。
3.2 符号/布尔变量的优化（如±1变量）
离散变量问题如0-1规划、±1规划通常具有强非凸性。半定松弛的常见思路是：把离散约束（例如 \(x_i\in\{\pm 1\}\)）对应的乘积关系转化为矩阵一致性条件，然后用半定约束放宽离散性。
这类问题在编码设计、组合优化与某些机器学习模型中常见。半定松弛能够在放宽后保留“二阶相关结构”，从而比简单的线性松弛更可能获得紧的界。但要得到离散解，往往需要进一步的截断或随机化步骤（见后文）。
3.3 图优化与谱方法相关问题
图优化中包含大量用二次型表示的目标与约束，例如最大割、图划分、团/独立集相关近似等。许多此类问题可以写成与图拉普拉斯、邻接矩阵相关的二次形式。半定松弛常被用来构造谱型松弛：把变量表示为向量，令它们的内积构成半定矩阵，从而将组合目标替换为半定规划目标。
这种联系使半定松弛与谱方法在直观上相通：谱方法常从特征分解获得连续表示，而半定松弛通过矩阵半定性保证这些表示满足一致的几何结构。实际应用中，半定解常再通过截断策略回到离散图划分。
3.4 距离几何与嵌入类问题
距离几何与嵌入问题的核心是：给定（或估计）一组距离/相似度关系，寻找一组点的坐标，使得距离与目标误差最小。若距离平方与内积之间存在标准转换，这类问题就会自然落入二次或半定结构。
半定松弛可用于“从局部一致性到全局坐标”的构造。例如在某些嵌入框架中，可以把Gram矩阵（内积矩阵）作为变量，并施加半定约束来保证它对应某组真实向量，从而形成可解的凸优化问题。所得嵌入可用于可视化、度量学习或图上的低维表示。
4 解的质量与近似保证
4.1 下界/上界与松弛间隙（gap）
由于半定松弛通常是放宽原可行域，若目标最小化，则半定松弛的最优值往往提供原问题的下界（反之亦然，取决于符号与约束方向）。松弛间隙（gap）衡量松弛解与原问题最优之间的差距，是评价近似质量的重要指标。
在实际问题中，松弛间隙的大小与问题结构强相关：有些实例松弛非常紧，甚至能直接得到原问题最优；另一些实例需要借助额外步骤改善离散解质量。理解gap能帮助选择是否值得进行更高规模的求解或更复杂的后处理。
4.2 截断与随机化（rounding）构造近似解
当原变量是离散的，半定规划求得的是连续矩阵解，并不直接满足离散取值。截断（rounding）旨在把连续解转换为离散变量。常见做法包括：
- 对半定矩阵的特征/因子分解得到向量表示，再根据向量方向投影得到±1或0-1决策；
- 使用随机化：从半定解对应的协方差/Gram结构中采样向量，再用阈值或最大化规则映射到离散解。
截断的关键是尽量让映射后目标值不要偏离过多。对某些经典问题（如特定图切割形式、±1二次优化等），截断策略能给出可证明的期望性能界（见下一节）。
4.3 近似比与可证明性能的来源
近似比通常体现为：从半定松弛得到的离散解，其目标值在最坏情形下相对最优值的比例或差距保证。可证明性能往往来自两部分： 1) 松弛解提供界（下界或上界）； 2) 截断/随机化策略能将半定解“以可控方式”转化为离散解，使得期望目标值与松弛界之间存在关系。
在某些模型上，半定松弛不仅提供数值答案，还给出形式化的保证：即使离散化不可避免带来误差，仍能上界误差的增长幅度。具体常数取决于问题类型与松弛构造方式。
4.4 可行性恢复与约束满足的处理
除了目标值，离散化后还可能违反原约束（例如某些容量、指派或一致性条件）。可行性恢复强调：在尽量保持目标质量的同时，将解调整到满足约束的集合里。
常见处理方式包括：
- 对违反约束的变量做局部修正或重新选择；
- 引入罚函数或拉格朗日乘子思想，在离散化时就偏向满足约束；
- 采用带约束的截断规则，把“满足约束”作为决策准则的一部分。
在实践中，是否需要严格满足所有约束，取决于问题的工程容忍度与应用场景；但从优化角度看，可行性恢复通常是让近似解真正可用的重要步骤。
5 计算实现
5.1 半定规划求解器概览（内点法、第一阶法）
半定规划可由多类算法求解。内点法（IPM）以高精度为优势，适合中小规模或需要较高精度的情况；其每次迭代通常计算较复杂的线性代数步骤，并在收敛到高精度时表现稳定。
第一阶法（如投影梯度类、交替方向乘子法ADMM变体等）更适合大规模或需要较低精度的工程场景。它们通常计算开销更低、可扩展性更好，但对收敛速度与精度控制更依赖步长策略与预处理。
5.2 规模与数值稳定性问题
半定松弛常带来显著规模膨胀：若原变量维度为 \(n\)，半定矩阵变量可能是 \(n\times n\)（或包含扩展维度），从而变量数量与约束数量都可能大幅增加。规模带来的后果包括：内存占用增大、矩阵操作成本上升，以及求解误差对结果的影响更明显。
数值稳定性方面，松弛约束往往包含大量迹/线性测度，矩阵系数可能跨越不同数量级。良好的尺度化（scaling）、正则化或预条件（preconditioning）能降低病态问题，提高求解可靠性。工程上还需注意：模型冗余约束过多时，求解器可能出现停滞或精度下降。
5.3 复杂度估计与工程折中
复杂度通常与半定变量的维度、约束数量以及算法迭代次数有关。内点法在理论上可给出多项式时间界，但常数因子较大；第一阶法则更依赖实际实现的收敛性与容差设置。
工程折中体现在：
- 是否选择更紧的松弛（可能带来更大模型）与是否接受更粗的近似；
- 求解精度（容差）与运行时间之间的平衡；
- 对稀疏结构进行利用以减少计算。
在许多应用中，目标不是求极致精确的半定最优值，而是获得足够好的界与可行离散解，因此容差设置与后处理方案对最终效果同样关键。
5.4 稀疏性与结构利用
当图结构、网络结构或局部性强时，对应的矩阵变量或约束系数往往呈现稀疏或块结构。利用这些结构能显著降低计算成本。例如：
- 稀疏矩阵运算替代稠密线性代数；
- 块对角或低秩结构带来更高效的分解；
- 对约束进行等价变换，使线性代数子问题更易求解。
结构利用的前提是松弛构造能保留原问题的代数组织方式，而不是完全“展开”成无结构的大矩阵。合理建模往往直接影响求解速度与可扩展性。
6 理论视角与扩展
6.1 拉格朗日对偶与对偶可行性
半定规划具有对偶结构。对偶变量对应约束的乘子信息，通过构造对偶可行解可以得到对偶目标值，从而与原问题形成上下界关系。若满足合适的正则条件（例如无隙性或Slater条件在适用条件下成立），原问题与对偶问题的最优值会相等，这使得界的解释更清晰。
对偶可行性也用于验证数值结果的质量：若数值求解得到的原解与对偶解之间差距较小，就表明当前解质量较高。
6.2 乘子、KKT条件与最优性判别
KKT条件提供了最优性判别框架。对半定规划而言，KKT通常涉及：
- 原问题可行性（半定性与仿射约束满足）；
- 对偶问题可行性；
-互补松弛（与矩阵半定性相关的互补条件）。
在数值求解中，KKT残差可以作为停机准则或误差度量，用于判断当前迭代是否足够接近最优。对于希望获得可靠近似保证或严格界的问题，利用KKT残差能降低“看似收敛但质量不足”的风险。
6.3 加强松弛：层级化/向量化思想
半定松弛的一个常见扩展方向是加强松弛：在保留半定框架的同时，引入更高阶一致性约束或更细粒度的矩阵表示。直观上，这相当于让放松更接近原问题，从而减小松弛间隙。
在理论层面，这类加强常以“层级化”（逐步增加约束复杂度）或“向量化”（引入更丰富的向量/矩阵变量表征）方式出现。代价是模型维度增加、求解更困难。工程上通常需要在“界更紧”和“可计算性”之间寻找折中点。
6.4 与其他松弛（如SOCP）对比
SOCP（二阶锥规划）是另一类常见凸松弛框架。许多二次约束可以直接写为二阶锥约束，从而无需引入半定矩阵变量。一般而言，SOCP模型往往规模更小、求解更快；但在表达能力与界紧度上，半定松弛往往更强。
对比的核心不在于“哪个一定更好”，而在于：某个具体问题的结构是否能被较紧地映射到SOCP，还是更自然地落入半定结构。不同松弛在界质量与计算成本之间形成不同权衡。
7 常见变体与命名由来
7.1 形如“向量化变量”的SDR框架
许多半定松弛可用“向量化变量”的统一描述。典型做法是把原变量 \(x\) 的若干二次关系表达成向量内积。于是，矩阵 \(X\)（如Gram矩阵）可被理解为这些向量内积的集合。只要施加 \(X\succeq 0\)，就保证该矩阵确实对应某组向量，从而形成可解的凸约束。
这种“先向量后矩阵”的视角有助于理解截断：既然半定解对应向量几何，那么将向量再映射为离散决策就成为自然的后处理流程。
7.2 目标函数与约束对应的不同松弛方式
半定松弛不止一种写法。不同问题在构造时可能采用不同的等式约束保留策略：
- 有的松弛保留更多与原变量相关的线性一致性；
- 有的松弛只保留必要的边界条件；
- 有的将某些非凸约束以罚或松弛形式吸收进目标。
同一类问题也可能有多个等价层面的半定建模方式，它们在计算效率与界紧度上可能差异明显。因此半定松弛通常是“框架”，而具体构造要结合问题结构选择。
7.3 与“Shor松弛”等经典命名的联系（通用思路层面）
在半定松弛的历史发展中，出现过一些与二次优化特定构造相关的命名，如Shor松弛等。它们通常体现为一种“把二次型关系改写为矩阵半定约束”的具体模板。无论具体名称如何变化，通用思路都是：把难点转化为对某个候选矩阵施加半定性，从而形成可求的凸优化问题。
命名往往对应特定的构造细节或常见应用对象。理解这些经典命名的价值在于快速识别某类问题能否采用成熟模板进行松弛，而不是严格依赖某一个固定公式。
8 示例与直观理解
8.1 一个二次目标的标准松弛流程
考虑一个含二次目标的最小化问题，形式上可概括为：
- 目标：包含 \(x^\top Q x\) 或带线性项的二次型；
- 约束：包含若干二次不等式或等式。
标准流程通常是： 1) 将所有二次项整理成关于 \(x\) 的二次型表达； 2) 引入矩阵变量 \(X\)，用 \(X\) 的元素承载类似 \(x x^\top\) 的关系； 3) 把原先不可凸的“严格等价关系”放松为 \(X\succeq 0\) 的一致性条件； 4) 将目标与约束改写为关于 \(X\) 的迹或线性测度； 5) 得到半定规划并求解，获得半定最优值与半定解。
若目标为最小化，半定解的最优值常作为原问题下界；若原问题是最大化，则相反情况更常见。
8.2 从图问题到半定矩阵的直观对应
在图划分或切割问题中，变量往往表示节点属于某一侧的离散选择。将其平方视为常量、把乘积项表示为“同侧/异侧”关系，就会产生二次项。随后可以引入矩阵 \(X\) 作为“节点选择关系”的连续替代：
- \(X_{ij}\) 代表某种与“节点 \(i,j\) 的相对选择”相关的连续量；
- 半定性保证这些连续量在向量层面可以由若干表示共同产生。
这样，原本离散的同侧/异侧结构变成向量内积结构，最后通过切割或阈值把向量再映射回离散划分。
8.3 截断示例：由半定解得到离散解的思路
直观的截断流程可以概括为： 1) 求得半定解 \(X\)； 2) 把 \(X\) 分解为若干向量的Gram矩阵形式（例如从特征分解或因子分解得到向量表示）； 3) 对每个节点/变量对应的向量做方向选择，例如根据向量与某个参考方向的符号决定±1，或根据投影值与阈值决定0-1； 4) 得到离散解，并计算其目标值；若仍需满足额外约束，可进行可行性恢复。
若使用随机化，通常会重复采样多次并挑选表现最好的候选解，从而在概率意义下提高近似质量。