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

ZENG You-fang; BAI Yan-qin; JIAN Jin-bao; TANG Chun-ming

doi:10.3879/j.issn.1000-0887.2011.04.011

Volume 32 Issue 4

Turn off MathJax

Article Contents

Article Navigation > Applied Mathematics and Mechanics > 2011 > 32(4): 497-508

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:

PDF( 393 KB)

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

doi: 10.3879/j.issn.1000-0887.2011.04.011

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

Received Date: 2010-12-30
Rev Recd Date: 2011-03-03
Publish Date: 2011-04-15

Abstract

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

FullText(HTML)

References(19)

References

[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