留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

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

曾友芳, 白延琴, 简金宝, 唐春明. 二阶锥规划两个新的预估-校正算法[J]. 应用数学和力学, 2011, 32(4): 497-508. doi: 10.3879/j.issn.1000-0887.2011.04.011
引用本文: 曾友芳, 白延琴, 简金宝, 唐春明. 二阶锥规划两个新的预估-校正算法[J]. 应用数学和力学, 2011, 32(4): 497-508. doi: 10.3879/j.issn.1000-0887.2011.04.011
ZENG You-fang, BAI Yan-qin, JIAN Jin-bao, TANG Chun-ming. Two New Predictor-Corrector Algorithms for Second-Order Cone Programming[J]. Applied Mathematics and Mechanics, 2011, 32(4): 497-508. doi: 10.3879/j.issn.1000-0887.2011.04.011
Citation: ZENG You-fang, BAI Yan-qin, JIAN Jin-bao, TANG Chun-ming. Two New Predictor-Corrector Algorithms for Second-Order Cone Programming[J]. Applied Mathematics and Mechanics, 2011, 32(4): 497-508. doi: 10.3879/j.issn.1000-0887.2011.04.011

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

doi: 10.3879/j.issn.1000-0887.2011.04.011
基金项目: 国家自然科学基金资助项目(71061002;11071158);广西自然科学基金资助项目(0832052;2010GXNSFB013047)
详细信息
    作者简介:

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

  • 中图分类号: O221.2

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

  • 摘要: 基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法.其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴.算法对于迭代点可行或不可行的情形都适用.主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键.在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数.数值实验结果表明提出的两个算法是有效的.
  • [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
  • 加载中
计量
  • 文章访问数:  1309
  • HTML全文浏览量:  22
  • PDF下载量:  881
  • 被引次数: 0
出版历程
  • 收稿日期:  2010-12-30
  • 修回日期:  2011-03-03
  • 刊出日期:  2011-04-15

目录

    /

    返回文章
    返回