×
Zeng, You-fang; Bai, Yan-qin; Jian, Jin-bao; Tang, Chun-ming

Two new predictor-corrector algorithms for second-order cone programming. (English) Zbl 1220.90093

Appl. Math. Mech., Engl. Ed. 32, No. 4, 521-532 (2011).
Summary: Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms, two interior-point predictor-corrector algorithms for the second-order cone programming (SOCP) are presented. The two algorithms 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. These algorithms are suitable to the cases of feasible and infeasible interior iterative points. A simpler neighborhood of the central path for the SOCP is proposed, which is the pivotal difference from other interior-point predictor-corrector algorithms. Under some assumptions, the algorithms possess the global, linear, and quadratic convergence. The complexity bound \(O(r\)l\(n(\varepsilon _{0}/\varepsilon ))\) is obtained, where \(r\) denotes the number of the second-order cones in the SOCP problem. The numerical results show that the proposed algorithms are effective.

Cited in 1 Document

MSC:

90C25 Convex programming
90C51 Interior-point methods

Keywords:

second-order cone programming; infeasible interior-point algorithm; predictor-corrector algorithm; global convergence; complexity analysis

Software:

DIMACS
Cite Review PDF
Full Text: DOI

References:

[1] Alizadeh, F. and Goldfarb, D. Second-order cone programming. Mathematical Programming: Series B, 95, 3–51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[2] Witzgall, C. Optimal Location of a Central Facility, Mathematical Models and Concepts, Technical Report 8388, National Bureau of Standards, Washington, DC (1964)
[3] Lobo, M. S., Vandenberghe, L., Boyd, S., and Lebret, H. Applications of second-order cone programming. Linear Algebra and Its Applications, 284, 193–228 (1998) · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[4] Kanno, Y., Ohsaki, M., and Ito, J. Large-deformation and friction analysis of non-linear elastic cable networks by second-order cone programming. International Journal for Numerical Methods in Engineering, 55, 1079–1114 (2002) · Zbl 1027.74075 · doi:10.1002/nme.537
[5] Makrodimopoulos, A. and Martin, C. M. Lower bound limit analysis of cohesive-frictional materials using second-order cone programming. International Journal for Numerical Methods in Engineering, 66, 604–634 (2006) · Zbl 1110.74833 · doi:10.1002/nme.1567
[6] Nemirovskii, A. and Scheinberg, K. Extension of Karmarkar’s algorithm onto convex quadratically constrained quadratic problems. Mathematical Programming, 72, 273–289 (1996) · Zbl 0853.90092
[7] Nesterov, Y. E. and Todd, M. J. Self-scaled barriers and interior-point methods for convex programming. Mathematics of Operations Research, 22, 1–42 (1997) · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[8] Nesterov, Y. E. and Todd, M. J. Primal-dual interior-point methods for self-scaled cones. SIAM Journal on Optimization, 8(2), 324–364 (1998) · Zbl 0922.90110 · doi:10.1137/S1052623495290209
[9] Adler, I. and Alizadeh, F. Primal-Dual Interior-Point Algorithms for Convex Quadratically Constrained and Semidefinite Optimization Problems, Technical Report RRR 46-95, RUTCOR, Rutgers University (1995)
[10] Alizadeh, F., Haeberly, J. P. A., and Overton, M. L. Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, 8(3), 746–768 (1998) · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[11] Monteiro, R. D. C. and Tsuchiya, T. Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Mathematical Programming: Series A, 88, 61–83 (2000) · Zbl 0967.65077 · doi:10.1007/PL00011378
[12] Chi, X. N. and Liu, S. Y. An infeasible-interior-point predictor-corrector algorithm for the second-order cone program. Acta Mathematica Scientia, 28B(3), 551–559 (2008) · Zbl 1174.90009
[13] Mizuno, S., Todd, M. J., and Ye, Y. On adaptive-step primal-dual interior-point algorithms for linear programming. Mathematics of Operations Research, 18(4), 964–981 (1993) · Zbl 0810.90091 · doi:10.1287/moor.18.4.964
[14] Miao, J. M. Two infeasible interior-point predictor-corrector algorithms for linear programming. SIAM Journal on Optimization, 6(3), 587–599 (1996) · Zbl 0856.90075 · doi:10.1137/S105262349325771X
[15] Zhang, Y. On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM Journal on Optimization, 4(1), 208–227 (1994) · Zbl 0803.90092 · doi:10.1137/0804012
[16] Kojima, M. Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs. Annals of Operations Research, 62, 1–28 (1996) · Zbl 0848.90084 · doi:10.1007/BF02206809
[17] Bai, Y. Q., Wang, G. Q., and Roos, C. Primal-dual interior-point algorithms for second-order cone optimization based on kernel functions. Nonlinear Analysis, 70, 3584–3602 (2009) · Zbl 1190.90275 · doi:10.1016/j.na.2008.07.016
[18] Pataki, G. and Schmieta, S. The DIMACS library of semidefinte-quadratic-linear programs. http://dimacs.rutgers.edu/Challenges/Seventh/Instances/ (2002)
[19] Pan, S. H. and Chen, J. S. A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions. Computational Optimization and Applications, 45, 59–88 (2010) · Zbl 1208.90170 · doi:10.1007/s10589-008-9166-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.