基于局部self-concordant障碍函数的全牛顿步多项式时间算法

摘要

由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.%The theory of self-concordant barriers developed by Nesterov and Ne-mirovski [4] provides an algorithm with polynomial complexity applicable to linear and convex optimization problem.The parameters of a self-concordant barrier function can be used to compute the complexity bound of the algorithm considered.In this paper we present a local self-concordant barrier function based on a kernel function in the neigh-borhood of the central path of linear optimization problem.We derive the local values of parameters of this barrier function and obtain the complexity bound of a full-Newton step interior-point algorithm based on this local self-concordant function for linear opti-mization problem.The bound matches the best known existing complexity bounds.