一类线性约束凸规划问题的一个原始－对偶内点算法
PDF下载 (381)张 艺.一类线性约束凸规划问题的一个原始－对偶内点算法[J].宁波大学学报(理工版),2013,26(02):103-107.DOI:
ZHANG Y.A Primal-dual Interior Point Algorithm for a Class of Convex Programming Problems with Linear Constraints[J].Journal of Ningbo University(Natural Science & Engineering Edition),2013,26(02):103-107.DOI:
| Title: | A Primal-dual Interior Point Algorithm for a Class of Convex Programming Problems with Linear Constraints |
| 作者: | 张 艺 |
| Author(s): | ZHANG Y |
| 关键词: | 凸规则; 内点算法; 原始－对偶; 路径跟踪 |
| Keywords: | convex programming; interior point algorithm; primal-dual; path-following |
| 分类号: | O221.2 |
| 文献标识码: | A |
| 摘要: | 对一类具有线性约束的凸规划问题给出了一个原始－对偶内点算法, 该算法可在任一原始－对偶可行内点启动, 并且全局收敛. 当初始点靠近中心路径时, 便成为中心路径跟踪算法. 数值算例表明该算法是有效的. |
| Abstract: | In this paper, a primal-dual interior point algorithm is presented for a class of convex programming problems with linear constrains. It can be implemented at any primal-dual interior feasible point and reaches the global convergence. If the initial point is close to the central path, it becomes a central path-following algorithm. The results of numerical tests show the effectiveness of the algorithm. |
| 参考文献 /References: | [1] Karmarkar N. A new polynomial algrithm for linear program[J]. Combinatoric, 1984, 4:373-395. [2] 方述诚, 普森普拉S. 线性优化及扩展理论与算法[M].北京: 科学出版社, 1994. [3] Monteiro R D C, Adler I. Interior path following primal-dual algorithms[J]. Mathemaical Programming, 1989, 44:27-41. [4] Monteiro R D C, Adler I. An extension of karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence[J]. Mathematics of Operations Research, 1990, 15:408-422. [5] Jansen B, Roos C, Terlaky T, et al. Polynomiality of primal-dual affine scaling algorithm for nonlinear complementarity problems[J]. Mathematical Programming, 1997, 78:315-345. [6] Yu Q, Huang C C, Jiang Y. A polynomial predietor- corrector interior-point algorithm for convex quadratic programming[J]. Acta Mathematica Scientia, 2006, 26B(2):263-270. [7] Renegar J. A mathematical view of interior-poit method in convex optimization[M]. Philadelphia PA: Mathematical Programming Society, 2001. [8] 金正静, 白延琴, 韩伯顺. 求解凸二次规划问题的一种加权路径跟踪算法[J]. 运筹学学报, 2010, 14(1):55-65. |
| 备注/Memo: | 收稿日期: 2012－12－14. 基金项目: 浙江省海洋与渔业项目（ZHYF201102）; 浙江省教育厅科研项目（Y201119382）; 宁波大学学科科研项目（XKl060）. 作者简介: 张 艺（1960－）, 男, 浙江海宁人, 副教授, 主要研究方向: 最优化理论与计算等. E-mail: zhangyi@nbu.edu.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
