运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2008年
1期
1-15
,共15页
运筹学%线性规划%障碍函数%self-concordant函数%内点算法%多项式时间算法
運籌學%線性規劃%障礙函數%self-concordant函數%內點算法%多項式時間算法
운주학%선성규화%장애함수%self-concordant함수%내점산법%다항식시간산법
Operations research%linear optimization%barrier function%self-concordant function%interior-point methods%polynomial-time complexity
由Nesterov和Nemirovski[4]创立的self-concordant障碍函数理论为解线性和凸优化问题提供了多项式时间内点算法.根据self-concordant障碍函数的参数,就可以分析内点算法的复杂性.在这篇文章中,我们介绍了基于核函数的局部self-concordant障碍函数,它在线性优化问题的中心路径及其邻域内满足self-concordant性质.通过求解此障碍函数的局部参数值,我们得到了求解线性规划问题的基于此局部Self-concordant障碍函数的纯牛顿步内点算法的理论迭代界.此迭代界与目前已知的最好的理论迭代界是一致的.
由Nesterov和Nemirovski[4]創立的self-concordant障礙函數理論為解線性和凸優化問題提供瞭多項式時間內點算法.根據self-concordant障礙函數的參數,就可以分析內點算法的複雜性.在這篇文章中,我們介紹瞭基于覈函數的跼部self-concordant障礙函數,它在線性優化問題的中心路徑及其鄰域內滿足self-concordant性質.通過求解此障礙函數的跼部參數值,我們得到瞭求解線性規劃問題的基于此跼部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.
