New complexity analysis of primal-dual IMPS for P_(*) LAPS based on large updates
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper we present new large-update primal-dual interior point algorithms for P_(*) linear complementarity problems(LAPS) based on a class of kernel functions, ψ(t) = [{t^(p+1)−1}/p+1] + 1/σ [e^{σ(1−t}) − 1], p∈ [0, 1],σ> 1. It is the first to use this class of kernel functions in the complexity analysis of interior point method(IPM) for P¤ LAPS. We showed that if a strictly feasible starting point is available, then new large-update primal-dual interior point algorithms for P_(*) LAPS have O{(1 + 2·k)n^(1/p+1) log n log n/ε} complexity bound. When p = 1, we have O((1+2·k)n^(1/2) log n log n/ε ) complexity which is so far the best known complexity for large-update methods.
Abstract
In this paper we present new large-update primal-dual interior point algorithms for P_(*) linear complementarity problems(LAPS) based on a class of kernel functions, ψ(t) = [{t^(p+1)−1}/p+1] + 1/σ [e^{σ(1−t}) − 1], p∈ [0, 1],σ> 1. It is the first to use this class of kernel functions in the complexity analysis of interior point method(IPM) for P¤ LAPS. We showed that if a strictly feasible starting point is available, then new large-update primal-dual interior point algorithms for P_(*) LAPS have O{(1 + 2·k)n^(1/p+1) log n log n/ε} complexity bound. When p = 1, we have O((1+2·k)n^(1/2) log n log n/ε ) complexity which is so far the best known complexity for large-update methods.
참고문헌 (14)
- Y. Q. Bai, "A new efficient large-update primal-dual interiorpoint method based on a finite barrier", SIAM J. Optim, 13(3), pp.766~782 (2002)
- Y. Q. Bai, "A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization", SIAM J. Optim., 15(1), pp.101~128 (2004)
- G. M. Cho, "Complexity of large-update interior point algorithm for P¤(·) linear complementarity problems", Comput. Math. Appl, 53(6), pp.948~960 (2007)
- M. El Ghami, "A polynomial-time algorithm for linear optimization based on a new class of kernel functions", Journal of Computational and Applied Mathematics (2008)
- T. Illes, "A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complementarity problems", European J. Oper. Res., 181(3), pp.1097~1111 (2007)
- M. Kojima, "A primal-dual interior point algorithm for linear programming, Progress in mathematical programming", pp.29~47 (1989), Springer
- M. Kojima, "A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science", pp.538~ (1991), Springer-Verlag
- M. Kojima, "A polynomial-time algorithm for a class of linear complementarity problems", Math. Programming, 44(1), pp.1~26 (1989)
- M. Kojima,, "An O(pnL) iteration potential reduction algorithm for linear complementarity problems", Math. Programming, 50(3), pp.331~342 (1991)
- N. Megiddo, "Pathways to the optimal set in linear programming, Progress in mathematical programming", pp.131~158 (1989), Springer
- J. Miao, "A quadratically convergent O((· + 1)pnL)-iteration algorithm for the P¤(·)-matrix linear complementarity problem", Math. Programming, 69(3), pp.355~368 (1995)
- J. Peng, "Self-regular functions and new search directions for linear and semidefinite optimization", Math. Program, 93(1), pp.129~171 (2002)
- C. Roos, "Theory and Algorithms for Linear Optimization, An interior point approach. Wiley-Interscience Series in Discrete Mathematics and Optimization" (1997), John Wiley & Sons
- U. Sch¨afer, "A linear complementarity problem with a P-matrix", SIAM Rev, 46(2), pp.189~201 (2004)