对称锥规划的内点算法及在信息科学中的应用

Since the interior-point method (IPM, for short) is one of the most effective methods for symmetric cone programming and is widely used in reactive power flow optimization in power systems, the signal processing in communications, venture capital in the financial world and the most effective choice of portfolio and so on, the seeking effective IPM has important significance in theory and extensive application value. At present, study on IPM for symmetric cone programming mainly focuses on two aspects: improving the numerical effect of narrow neighborhood IPM and reducing the complexity of wide neighborhood IPM. However, the numerical effect of narrow neighborhood IPM is worse than wide neighborhood IPM, this project will study wide neighborhood inexact IPM for symmetric cone programming and the application in information sciences. To achieve this, we adopt three approaches, one is to search new wide neighborhood and to design wide neighborhood IPM with low complexity and good practice effects. The other is to combine the iterative method of linear equations and infeasible-IPMs and to design inexact IPM. A third is to establish the symmetric cone programming model of some important practical problems in information sciences.

内点算法是求解对称锥规划的有效方法之一，并被广泛的应用于求解电力系统无功优化问题、通讯领域的信号处理问题、金融领域的风险投资以及证券组合的有效选择问题等，所以寻求高效的内点算法具有重要的理论意义和广泛的应用价值。目前，对称锥规划的内点算法研究主要集中在改进窄邻域算法的数值效果及降低宽邻域算法的复杂性两个方面。然而，窄邻域算法的实际计算效果很难与宽邻域算法相媲美，所以，本项目将重点研究对称锥规划的宽邻域非精确内点算法及在信息科学中的应用。为此，我们采用了三种解决途径，其一是寻找新的宽邻域，并依此为基础设计数值效果好、复杂性低的宽邻域内点算法；其二是将线性方程的迭代求解法与不可行内点算法相结合，设计非精确内点算法；其三是将信息科学中的重要实际问题建模为对称锥规划模型，并用设计的新算法来处理它。

本项目在国家自然科学基金（No.11501180）的资助下，重点研究了对称锥规划的宽邻域非精确内点算法及在信息科学中的应用。主要研究成果如下：..1) 通过改变迭代方式，来降低已有宽邻域算法的复杂度。在该方面，我们研究了两类重要方法。其一，使用了弧搜索的方式代替了传统的线搜索方式，改变了算法的复杂度，并获得了不错的数值效果。其二，通过同解方程，使用一个核函数来代替传统的牛顿方程，这样也改变了迭代方向，可以起到改进算法的复杂度的效果。..2) 通过高阶矫正技术， 来降低已有宽邻域算法的复杂度。在该方面，我们重点研究了二阶矫正算法，该算法不但具有高阶矫正算法的优点，而且方便分析复杂度和编写程序。..3) 寻找新的宽邻域，并以此为基础设计宽邻域算法。 我们阅读了大量的相关文献，进行了多种尝试，并成功的使用1-范数代替了F-范数，最后设计出了1-范数宽邻域。在该方面，我们以1-范数宽邻域为基础，以Mizuno-Todd-Ye预估矫正算法为载体，设计了一个新的宽邻域不可行的内点算法，该算法具有复杂度低，数值效果好的特点。..4) 时刻关注对称锥规划的可交换类方向的最新研究成果，为深入研究非精确不可行内点算法打好基础。另外，我们重点研究了对称锥规划在纠错编码、传感器网络定位、信号处理、电力系统、蛋白质分类等中的应用。. .依托本项目， 课题组发表或录用相关论文9篇，其中SCI收录6 篇，EI收录1 篇，其余发表在国家核心期刊上。