×

Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. (English) Zbl 1229.90084

The authors propose a second order interior point algorithm for symmetric cone programming, using a wide neighborhood of the central path. The basic tool of their analysis of the complexity bounds of the proposed methods is the theory of Euclidean Jordan algebras. Polynomial convergence for several infeasible and feasible interior point methods is also established.

MSC:

90C05 Linear programming
90C25 Convex programming
90C51 Interior-point methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh F, Haeberly JP, Overton ML (1998) Primal-dual interior point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J Optim 8: 746–768 · Zbl 0911.65047 · doi:10.1137/S1052623496304700
[2] Faraut J, Korányi A (1994) Analysis on symmetric cones, Oxford Mathematical Monographs. Oxford University Press, New York · Zbl 0841.43002
[3] Faybusovich L (1997) Linear systems in Jordan algebras and primal-dual interior-point algorithms. J Comput Appl Math 86: 149–175 · Zbl 0889.65066 · doi:10.1016/S0377-0427(97)00153-2
[4] Mehrotra S (1992) On the implementation of a primal dual interior point method. SIAM J Optim 2: 575–601 · Zbl 0773.90047 · doi:10.1137/0802028
[5] Monteiro RDC (1998) Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. SIAM J Optim 8: 797–812 · Zbl 0913.65052 · doi:10.1137/S1052623496308618
[6] Monteiro RDC, Tsuchiya T (2000) Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. Math Program 88: 61–83 · Zbl 0967.65077 · doi:10.1007/PL00011378
[7] Monteiro RDC, Zhang Y (1998) A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. Math Program 81: 281–299 · Zbl 0919.90109
[8] Muramatsu M (2002) On a commutative class of search directions for linear programming over symmetric cones. J Optim Theory Appl 112: 595–625 · Zbl 0994.90095 · doi:10.1023/A:1017920200889
[9] Nesterov YE, Nemirovskii AS (1994) Interior-point polynomial algorithms in convex programming. SIAM, Philadelphia · Zbl 0824.90112
[10] Nesterov YE, Todd MJ (1997) Self-scaled barriers and interior point methods for convex programming. Math Oper Res 22: 1–42 · Zbl 0871.90064 · doi:10.1287/moor.22.1.1
[11] Rangarajan BK (2006) Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J Optim 16: 1211–1229 · Zbl 1131.90043 · doi:10.1137/040606557
[12] Salahi M, Mahdavi-Amiri N (2006) Polynomial time second order Mehrotra-type predictor-corrector algorithms. Appl Math Comput 183: 646–658 · Zbl 1112.65057 · doi:10.1016/j.amc.2006.05.092
[13] Schmieta SH, Alizadeh F (2001) Associative and Jordan algebras, and polynomial time interior-point algorithms for symmetric cones. Math Oper Res 26: 543–564 · Zbl 1073.90572 · doi:10.1287/moor.26.3.543.10582
[14] Schmieta SH, Alizadeh F (2003) Extension of primal-dual interior-point algorithms to symmetric cones. Math Program 96: 409–438 · Zbl 1023.90083 · doi:10.1007/s10107-003-0380-z
[15] Tsuchiya T (1999) A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming. Optim Methods Softw 11: 141–182 · Zbl 0957.90129 · doi:10.1080/10556789908805750
[16] Zhang Y (1994) On the convergence of a class of infeasible-interior-point methods for the horizontal linear complementarity problem. SIAM J Optim 4: 208–227 · Zbl 0803.90092 · doi:10.1137/0804012
[17] Zhang Y (1998) On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J Optim 8: 365–386 · Zbl 0913.65050 · doi:10.1137/S1052623495296115
[18] Zhang Y, Zhang D (1995) On polynomial of the Mehrotra-type predictor-corrector interior-point algorithms. Math Program 68: 303–318 · Zbl 0837.90087 · doi:10.1007/BF01585769
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.