DSDP
介绍
DSDP 是一款针对稀疏半正定规划问题的开源求解器，其开发者为 Steve Benson, Yinyu Ye, 与 Xiong Zhang。DSDP 内部实现了高效的 Dual-Scaling 内点算法，相比于其他种类的内点算法能够更好地利用问题的稀疏性以及低秩结构，同时在内存使用上更为友好，在半正定规划问题的求解效率上处于世界前列。目前 DSDP 的最新版本支持半正定与线性规划混合问题的求解，并被广泛地运用于线性矩阵不等式 （LMI） 求解、模型控制，拓扑结构设计及组合优化的松弛问题求解中。
参数
DSDP 包含如下日志与算法参数
求解日志
| 参数名 <默认值> | 类型 | 参数含义 |
|---|---|---|
| print <10> | 整型 | 每 k 次迭代输出日志 |
| dloginfo <0> | 整型 | 超过该迭代数后输出日志 |
| dlogsummary <1> | 整型 | 输出时间日志 |
| help | 无 | 输出参数帮助信息 |
算法参数
| 参数名 <默认值> | 类型 | 参数含义 |
|---|---|---|
| timelimit <15000> | 浮点型 | 算法时间限制 |
| gaptol <1e-6> | 整型 | 在相对对偶间隙小于该值时结束 |
| r0 <-1> | 浮点型 | 取非负值时用单位矩阵乘该值以初始化对偶变量 S |
| penalty <1e10> | 浮点型 | 对偶不可行性惩罚参数 |
| boundy <1e7> | 浮点型 | 对偶变量 y 的上下界参数 |
| maxit <200> | 整型 | 最大迭代次数 |
| zbar <1e10> | 浮点型 | 对偶目标函数值上界参数 |
| mu0 <-1> | 浮点型 | 取非负值时初始化障碍函数参数 |
| rho <3> | 浮点型 | 势函数参数 |
| drho <1> | 浮点型 | 使用动态势函数参数策略 |
| pnormtol <1e30> | 浮点型 | 确保对偶邻近范数小于该值 |
| reuse <4> | 整型 | 重复利用 Schur 矩阵次数 |
| bigM <0> | 浮点型 | 取正值时，不强制消除而是使用 Big-M 法惩罚对偶不可行性 |
使用示例
DSDP 目前可以通过 C 语言子例程库直接调用，同时也支持求解 SDPA 格式的问题，例如在通过编译获取 DSDP 的二进制可执行文件后，可以通过
readsdpa filename.dat-s
1
命令调用求解器进行求解。