Algorithms for Optimization Problems and Systems of Bilinear Equations over Positive Definite Symmetric Matrices and its Applicatoins

正定对称锥集上的优化问题和双线性方程组的典型例子是半定规划（SDP）和由SDP产生的双线性方程组。在本研究中，我们还研究了线性规划（LP）和二阶锥规划（SOCP）作为SDP的特殊情况。我们继续研究的课题是：（1）SDP的原-对偶邻域点算法的多项式性分析;（2）SOCP的原-对偶邻域点算法的多项式性分析;（3）LP的仿射尺度算法的全局收敛性的反例构造。我们在项目期间发表了三篇关于这些主题的论文。本课题还研究了以下四个新课题：（4）SDP在图形模型估计中的应用;（5）SOCP在直线电机车磁屏蔽优化设计中的应用（6）对求解线性规划问题的Vavasis-Ye多项式时间收敛点算法的改进，该算法的复杂性仅取决于系数矩阵A ;（7）利用JB代数推广了多项式时间原-对偶邻域点算法，使之能求解高维问题。我们还实现了LP的对偶仿射尺度算法和SDP的原始-对偶路径跟踪算法，并尝试解决标准基准问题。

Typical examples of optimization problems and systems of bilinear equations over the set of positive definite symmetic cones are semidefinite programming (SDP) and the systems bilinear equations arising from SDP. In this research, we also studied linear programming (LP) and second-order cone programming (SOCP) as special cases of SDP. The topics we continued to study from the past and related to the project is : (1) Polynomi-ality analysis of primal-dual interior-point algorithms for SDP ; (2) Polynomiality analysis of primal-dual interior-point algorithms for SOCP ; (3) Costruction of a counter example of global convergence of, the affine-scaling algorithm for LP. We published three papers on these topics in the term of the project. There are the following four other new topics we studied in the project : (4) Application of SDP to estimation of graphical models ; (5) Application of SOCP to optimal design of magnetic shielding in linear motor car (new bullet train) ; (6) Modification of the Vavasis-Ye polynomial-time interior-point algorithm for linear programming whose complexity just depends on the coeflicient matrix A ; (7) Extension of polynomial-time primal-dual interior-point, algorithms to inflnite, , dimensional problems using JB algebras. We also implemented the dual affine-scaling algorithm for LP and the primal-dual path-following algorithms for SDP, and made attempt, s to solve standard benchmark problems.