AN ELIGIBLE PRIMAL-DUAL INTERIOR-POINT METHOD FOR LINEAR OPTIMIZATION
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
It is well known that each kernel function defines a primal-dual interior-point method(IPM). Most of polynomial-time interior-point algorithms for linear optimization(LO) are based on the logarithmic kernel function. In this paper we define a new eligible kernel function and propose a new search direction and proximity function based on this function for LO problems. We show that the new algorithm has O((log p)\sqrt{n} log n log{n/\epsilon}) and O((q log p)^{3/2}\sqrt{n} log{n/\epsilon}) iteration bound for large- and small-update methods, respectively. These are currently the best known complexity results.
Abstract
It is well known that each kernel function defines a primal-dual interior-point method(IPM). Most of polynomial-time interior-point algorithms for linear optimization(LO) are based on the logarithmic kernel function. In this paper we define a new eligible kernel function and propose a new search direction and proximity function based on this function for LO problems. We show that the new algorithm has O((log p)\sqrt{n} log n log{n/\epsilon}) and O((q log p)^{3/2}\sqrt{n} log{n/\epsilon}) iteration bound for large- and small-update methods, respectively. These are currently the best known complexity results.
참고문헌 (11)
- M. Achache, "The application of a new class of parameterized kernel functions for mono- tone LCP", ~ (2013)
- E.D. Andersen, "Implementation of interior point methods for large scale linear programming, In Interior point methods of mathematical programming", pp.189~252 (1996), Kluwer Academic Publisher
- Y.Q. Bai, "A new ecient large-update primal-dual interior- point method based on a nite barrier", Siam J. on Optimization, 13, pp.766~782 (2003)
- Y.Q. Bai, "A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization", Siam J. on Optimization, 15, pp.101~128 (2004)
- Y.Q. Bai, "A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms", ANZIAM J, 49, pp.259~270 (2007)
- Y.Q. Bai, "Primal-dual interior point algorithms for second- order cone optimization based on kernel functions", Nonlinear Analysis, 70, pp.3584~3602 (2009)
- N.K. Karmarkar, "A new polynomial-time algorithm for linear programming", Combina- torica, 4, pp.373~395 (1984)
- M. Kojima, "A primal-dual interior-point algorithm for linear programming, In Progress in mathematical programming: Interior point and related methods", pp.29~47 (1989), Springer-Verlag
- J. Peng, "Self-Regularity, A new paradigm for primal-dual interior-point algorithms" (2002), Princeton University Press
- C. Roos, "Theory and algorithms for linear optimization, An interior approach" (1997), John Wiley & Sons
- N.J. Todd, "Recent developments and new directions in linear programming, In Mathematical Programming : Recent developments and applica- tions", pp.109~157 (1989), Kluwer Academic Publishers