Numerical Methods for Large Scale Semidefinite Programming

在本研究项目中，我们开发了求解大规模半定规划的半定规划算法SDPA。SDPA的主要特点是：(A)SDPA是用C语言编写的。(B)SDPA采用了Mebrotra型预测-校正步骤，这有助于节省迭代次数和增加数值稳定性。(C)除了HRVW/KSH/M搜索方向外，AHO搜索方向和NT搜索方向可由用户选择。(D)SDPA利用Meschach提高数值稳定性。(E)SDPA提供了一些关于半定程序不可行的信息。(F)SDPA不仅处理块对角矩阵，还处理稀疏矩阵数据结构。将该稀疏矩阵数据结构应用于非凸二次规划问题的半定规划松弛、双线性矩阵不等式等问题，并通过大量的计算实验验证了其计算效率。

In this research project, we developed the SDPA (SemiDefinite Programming Algorithm) for solving large scale semidefinite programs. The main features of the SDPA are :(a) The SDPA is written in C++.(b) The SDPA incorporates the Mebrotra-type predictor-corrector step, which contributes to saving the number of iterations and to increasing the numerical stability.(c) Besides the HRVW/KSH/M search direction the AHO search direction and the NT search direction are available at the user's option.(d) The SDPA utilizes the Meschach to increase the numerical stability.(e) The SDPA provides some information on infeasibility of a semidefinite program to be solved.(f) The SDPA handles not only block diagonal matrices but also sparse matrix data structure. When an SDP to be solved is large scale and sparse, this sparse matrix data structure is effectively utilized in increasing the computational efficiency and saving the memory.We applied the SDPA to various problems such as the semidefinite programming relaxation of nonconvex quadratic programming problems and bilinear matrix inequalities, and confirmed its computational efficiency through numerious computational experiments.