双步长内点算法中一个子问题的研究
|
摘要
“互补问题”作为一类新的数学模型,是1964年美国R.W.Cottle在其博士学位论文“Nonlinear Programs with Positively BoundedJacobians”中提出的。这一数学问题在初期曾被称为“拼合问题”、“基本问题”或“互补转轴问题”等。而第一个具有多项式复杂性和实用性的线性规划的内点算法是由Karmarkar于1984年首先提出的。此后20年,经过众多优化专家的共同努力,对内点法的研究取得了丰硕成果。由于线性规划只是互补问题的一个特例,所以内点法被推广到求解某些互补问题。
本文的目的就是对单调线形互补问题的一类新的原始对偶路径跟踪内点算法中所涉及的双步长问题进行分析。新算法中的双步长方法把经典的牛顿方向看作另外两个方向的和。并对这二个方向采用不同的步长大小,分别记为a_1和a_2。本文首先介绍新算法及两个步长的性质和对新算法迭代的影响。之后,根据步长的性质列出求解步长的两种方法,再用Matlab将两种算法编写成两个程序。最后,在对大量数值结果分析的基础上得出,把a_2固定为1,对a_1用二分法进行搜索的方法是可行的。
R.W.Cottle proposed the "Complimentarity problem" in his PhD degree paper "Nonlinear Programs with Positively Bounded Jacobians"in 1964. This problem was first referred to as "composite problem", "fundamental problem" or "complementarity pivot problem". Karmarkar proposed an interior point method for linear problem in 1984. This method not only has a polynomial complexity, but also is highly efficient in practice. After 20 years of hard work of many mathematicians, interior point method has achieved great improvement. Because linear programming is just a special case of Complimentarity problem, interior point method is generalized to solve it.
The aim of this paper is to analyze the two-step-size problem, which was presented in a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. The new algorithm treats the classical Newton direction as the sum of two other directions, and the two directions will be equipped with different step sizes, which are denoted respectively byα_1 andα_2. In this paper, the new algorithm and the properties ofα_1 andα_2 will be introduced first. After the introduction, we discuss two ways which are used to find out the step sizes. Two Matlab programs about the algorithm will be given in the fourth chapter . Based on the numerical results we get from the operation of the programs, we can say that the method in which we setα_2 = 1, and then use bisection to obtainα_1 is feasible.
本文的目的就是对单调线形互补问题的一类新的原始对偶路径跟踪内点算法中所涉及的双步长问题进行分析。新算法中的双步长方法把经典的牛顿方向看作另外两个方向的和。并对这二个方向采用不同的步长大小,分别记为a_1和a_2。本文首先介绍新算法及两个步长的性质和对新算法迭代的影响。之后,根据步长的性质列出求解步长的两种方法,再用Matlab将两种算法编写成两个程序。最后,在对大量数值结果分析的基础上得出,把a_2固定为1,对a_1用二分法进行搜索的方法是可行的。
R.W.Cottle proposed the "Complimentarity problem" in his PhD degree paper "Nonlinear Programs with Positively Bounded Jacobians"in 1964. This problem was first referred to as "composite problem", "fundamental problem" or "complementarity pivot problem". Karmarkar proposed an interior point method for linear problem in 1984. This method not only has a polynomial complexity, but also is highly efficient in practice. After 20 years of hard work of many mathematicians, interior point method has achieved great improvement. Because linear programming is just a special case of Complimentarity problem, interior point method is generalized to solve it.
The aim of this paper is to analyze the two-step-size problem, which was presented in a new class of primal-dual path-following interior point algorithms for solving monotone linear complementarity problems. The new algorithm treats the classical Newton direction as the sum of two other directions, and the two directions will be equipped with different step sizes, which are denoted respectively byα_1 andα_2. In this paper, the new algorithm and the properties ofα_1 andα_2 will be introduced first. After the introduction, we discuss two ways which are used to find out the step sizes. Two Matlab programs about the algorithm will be given in the fourth chapter . Based on the numerical results we get from the operation of the programs, we can say that the method in which we setα_2 = 1, and then use bisection to obtainα_1 is feasible.
引文
[1] Ai W B, Zhang S Z. An O(nL)iteration primal-dual path-following method,based o n wide neighborhood large updates, for monotone linear complementarity problems. [J] .SIAM Journal on Optimization, 2005.
[2] Cottle R W. Note on a fundamental theorem in quadratic programming. Journal of the Society of Industrial and Applied Mathematics, 1964,12:663
[3] Dantzig G B. Cottle R W. Positive (semi-) definite programming. In: Abadie J, ed.Nonlinear Programming. Amsterdam: North-Holland, 1967. 55
[4] N. Megiddo. Pathways to the optimal set in linear programming. Progress in Mathematical Programming. Springer Verlag, New York, 1989.
[5] M. Kojima, S. Mizuno, and A. Yoshise. A prima-dual interior point algorithm for linear programming. Progress in Mathematical Programming. Springer Verlag, New York, 1989.
[6] M. Kojima, S. Mizuno, and A. Yoshise. A polynomial-time algorithm for a class of linear complementarity problems Mathematical Programming 44,1-26,1989.
[7] R. D. C. Monteiro, I. Adler. Interior path following primal-dual algorithms. Part I: linear programming, Mathematical Programming 44, 27-41,1989.
[8] R. D. C. Monteiro, I. Adler. Interior path following primal-dual algorithms. Part II: convex quadratic programming, Mathematical Programming 44, 43-66,1989.
[9] S. J. Wright. Primal-dual interior-point methods. SIAM Publications,Philadelphia, 1997.
[10] P, Hung and Y. Ye. An asymptotical O(n～(1/2)L) -iteration path-following linear programming algorithm that use wide neighborhoods. SIAM Journal on Optimization 6, 570-586,1996.
[11] J. F. Sturm and s. zhang. On a wide region of centers and primal-dual interior point algorithms for linear programming. Mathematics of Operations Research 22, 408-431,1997.
[12] Yinyu Ye. Interior point algorithms: theory and analysis. WILEY INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION. 1997.
[13]Robert J.Vanderbei.LINEAR PROGRAMMING second edition.Kluwer Academic Publishers.2001.
[14]C.Roos,T.Terlaky,J.Ph.Vial.Theory and Algorithms for Linear Optimization.WILEY-INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION.1997.
[15]Tamas Terlaky.INTERIOR POINT METHIDS OF MATHEMATICAL PROGRAMMING Kluwer Academic Publishers.1996.
[17]戴霞.框式约束凸二次规划问题的内点算法.[学位论文].北京图书馆.北京图书馆.2007年4月.12页到15页.
[18]龚小玉.非单调线性互补问题内点算法的研究.[学位论文].三峡大学.中国知网.2007年4月.
[2] Cottle R W. Note on a fundamental theorem in quadratic programming. Journal of the Society of Industrial and Applied Mathematics, 1964,12:663
[3] Dantzig G B. Cottle R W. Positive (semi-) definite programming. In: Abadie J, ed.Nonlinear Programming. Amsterdam: North-Holland, 1967. 55
[4] N. Megiddo. Pathways to the optimal set in linear programming. Progress in Mathematical Programming. Springer Verlag, New York, 1989.
[5] M. Kojima, S. Mizuno, and A. Yoshise. A prima-dual interior point algorithm for linear programming. Progress in Mathematical Programming. Springer Verlag, New York, 1989.
[6] M. Kojima, S. Mizuno, and A. Yoshise. A polynomial-time algorithm for a class of linear complementarity problems Mathematical Programming 44,1-26,1989.
[7] R. D. C. Monteiro, I. Adler. Interior path following primal-dual algorithms. Part I: linear programming, Mathematical Programming 44, 27-41,1989.
[8] R. D. C. Monteiro, I. Adler. Interior path following primal-dual algorithms. Part II: convex quadratic programming, Mathematical Programming 44, 43-66,1989.
[9] S. J. Wright. Primal-dual interior-point methods. SIAM Publications,Philadelphia, 1997.
[10] P, Hung and Y. Ye. An asymptotical O(n～(1/2)L) -iteration path-following linear programming algorithm that use wide neighborhoods. SIAM Journal on Optimization 6, 570-586,1996.
[11] J. F. Sturm and s. zhang. On a wide region of centers and primal-dual interior point algorithms for linear programming. Mathematics of Operations Research 22, 408-431,1997.
[12] Yinyu Ye. Interior point algorithms: theory and analysis. WILEY INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION. 1997.
[13]Robert J.Vanderbei.LINEAR PROGRAMMING second edition.Kluwer Academic Publishers.2001.
[14]C.Roos,T.Terlaky,J.Ph.Vial.Theory and Algorithms for Linear Optimization.WILEY-INTERSCIENCE SERIES IN DISCRETE MATHEMATICS AND OPTIMIZATION.1997.
[15]Tamas Terlaky.INTERIOR POINT METHIDS OF MATHEMATICAL PROGRAMMING Kluwer Academic Publishers.1996.
[17]戴霞.框式约束凸二次规划问题的内点算法.[学位论文].北京图书馆.北京图书馆.2007年4月.12页到15页.
[18]龚小玉.非单调线性互补问题内点算法的研究.[学位论文].三峡大学.中国知网.2007年4月.