基于MATLAB的半正定规划(SDP)数值求解器

资 源 简 介

本项目旨在利用MATLAB平台实现半正定规划（SDP）问题的数值求解。程序通过构建标准型的半正定规划数学模型，将线性目标函数在对称半正定矩阵约束下进行极小化。该程序结构设计严谨，逻辑条理清晰，完整实现了凸优化理论中处理非线性、非光滑约束的关键步骤。其核心功能包括自动化构建目标系数矩阵、定义线性矩阵不等式（LMI）约束以及调用高效计算引擎进行迭代搜索。本项目不仅适用于基础的数学极值问题求解，更广泛应用于控制理论中的稳定性分析、组合优化中的SDP松弛、信号处理中的波束形成优化以及机器学习中的度量学习等领域。代

详 情 说 明

半正定规划(SDP)最优值求解器

本项目提供了一个在MATLAB环境下运行的鲁棒半正定规划求解器。该工具专门用于处理具有线性矩阵不等式（LMI）约束的凸优化问题，通过数值方法精确计算原始问题的最小值及其对偶问题的最大值。

项目核心功能

本项目实现了一个标准的对称中心路径跟踪内点法（Interior Point Method），具体功能包括：

1. 标准型问题定义：系统支持对原始形式 $min text{Tr}(CX)$ 且满足 $text{Tr}(A_i X) = b_i$ 和 $X succeq 0$ 的问题进行建模。
2. 随机可行性测试生成：内置自动化脚本可生成已知可行域的测试案例，通过构造确定的原可行解来确保数学模型的数学完备性。
3. 双重残差监测：在求解过程中实时跟踪原始残差和对偶残差，确保每一代更新都向可行域收敛。
4. 收敛过程可视化：自动生成收敛曲线图，直观展示对偶间隙（Duality Gap）与残差项随迭代次数的下降趋势。

系统实现逻辑

求解过程遵循高度结构化的数学逻辑，具体步骤如下：

• 初始化阶段：设定初始矩阵变量 $X$ 和 $S$ 为适当维度的单位矩阵倍数，将对偶变量 $y$ 初始化为零向量。
• 残差与中心化计算：在每次迭代中计算原始线性约束残差 $r_p$ 和对偶矩阵约束残差 $R_d$，利用对偶间隙计算中心化参数 $mu$。
• Schur补系统构建：这是求解器的核心计算单元。程序通过计算由 $M_{ij} = text{Tr}(A_i X A_j S^{-1})$ 组成的 $m times m$ 矩阵，构建用于求解牛顿方向的线性方程组。
• 方向计算与对称化：基于 HKM (Helmberg-Kojima-Monteiro) 方向求解牛顿搜索步长。计算出的原变量增量 $Delta X$ 会进行强制对称化处理，以抵消浮点运算带来的数值偏移。
• 步长缩放与安全性检查：通过广义特征值分析确定最大允许步长，确保变量在迭代后保持半正定性。

关键函数与算法细节

1. 内点法核心引擎：

采用原-对偶路径跟踪算法。该引擎通过预估-校正思想的简化版本，利用 Schur 补系统有效降低了高维矩阵运算的复杂度。特别是在处理 $Delta y$ 的解时，直接利用了矩阵的迹性质进行高效投影。

1. 最大步长计算 (max_step)：

该函数是保障算法稳定性的关键。它并不使用简单的比例缩减，而是通过求解 $Delta W$ 和 $W$ 的广义特征值来精确确定决策变量在边界处坍缩前的临界值，从而在保证正定性的前提下尽可能加速收敛。

1. 参数化迭代控制：

算法引入了目标缩减因子 $sigma$ 和步长保护因子 $gamma$，有效平衡了收敛速度与数值稳定性。

使用方法

1. 环境配置：只需拥有 MATLAB 运行环境，无需安装任何额外的工具箱（如 CVX 或 Sedumi），核心逻辑均由底层数学函数实现。
2. 参数调整：用户可以在逻辑代码前端通过修改矩阵维度 $n$ 和约束数量 $m$ 来测试不同规模的问题。
3. 自定义约束：通过修改目标矩阵 $C$ 和约束矩阵序列 $A_i$，用户可以将此求解器应用于波束形成、度量学习或协方差矩阵估计等特定工程场景。
4. 运行执行：运行主函数后，控制台将输出详细的目标值对比，并弹出显示收敛特性的图形界面。

系统要求

• MATLAB R2016b 或更高版本。
• 至少 8GB 内存（在处理大规模矩阵 $n > 100$ 时）。
• 标准计算能力，无需特殊 GPU 加速。