EXPECTED NUMBER OF ITERATIONS OF INTERIOR-POINT ALGORITHMS FOR LINEAR PROGRAMMING
摘要
We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of theseTodd's probabilisticalgorithms is bounded above by O(n^1.5). The random LP problem is model with the Cauchy distribution.
参考文献11
-
1Anstreicher, K M , Ji, J , Potra, P A , & Ye, Y , Probabilistic Analysis of an Infeasible Primal-dual Algorithm for Linear Programming, Mathematics of Operations Research 1, (1999), 176-192.
-
2Girko, V L , On the distribution of solutions of systems of linear equations with random coefficients,Theor. Probability and Math. Statist. 27 (1974), 41-44.
-
3Huang, S , Average number of iterations of interior-point algorithms for linear programming, Science in China (A), Vol. 43(8), 829-835.
-
4Karmarkar, N , A newp01ynomial time algorithm for linear programming, Cornbinatorica 4, (1984),373-395.
-
5Kojima, M , Mizuno, S & Yoshise, A , An O(√nL) iteration potential reduction algorithm forlinear complementarity problems, Mathematical Programming 50, (1991), 331-342.
-
6Lustig, I J , R E Marsten and D F Shanon, "The primal-dual interior point method on the Crays upercomputer," In T F Coleman and Y Li, editors, Large-scale Numerical Optimization, pages 70-80, SIAM, 1990.
-
7Mehrotra, S & Ye, Y , Finding an interior point in the optimal face of linear programs, Mathematical Programming 62, (1993), 497-516.
-
8Potra, F A , An infeasible interior-point predictor-corrector algorithm for linear programming,SIAM J. Optim. 6, (1996), 19-32.
-
9Todd, M J , Probabilistic models for linear programming, Mathematics of Operations Research 16,(1991), 671-693.
-
10Yang, G. and S. Huang, Solving the bank asset and liability management model via an interior point algorithm, Lecture Notes in Decision Sciences, Vol. 2, Financial Systems Engineering, Global Link Publisher, Hong Kong, p. 530-544.
-
1黄思明.Average number of iterations of some polynomial interior-point——Algorithms for linear programming[J].Science China Mathematics,2000,43(8):829-835.
-
2WangYan-jin,FeiPu-sheng,YanZi-zong.A Potential-Reduction Algorithm for Linear Complementarity Problems[J].Wuhan University Journal of Natural Sciences,2004,9(2):144-148.
-
3Yan-liang CHEN,Mao-zai TIAN,Ke-ming YU,Jian-xin PAN.Composite Hierachical Linear Quantile Regression[J].Acta Mathematicae Applicatae Sinica,2014,30(1):49-64.
