A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. (English) Zbl 0957.90129

Summary: In this paper we study primal-dual path-following algorithms for Second-Order Cone Programming problems (SOCP). We extend the standard long-step/semilong-step/short-step primal-dual path-following alogorithms for LP and SDP to SOCP, and prove that the long-step algorithm using the NT direction and the HRVW/KSH/M direction have \(O(n \log \varepsilon^{-1})\) iteration-complexity and \(O(n^{3/2} \log \varepsilon^{-1})\) iteration-complexity, respectively, to reduce the duality gap by a factor of \(1/\varepsilon\), where \(n\) is the number of the second-order cones. We also show that the short and semilong-step algorithms using the NT direction and the HRVW/KSH/M direction have \(O(\sqrt{n} \log \varepsilon^{-1})\) and \(O(n \log \varepsilon^{-1})\) iteration-complexities, respectively.


90C51 Interior-point methods
90C30 Nonlinear programming
Full Text: DOI


[1] Adler, I. and Alizadeh, F. May 1994. ”Primal-dual interior-point algorithms for convex quadratically constrained and semidefinite optimization problems”. May, Manuscript, Revised: August, 1995
[2] Alizadeh, F. 1997. Optimization over the Ice-cream cone. Talk given at the 16th International Symposium on Mathematical Programming. August1997, Lausanne, Switzerland. pp.24–29.
[3] DOI: 10.1137/S1052623496304700 · Zbl 0911.65047
[4] Alizadeh F., Optimization with semidefinite, quadratic and linear constraints (1997)
[5] DOI: 10.1137/0804033 · Zbl 0821.90137
[6] Faybusovich, L. 1995. ”Jordan algebras, symmetric cones and interior-point methods”. USA: Department of Mathematics, Notre Dame. Manuscript
[7] DOI: 10.1016/S0377-0427(97)00153-2 · Zbl 0889.65066
[8] DOI: 10.1023/A:1009701824047 · Zbl 0973.90095
[9] Faraut J., Analysis on Symmetric Cones (1994) · Zbl 0841.43002
[10] DOI: 10.1137/0806020 · Zbl 0853.65066
[11] DOI: 10.1007/BF01588796 · Zbl 0725.90076
[12] DOI: 10.1137/S1052623496297097 · Zbl 0912.90231
[13] Kojima M., Progress in Mathematical Programming, Interior-point and Related Methods pp 29– (1989)
[14] DOI: 10.1137/S1052623494269035 · Zbl 0872.90098
[15] DOI: 10.1016/S0024-3795(98)10032-0 · Zbl 0946.90050
[16] DOI: 10.1137/0728029 · Zbl 0742.65046
[17] DOI: 10.1137/S1052623495293056 · Zbl 0913.65051
[18] DOI: 10.1137/S1052623496312836 · Zbl 0960.65072
[19] Monteiro R. D. C., Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-Family of directions (1998)
[20] DOI: 10.1007/BF01580085 · Zbl 0919.90109
[21] DOI: 10.1007/BF02592093 · Zbl 0853.90092
[22] Nesterov Yu., Interior Point Polynomial Methods in Convex Programming (1994)
[23] DOI: 10.1287/moor.22.1.1 · Zbl 0871.90064
[24] DOI: 10.1137/S1052623495290209 · Zbl 0922.90110
[25] Schmieta S., Associative algebras, symmetric cones and polynomial time interior point algorithms (1998) · Zbl 1073.90572
[26] DOI: 10.1137/S105262349630060X · Zbl 0913.90217
[27] Tsuchiya T., A polynomial primal-dual path-following algorithm for second-order cone programming (1997)
[28] DOI: 10.1137/S1052623495288362 · Zbl 0885.68074
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.