• 论文 •

### 一类非单调线性互补问题的高阶仿射尺度算法

1. 三峡大学理学院,武汉大学数学与统计学院 宜昌,443002 ,武汉, 430072
• 出版日期:2004-01-14 发布日期:2004-01-14

### A HIGH-ORDER AFFINE SCALING ALGORITHM FOR A CLASS OF NONMONOTONIC LINEAR COMPLEMENTARY PROBLEMS

1. Zhang Mingwang Huang Chongchao (College of Science, Three Gorges University, Yichang, 443000; School of Mathematics and Statistics, Wuhan University, Wuhan, 430072)
• Online:2004-01-14 Published:2004-01-14
1.引言 自从1984年著名的Karmarkar算法发表以来,由其理论上的多项式收敛性及实际计算的有效性,使得内点算法成为近十几年来研究的热点.大量线性规划、二次规划及单调线性互补问题的内点算法被提出,其收敛性被讨论.在已有的内点算法中,最具代表性的算法有三类:势函数投影变换方法、仿射尺度算法和路径跟踪法.各类算法向凸规划问题、非
In this paper, a new interior point algorithm-high-order affine scaling for a class of nonmonotonic linear complementary problems is developed . On the basis of idea of primal-dual affine scaling method for linear programming , the search direction of our algorithm is obtained by a linear system of equation at each step . We show that, by appropriately choosing the step size, the algorithm has polynomial time complexity. We also give the numberical results of the algorithm for two test problems.
()
 [1] N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984) , 373-395． [2] Y. Ye, Interior Point Algorithm-Theory and Analysis, John Wiley and Sons, New York, 1997． [3] R.D.C. Monteiro and I. Alder, An extension of karmarkar type algorithm to a class of convex separable programming problem with global linear rate of convergence, Mathematics of Operations Research, 15 (1990) , 408-422． [4] K.O. Kortanek and Jian Thu, A polynomial barrier algorithm for linearly constrained convex programming problem, Mathematics of Operations Research, 18 (1993) , 116-127． [5] E.D. Andersen, Y. Ye. On homogeneous algorithm for the monotone complementary problem, Mathematical Programming, 84 (1999) , 375-399． [6] R.D.C. Monteiro. Prime-dual path-following algorithm for semidefinite programming, SIAM Journal on Optimization, 3 (1997) , 663-678． [7] M. Kojima, N. Megiddo and Y. Ye, An interior-point potential reduction algorithm for the linear complementary problem, Mathematical Programming, 54 (1992) , 267-279． [8] He Shanglu, Xu Chengxian, A path-following method for a class of nonmonotonic linear complementary problems and its computational complexity, Mathematica Numerica Sinica, 23:3 (2001) , 299-306． [9] R.D.C. Monteiro, I. Alder and M.C.C. Resende, A polymomial-time primal-dual affine scaling algorithm for linear and convex quadrtic programming and its power series extension, Mathematics of Operations Research, 15 (1990) , 191-214． [10] G. Thao and J. Sun, On the rate of local convergence of high-order infeasible path followingalgorithm, Computational Optimization and Applications, 14:3 (1999) , 293-307． [11] K.G. Murty, Linear complementary, linear and nonlinear programming, Helderman, Berlin,1988． [12] Sun Defeng, A iterative method for solving variational inequality problems and complementarity problems, Numerical Mathematics (A Journal of Chinese Universities), 16:2 (1994) , 145-453．
 No related articles found!