NEW PRIMAL-DUAL INTERIOR POINT METHODS FOR P*(κ) LINEAR COMPLEMENTARITY PROBLEMS
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper we propose new primal-dual interior point methods (IPMs) for P*(κ) linear complementarity problems (LCPs) and analyze the iteration complexity of the algorithm. New search directions and proximity measures are defined based on a class of kernel functions,[수식] If a strictly feasible starting point is available and the parameter [수식] where [수식], then new large-update primal-dual interior point algorithms have [수식] iteration complexity which is the best known result for this method. For small-update methods, we have [수식] iteration complexity.
Abstract
In this paper we propose new primal-dual interior point methods (IPMs) for P*(κ) linear complementarity problems (LCPs) and analyze the iteration complexity of the algorithm. New search directions and proximity measures are defined based on a class of kernel functions,[수식] If a strictly feasible starting point is available and the parameter [수식] where [수식], then new large-update primal-dual interior point algorithms have [수식] iteration complexity which is the best known result for this method. For small-update methods, we have [수식] iteration complexity.
참고문헌 (15)
- 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)
- Y. Q. Bai, "A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms", Acta Math. Sin. (Engl. Ser.), 25(12), pp.2169~2178 (2009)
- G. M. Cho, "Complexity of large-update interior point algorithm for P＊(·) linear complementarity problems", Comput. Math. Appl., 53(6), pp.948~960 (2007)
- T. Ill´es, "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 Unified Approach to Interior Point Algorithms for Linear Complementarity Problems", Lecture Notes in Computer Science, 통권 : 538 (1991), Springer-Verlag
- M. Kojima, "A primal-dual interior point algorithm for linear programming, Progress in mathematical programming (Pacific Grove, CA, 1987)", pp.29~47 (1989), Springer
- 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), Ser. A
- N. Megiddo, "Pathways to the optimal set in linear programming, Progress in mathematical programming (Pacific Grove, CA, 1987)", 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), Ser. A
- J. Peng, "A new and efficient large-update interior-point method for linear optimization", Vychisl. Tekhnol., 6(4), pp.61~80 (2001)
- J. Peng, "Self-regular functions and new search directions for linear and semidefinite optimization", Math. Program., 93(1), pp.129~171 (2002), Ser. A
- C. Roos, "Theory and Algorithms for Linear Optimization, An interior point approach. Wiley-Interscience Series in Discrete Mathematics and Optimization" (1997), John Wiley & Sons, Ltd.
- U. Sch¨afer, "A linear complementarity problem with a P-matrix", SIAM Rev., 46(2), pp.189~201 (2004)
- S. J. Wright, "Primal-Dual Interior-Point Methods" (1997), Society for Industrial and Applied Mathematics