.png){kind=icon}
返回
Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2005.09.079.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Interior point methods have shown their powers in solving linear optimization problems and large classes of other optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst case complexity. The so-called large update interior point methods perform in practice much better than the small update methods which have the best known theoretical complexity. Recently, this gap has been reduced by Peng, Roos and Terlaky by introducing new self regular kernel functions. In this paper, by focusing on linear optimization problem and motivated by the self regular family of kernel functions, we impose some mild condition on the kernel functions and we give a new class of kernel functions. We also give a simple complexity analysis for large-update interior point methods based on the kernel functions in this new class. Finally, we apply our analysis to two family of kernel functions in our new class. We also explore the complexity of the algorithm and we show that the so far worst case O(root n log n log n/is an element of) iteration bound can be achieved in special case. (c) 2005 Elsevier Inc. All rights reserved.
Keyword:
linear optimization
primal-dual interior point method
kernel function
proximity function
large update method
polynomial complexity
期刊
IF:
3.4
论文数:
2.3W
被引数:
3.3W
机构
暂无机构信息
.png){kind=icon}
