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

A Full-Newton Step Polynomial-time Algorithm Based on a Local Self-concordant Barrier Function for Linear Optimization

由Nesterov和Nemirovski^([4])创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.

The theory of self-concordant barriers developed by Nesterov and Nemirovski [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 neighborhood 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 optimization problem. The bound matches the best known existing complexity bounds.