对称锥宽邻域内点算法研究.ppt

对称锥的宽邻域内点算法研究,杨喜美 2014-4-15,目录,Part 1 作品简介 Part 2 作品创新点,从题目我们可以看出，我们解决的问题是对称锥规划问题，我们使用的工具是内点算法。,问题1：什么是对称锥规划问题？ 问题2：什么是内点算法？,对称锥规划问题,对称锥规划问题是指带有对称锥约束的优化问题，其目标函数为线性函数，约束条件为仿射空间和闭凸锥的交集。其标准形式，如下：,对称锥规划问题的常见子类,包括三类常见的规划问题 当 时，线性规划 当 时，半定规划 当 时，二阶锥规划,研究意义：,研究对称锥规划问题可以为求解三类特殊的规划问题以及非线性最优化问题提供统一框架，能够使我们更好的理解三类特殊规划问题的本质特性；因此，它是一类内容新、涵盖面宽、理论丰富、学术价值高的优化问题。另外，它在经济、管理、交通、控制和信息等学科中有广泛的应用，所以，吸引了众多优化专家、学者从不同的角度致力于对称锥优化问题的研究。,内点算法,1984年 ，Karmarka为求解线性规划而提出的。由于该算法具有多项式复杂度被受关注。它成为了求解线性规划、线性互补问题的一类十分有效的算法. 1988年 ，Nesterov和Nemirovskii将其推广到半定规划，这表明内点算法的适用范围有了实质性的变化。 Nesterov和Todd提出self-scaled锥的第一个多项式时间原-对偶短步路径跟踪算法。Gler证明了self-scaled锥即是对称锥。Faybusovich为推广原-对偶内点算法到对称锥上做了基础性工作。 至此，内点算法求解对称锥规划问题才引起重视，并一直是研究的热门课题。,研究目标 窄邻域算法具有较低的理论复杂度，但是实践性较差； 宽邻域算法实践性较好，但是理论复杂度高； 我们的研究目标就是设计出兼有两者优点的内点算法。,作品创新点,把Ai-Zhang邻域推广到对称锥上，设计了一个不可行的宽邻域路径跟踪算法 提出自己的宽邻域，使用提出的宽邻域设计了一个不可行的Mehrotra-型预估-矫正内点算法 为了改善宽邻域算法的实践性我们也设计了一个二阶矫正算法 为改善算法的有效性，设计了一个弧搜索内点算法，该算法工作在常用的大邻域，负无穷邻域内。,所做的工作,已获得的成果,1 Ximei Yang, Hongwei Liu, Xiaoliang Dong. Polynomial convergence of Mehrotra-type predictioncorrector infeasible-IPM for symmetric optimization based on the commutative class directions. Applied Mathematics and Computation(AMC). Volume 230, 1 March 2014, Pages 616628. (SCI,二区, IF1.454,已检索,引用次数0) 2 Ximei Yang, Hongwei Liu, Yinkui Zhang. A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighborhood for semi-definite programming. International Journal of Computer Mathematics(IJCM). DOI:10.1080/00207160.2013.827784. (SCI,四区,IF 0.542,未检索，引用次数0) 3 Hongwei Liu, Ximei Yang, Changhe Liu. A New Wide Neighborhood Infeasible-Interior-Point Method for Symmetric Cone Programming. Journal of Optimization Theory and Applications(JOTA). September 2013, Volum158, Issue 3, pp 796-815. (SCI, 三区,IF 1.423,已检索,引用次数1) 4 Hongwei Liu, Changhe Liu,Ximei Yang. New complexity analysis of a Mehrotra-type predictorcorrector algorithm for semidefinite programming. Optimization Methods and