Numerical Methods for Large Scale Semidefinite Programming

在这个研究项目中，我们开发了用于求解大规模半确定规划的SDPA（半确定规划算法）。SDPA的主要特点是：(a) SDPA是用c++编写的。(b) SDPA采用mebrotra型预测校正步进，节省了迭代次数，提高了数值稳定性。(c)除HRVW/KSH/M搜索方向外，用户还可选择who搜索方向和NT搜索方向。(d) SDPA利用Meschach增加数值稳定性。(e) SDPA提供了关于待解决的半确定方案的不可行性的一些资料。(f) SDPA不仅处理块对角矩阵，而且处理稀疏矩阵数据结构。当待解的SDP规模较大且稀疏时，可以有效地利用这种稀疏矩阵数据结构来提高计算效率和节省内存。我们将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.