Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function

摘要

The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimiza-tions,which provide a method with polynomial-time iterations to solve linear and quadratic convex optimization problems.The parameters of a self-concordant barrier function can be used to compute the complexity bound of the proposed algorithm.In this paper,it is proved that the finite barrier function is a local self-concordant barrier function.By deriving the local values of parameters of this barrier function,the desired complexity bound of an interior-point algorithm based on this local self-concordant function for linear optimization problem is obtained.The bound matches the best known bound for smallupdate methods.