凸二次半定规划一个长步原始对偶路径跟踪算法

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2021-12-27

凸二次半定规划一个长步原始对偶路径跟踪算法黎健玲¹, 王培培¹, 曾友芳¹, 简金宝²1. 广西大学数学与信息科学学院, 南宁 530004;
2. 广西民族大学理学院, 南宁 A Long Step Primal-Dual Path-following Algorithm for Convex Quadratic Semidefinite Programming LI Jianling¹, WANG Peipei¹, ZENG Youfang¹, JIAN Jinbao²1. College of Mathematics and Information Science, Guangxi University, Nanning 530004, China;
2. College of Science, Guangxi University for Nationalities, Nanning 530006, China

摘要
图/表
参考文献
相关文章(2)
点击分布统计
下载分布统计
-->

全文: PDF(414 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

摘要本文基于Nesterov-Todd方向，并引进中心路径测量函数以及原始对偶对数障碍函数，建立了一个求解凸二次半定规划的长步路径跟踪法.算法保证当迭代点落在中心路径附近时步长1被接受.算法至多迭代O（n|ln ε|）次可得到一个ε最优解.论文最后报告了初步的数值试验结果.

服务

加入引用管理器

E-mail Alert

RSS

收稿日期: 2018-11-19

PACS:

O221.2

基金资助:国家自然科学基金（11561005），广西自然科学基金（2016GXNSFAA380248）资助项目.

引用本文:

黎健玲, 王培培, 曾友芳, 简金宝. 凸二次半定规划一个长步原始对偶路径跟踪算法[J]. 应用数学学报, 2020, 43(1): 12-32. LI Jianling, WANG Peipei, ZENG Youfang, JIAN Jinbao. A Long Step Primal-Dual Path-following Algorithm for Convex Quadratic Semidefinite Programming. Acta Mathematicae Applicatae Sinica, 2020, 43(1): 12-32.

链接本文:

http://123.57.41.99/jweb_yysxxb/CN/或 http://123.57.41.99/jweb_yysxxb/CN/Y2020/V43/I1/12

[1]	Higham N J. Computing the nearest correlation matrixa problem from finance. J. IMA Journal of Numerical Analysis, 2002, 22(3):329-343
[2]	Vandenberghe L, Boyd S. Semidefinite programming. J. SIAM Review, 1996, 38:49-95
[3]	Nie J W, Yuan Y X. A potential reduction algorithm for an extended SDP problem. J. Science in China, Series A. Mathematics, 2000, 43(1):35-46
[4]	Nie J W, Yuan Y X. A predictor-corrector algorithm for QSDP combining Dikin-Type and newton centering steps. J. Annals of Operations Research, 2001, 103:115-133
[5]	Xu F M, Xu C X. Primal-dual algorithm for quadratic semidefinite programming. J. Chinese Journal of Engineering Mathematics, 2006, 23(4):590-598
[6]	Toh K C. An inexact primal-dual path following algorithm for convex quadratic SDP. J. Mathematical Programming, 2008, 112(1):221-254
[7]	Toh K C, Tütüncü R H, Todd M J. Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems. J. Pacific Journal of Optimization, 2006, 3(1):135-164
[8]	Todd M J, Toh K C, Tütüncü R H. On the Nesterov-Todd direction in semidefinite programming. J. SIAM Journal on Optimization, 1998, 8(3):769-796
[9]	Zhang Y. On extending primal-dual interior-point algorithms from linear programming to semidefinite programming. J. SIAM Journal on Optimization, 1998, 8(2):365-386
[10]	Jiang J. A long step primal-dual path following method for semidefinite programming. J. Operations Research Letters, 1998, 23(1-2):53-61
[11]	Klerk E D. Aspects of semidefinite programming:interior point algorithms and selected applications. Boston, Dordrecht, London, Moscow, New York:Kluwer Academic Publishers, 2004
[12]	修乃华, 罗自炎. 半定规划. 北京:北京交通大学出版社, 2014(Xiu N H, Luo Z Y. Semidefinite Programming. Beijing:Beijing Jiaotong University Press, 2014)
[13]	Horn R A, Johnson C R. Matrix analysis (second edition). Cambridge:Cambridge University, 1985
[14]	Nemirovskii A, Gahinet P. The projective method for solving linear matrix inequalities. J. Mathmatical Programming, Series B,1997,77(1):163-190
[15]	Roos C, Terlaky T, Vial J P. Theory and algorithms for linear optimization:an interior point approach. New York:John Wiley and Sons, 1997
[16]	Jansen B, Roos C, Terlaky T, Vial J P. Primal-dual algorithms for linear programming based on the logarithmic barrier method. J. Journal of Optimization Theory and Applications, 1994, 83(1):1-26
[17]	Zhao X Y. A semismooth Newton-CG augmented lagrangian method for large scale linear and convex quadratic SDPs. Singapore:National University of Singapore, 2009

[1]	艾文宝, 张可村. 线性规划的一般中心路径和最大步长一般中心路径的跟随算法[J]. 应用数学学报(英文版), 2001, 17(3): 296-303.
[2]	艾文宝, 张可村. 线性规划的一般中心路径和最大步长一般中心路径的跟随算法[J]. 应用数学学报(英文版), 2001, 17(3): 296-303.

PDF全文下载地址:

http://123.57.41.99/jweb_yysxxb/CN/article/downloadArticleFile.do?attachType=PDF&id=14708