二阶锥规划的基于若当代数结构的内点算法研究

As the basic of symmetric optimization, second order cone optimization has many important implications in engineering, control and financial, such as the robust optimization and combinational optimization and so on. Further, second order cone optimization has explicit problem structure and rich dual theory. It also can be solved by interior point methods in polynomial time complexity. For other aspects, semidefinite optimization can be solved easily by transforming into second order cone optimization..The study on the infeasible interior point methods improves the development of symmetric optimization in recent years. The infeasible interior point methods has polynomial time complexity bound and overcome the difficulty of finding a feasible initial point, which plays an important role for solving large scale symmetric optimization..We first study the interior point methods and infeasible interior point methods of second order cone optimization and then extend them to symmetric optimization. We use the Euclidean Jordan algebraic approach to design new algorithm and analyze the algorithm to improve the complexity bound.

作为最基础的对称锥优化问题，二阶锥规划有许多重要的应用，例如，在工程、控制和金融等领域(如鲁棒优化和组合优化)有广泛应用。此外，二阶锥规划具有明确的结构特征和对偶理论，有多项式时间内点算法来求解。因为二阶锥规划具备这些特点，一些半正定规划也可以通过模型转化或松弛，借助于二阶锥规划这一工具来求解。.近年来，对不可行内点算法的研究促进了锥优化的发展。不可行内点算法能够克服内点算法需要寻找一个可行初始内点的困难，同时也具有多项式时间算法，这对求解大规模的锥规划有非常重要的推动作用。.针对对称锥规划，我们从研究二阶锥规划的理论和算法入手，通过分析二阶锥规划自有的结构特征，利用欧几里得若当代数知识，来设计新的内点算法以及不可行内点算法。我们将改进算法和引入新的分析技术，并进行数值模拟。最后将研究结果推广到对称锥规划。

自从2006年Nemirovski在世界数学家大会一小时报告介绍锥优化的理论和算法以来，锥优化成为研究者十分关注的研究领域。由于二阶锥规划近年来广泛应用于机器学习，图像处理，分类问题，鲁棒优化，投资组合等实际应用问题以及使用来降维处理半正定矩阵锥优化问题，使得二阶锥规划成为研究者特别关注的研究领域。在求解二阶锥规划的算法中，基于若尔当代数的不可行内点算法是求解这类问题非常有效的多项式时间算法。. 本项目主要研究三个方面的内容：（1）进一步挖掘二阶锥在若尔当代数下的结构特征；（2）基于二阶锥的代数结构设计求解二阶锥规划的不可行内点算法；（3）探讨二阶锥规划在实际问题中的应用。对于问题（1）二阶锥的若尔当代数我们发现研究者已经研究的非常透彻，很难有新的突破；对于问题（2）基于二阶锥的代数结构设计内点算法，主要研究了Chubanov's多项式时间算法到二阶锥的扩展及改进和以及一些新的带参数的障碍函数在内点算法中的应用，项目目前正在进展中；对于问题（3）目前正在探究二阶锥在支持向量机中的应用。. 项目的研究一方面具有理论价值，是对数值性能良好的内点算法的进一步研究，具有理论价值；另外一方面，项目算法的研究具有应用价值，研究的算法能够使用来求解实际应用问题，具有实际意义。