|
| 摘要: |
| 本文研究了P*(k)线性互补问题的大步校正原始-对偶内点算法.基于一个强凸且不同于通常的对数函数和自正则函数的新核函数,对具有严格可行初始点的该问题,算法获得的迭代复杂性为O((1+2k)√n(log n)2 log (n)/(ε),该结果缩小了大步校正内点算法的实际计算与理论复杂性界之间的差距. |
| 关键词: 线性互补问题 核函数 大步校正方法 多项式复杂性 |
| DOI： |
| 分类号:O221.2 |
| 基金项目:Supported by National Natural Science Foundation of China (61273183). |
|
| LARGE-UPDATE METHOD FOR P*(k) LINEARCOMPLEMENTARITY PROBLEMS BASED ON ANEW KERNEL FUNCTION |
|
CHEN Dong-hai,ZHANG Ming-wang
|
| Abstract: |
| A large-update primal-dual interior-point method for P*(k) linear complementarity problems is presented in this paper. Based on a new kernel function which is strongly convex and difiers from the usual logarithmic or self-regular function, we show that if a strictly feasible starting point is available, the new method for P*(k) linear complementarity problems has the polynomial complexity O((1 + 2k)√n(log n)2 log (n)/(ε), which reduced the gap between the practical behavior of the large-update method and its theoretical performance results. |
| Key words: linear complementarity problem kernel function large-update method polynomial complexity |
