二阶锥规划两个新的预估-校正算法

曾友芳; 白延琴; 简金宝; 唐春明

doi:10.3879/j.issn.1000-0887.2011.04.011

二阶锥规划两个新的预估-校正算法

doi: 10.3879/j.issn.1000-0887.2011.04.011

上海大学数学系, 上海 200444;

基金项目: 国家自然科学基金资助项目(71061002;11071158);广西自然科学基金资助项目(0832052;2010GXNSFB013047)

详细信息

作者简介:
曾友芳(1974- ),女,广西靖西人,讲师,博士生(联系人.E-mail:zengyf@gxu.edu.cn).

中图分类号: O221.2
计量
- 文章访问数: 1549
- HTML全文浏览量: 73
- PDF下载量: 885
- 被引次数: 0
出版历程
- 收稿日期: 2010-12-30
- 修回日期: 2011-03-03
- 刊出日期: 2011-04-15

Two New Predictor-Corrector Algorithms for Second-Order Cone Programming

Department of Mathematics, Shanghai University, Shanghai 200444, P. R. China;
College of Mathematics and Information Science, Guangxi University, Nanning 530004, P. R. China

摘要

摘要: 基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法．其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴．算法对于迭代点可行或不可行的情形都适用．主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键．在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数．数值实验结果表明提出的两个算法是有效的．
- 二阶锥规划 /
- 不可行内点算法 /
- 预估-校正算法 /
- 全局收敛性 /
- 复杂性分析
Abstract: Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms,two interior-point predictor-corrector algorithms for second-order cone programming (SOCP) were presented.They use the Newton direction and the Euler direction as the predictor directions,respectively.The corrector directions belong to the category of the Alizadeh-Haeberly-Overton (AHO) directions.The two new algorithms were suitable to cases of feasible and infeasible interior iterative points.A simpler neighborhood of central path for the SOCP was proposed,which was the pivotal difference from other interior-point predictor-corrector algorithms.Under some assumptions,the algorithms possess global,linear and quadratic convergence.The complexity bound O (rln (ε₀/ε)) was obtained,where r denotes the number of second-order cones in SOCP problem.The numerical results show that the proposed algorithms are effective.
- second-order cone programming /
- infeasible interior-point algorithm /
- predictor-corrector algorithm /
- global convergence /
- complexity analysis

HTML全文

参考文献(19)

[1]	Alizadeh F, Goldfarb D. Second-order cone programming[J]. Mathematical Programming Ser B, 2003,95(1 ):3-51. doi: 10.1007/s10107-002-0339-5
[2]	Witzgall C. Optimal location of a central facility, mathematical models and concepts[R]. Technical Report 8388, National Bureau of Standards,Washington, DC, 1964.
[3]	Lobo M S, Vandenberghe L, Boyd S, Lebret H. Applications of second-order cone programming[J].Linear Algebra and Its Applications, 1998, 284(1/3): 193-228. doi: 10.1016/S0024-3795(98)10032-0
[4]	Kanno Y, Ohsaki M, Ito J. Large-deformation and friction analysis of non-linear elastic cable networks by second-order cone programming[J].International Journal for Numerical Methods in Engineering,2002, 55(9):1079-1114. doi: 10.1002/nme.537
[5]	Makrodimopoulos A, Martin C M. Lower bound limit analysis of cohesive-frictional materials using second-order cone programming[J].International Journal for Numerical Methods in Engineering,2006, 66(4):604-634. doi: 10.1002/nme.1567
[6]	Nemirovskii A, Scheinberg K. Extension of Karmarkar’s algorithm onto convex quadratically constrained quadratic problems[J]. Mathematical Programming, 1996,72(3):273-289.
[7]	Nesterov Y E, Todd M J. Self-scaled barriers and interior-point methods for convex programming[J]. Mathematics of Operations Research, 1997, 22(1):1-42. doi: 10.1287/moor.22.1.1
[8]	Nesterov Y E, Todd M J. Primal-dual interior-point methods for self-scaled cones[J]. SIAM Journal on Optimization, 1998, 8(2): 324-364. doi: 10.1137/S1052623495290209
[9]	Adler I, Alizadeh F. Primal-dual interior-point algorithms for convex quadratically constrained and semidefinite optimization problems[R]. Technical Report RRR 46-95, RUTCOR, Rutgers University, 1995.
[10]	Alizadeh F, Haeberly J P A, Overton M L. Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results[J]. SIAM Journal on Optimization, 1998, 8(3): 746-768. doi: 10.1137/S1052623496304700
[11]	Monteiro R D C, Tsuchiya T. Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions[J].Mathematical Programming Ser A, 2000, 88(1):61-83. doi: 10.1007/PL00011378
[12]	Chi X N, Liu S Y. An infeasible-interior-point predictor-corrector algorithm for the second-order cone program[J]. Acta Mathematica Scientia B, 2008, 28(3): 551-559. doi: 10.1016/S0252-9602(08)60058-2
[13]	Mizuno S, Todd M J, Ye Y. On adaptive-step primal-dual interior-point algorithms for linear programming[J]. Mathematics of Operations Research, 1993, 18(4): 964-981. doi: 10.1287/moor.18.4.964
[14]	Miao J M. Two infeasible interior-point predictor-corrector algorithms for linear programming[J]. SIAM Journal on Optimization, 1996, 6(3): 587-599. doi: 10.1137/S105262349325771X
[15]	Zhang Y. On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem[J]. SIAM Journal on Optimization, 1994, 4(1): 208-227. doi: 10.1137/0804012
[16]	Kojima M. Basic lemmas in polynomial-time infeasible-interior point methods for linear programs[J]. Annals of Operations Research, 1996, 62(1):1-28. doi: 10.1007/BF02206809
[17]	Bai Y Q, Wang G Q, Roos C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions[J]. Nonlinear Analysis, 2009, 70(10): 3584-3602. doi: 10.1016/j.na.2008.07.016
[18]	Pataki G, Schmieta S. The DIMACS library of semidefinite-quadratic-linear programs[R]. Technical report. Computational Optimization Research Center, Columbia University, 2002.
[19]	Pan Sh H, Chen J Sh. A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions[J]. Computational Optimization and Applications, 2010, 45(1):59-88. doi: 10.1007/s10589-008-9166-9