Polynomial-time interior-point algorithm based on a local self-concordant finite barrier function |
| |
| Authors: | Zheng-jing Jin Yan-qin Bai |
| |
| Institution: | 1. College of Sciences,Shanghai University,Shanghai 200444,P.R.China;College of Sciences,Zhejiang Forestry University,Lin'an 311300,Zhejiang,P.R.China
2. College of Sciences,Shanghai University,Shanghai 200444,P.R.China |
| |
| Abstract: | The choice of self-concordant functions is the key to efficient algorithms for linear and quadratic convex optimizations,
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 small-update methods.
Project supported by the National Natural Science Foundation of China (Grant No.10771133), the Shanghai Leading Academic Discipline
Project (Grant No.S30101), and the Research Foundation for the Doctoral Program of Higher Education (Grant No.200802800010) |
| |
| Keywords: | linear optimization self-concordant function finite barrier interior-point methods polynomial-time complexity |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
| 点击此处可从《上海大学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《上海大学学报(英文版)》下载免费的PDF全文 |
|
