Semidefinite Programming

半正定规划介绍

问题定义

半正定规划问题（Positive Semidefinite Programming）是一类特殊的非线性凸优化问题，被广泛地使用于求解控制优化、结构设计与组合优化问题的凸松弛。与一般的数学规划问题不同，半正定规划的主要优化变量为一系列矩阵，其常用的标准形式由

$\begin{array}{c} \min_x & \sum_{j = 1}^p \langle C_j, X_j \rangle & \\ \text{subject to} ~~& \sum_{j = 1}^p \langle A_{i j}, X_j \rangle = b_i, & i = 1, \ldots, m\\ & X_j \in \mathbb{S}_+^{n_j}, & \end{array}$

给出。其中为问题的系数参数，均为对称矩阵；为等式约束的右手向量；问题的优化变量为一系列的对称半正定矩阵。半正定规划中的矩阵内积运算由给出。

半正定规划是凸优化问题的一个分支，它具有线性目标函数（由用户指定的最大化或最小化函数），且其定义在半正定矩阵构成的凸锥与仿射空间的交集上，即光谱面。

在最佳化理论中，半正定规划是一个相对较年轻的领域，并且基于各种原因，学界不断的增加对它的兴趣：许多作业研究和组合最佳化的问题都能建模成半正定规划问题，或以半正定规划的方式得到近似解；在自动控制理论中，半正定规划用于处理线性矩阵不等式。此外，半正定规划是锥规划的特例，因此实际上可以内点法快速求解。所有线性规划问题都可以表示成半正定规划，此外，多项式最优化问题的解也可以由半正定规划逼近。

半正定规划经常用于处理复杂系统的最佳化，而近年来，量子查询复杂性理论的问题也经常被建模成半正定规划。

求解算法

目前主流的半正定规划求解器主要使用内点法（Interior Point Method）作为底层算法，目前已有较成熟实现的半正定规划内点算法包括

原始对偶内点算法（Primal Dual Interior Point Method）

包括 Infeasible Interior Point Method 与 Homogeneous Self-dual Embedding，为目前主流商用内点法求解器内部算法
对偶障碍函数法（Dual-scaling Interior Point Method）

DSDP 求解器内部实现的内点算法等。