应用数学学报
首页  |  期刊介绍  |  编 委 会  |  投稿指南  |  期刊订阅  |  广告服务  |  相关链接  |  下载中心  |  联系我们  |  留言板
 
应用数学学报 英文版  
   
   
高级检索 »  
应用数学学报  1996, Vol. 19 Issue (1): 46-50    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索  |   
二次规划的内椭球算法
郭田德, 吴方
中国科学院应用数学研究所, 北京100080
INTERIOR ELLIPSOID METHOD FOR CONVEX QUADRATIC PROGRAMMING
GUO TIANDE, WU FANG
Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing 100080
 全文: PDF ( KB)   HTML ( KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 对于标准型的凸二次规划问题本文给出了一个新算法。算法的每一步迭代,利用内椭球的思想来近似求解一个线性规划子问题而得到迭代方向,再适当选取步长而使之成为多项式算法,其迭代步数为O(nL2),每一步迭代所需计算量为O(n3),其中n为变量个数,L为问题的输入长度。
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
郭田德
吴方
关键词凸二次规划   内椭球算法   多项式算法   Karmarkar算法   计算复杂度     
Abstract: In this paper, a new variant of the interior ellipsoid method for convex quadratic programming is developed. Compared to the algorithm proposed by Ye and Tse[5],the sub-problem of new algorithm is a linear programming which is easy to solve, although both have the same complexity.
Key wordsConvex quadratic programming   interior ellipsoid method   Karmarkar algorithm   complexity   
收稿日期: 1995-01-20;
基金资助:国家自然科学基金
引用本文:   
郭田德,吴方. 二次规划的内椭球算法[J]. 应用数学学报, 1996, 19(1): 46-50.
GUO TIANDE,WU FANG. INTERIOR ELLIPSOID METHOD FOR CONVEX QUADRATIC PROGRAMMING[J]. Acta Mathematicae Applicatae Sinica, 1996, 19(1): 46-50.
 
[1] Karmarkar, N. A New Polynomial-time Algorithm for Linear Programming, Combinatorica, 1984, 4:373-395.
[2] Todd, Michael J. and Burell. An Extension of Karmarkar's Algorithm for Linear Programming Using Dual Variables, Algorithmica, 1986, 1:409-424.
[3] Monteiro, R.D.C. and Adler, I. Interior Path Following Primal-dual Algorithm, part Ⅱ:Convex Quadratic Programming, Mathematical Programming, 1989, 44:43-66.
[4] Barnes, E.R. A Variation on Karmarkar's Algorithm for Solving Linear Programming Problems,Mathematical Programming, 1986, 36:174-182.
[5] Ye, Y. and Tse, E. An Extension of Karmarkar's Algorithm for Convex Quadratic Programming,Mathematical Programming, 1989, 47:157-179.
[6] Dikin, LI. Iterative Solution of Problems of Linear and Quadratic Programming, Soviet Math. Dokl.,1967, 8:674-675.
[7] Goldfarb, D. and Liu. An O(n3L) Primal Interior Point Algorithm for Convex Quadratic Programming. Mathematical Programming, 1991, 49:325-340.
[8] Kapoor, S. and Vaidya, P. Fast Algorithm for Convex Quadratic Programming and Multicommodity Flows, Proceedings of the 18th Annual ACM Symposium on the Theory of Computing, 1986, 197-159.
[9] Ben Daya, M. and Shetty, C.M. Polynomial Barrier Function Algorithm for Convex Quadratic Programming, Manuscript, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, GA, 1988).
[10] Ye, Y. Further Development on the Interior Algorithm for Convex Quadratic Programming, Manuscript, Department of Engineering-Economic Systems, Stanford, CA, 1987.
[11] Mehrotra, S. and Sun, J. An Algorithm for Convex Quadratic Programming that Requies O(n3.5L) Arithmetic Operations, Mathematics of Operations Research, 1990, 15:342-363.
[12] Gonzaga, C.C. An Algorithm for Solving Linear Programming Problems in O(n3.5L) Operations, in Megiddo, ed., Advances in Mathematical Programming-Interior Point and Related Method Chapter 1,Springer, Berlin, 1989.
[13] Jarre, F. On the Convergence of the Method of Analytic Centers When Applied to Convex Quadatic Programs, Mathematical Programming, 1991, 49:341-358.
没有找到本文相关文献
  版权所有 © 2009 应用数学学报编辑部   E-mail: amas@amt.ac.cn
京ICP备05002806号-9