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

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

doi: 10.3879/j.issn.1000-0887.2011.04.011
  • Received Date: 2010-12-30
  • Rev Recd Date: 2011-03-03
  • Publish Date: 2011-04-15
  • 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 (ε0/ε)) was obtained,where r denotes the number of second-order cones in SOCP problem.The numerical results show that the proposed algorithms are effective.
  • loading
  • [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
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (1543) PDF downloads(885) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return