A New Kernel Function Yielding the Best Known Iteration Bounds for Primal-Dual Interior-Point Algorithms
A New Kernel Function Yielding the Best Known Iteration Bounds for Primal-Dual Interior-Point Algorithms作者机构:Department of Mathematics Shanghai University Shanghai 200436 P. R. China Business School University of Shanghai for Science and Technology Shanghai 200093 P. R. China Faculty of Electrical Engineering Mathematics and Computer Science Delft University of Technology P.O. Box 5031 2600 GA Delft The Netherlands
出 版 物:《Acta Mathematica Sinica,English Series》 (数学学报(英文版))
年 卷 期:2009年第25卷第12期
页 面:2169-2178页
核心收录:
学科分类:07[理学] 08[工学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:Supported by National Natural Science Foundation of China (Grant Nos.10771133 and 70871082) Shanghai Leading Academic Discipline Project (Grant No.S30104)
主 题:linear optimization interior-point method primal-dual method large-update method polynomial complexity
摘 要:Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.