Curvature integrals and iteration complexities in SDP and symmetric cone programs.

*(English)*Zbl 1319.90049Summary: In this paper, we study iteration complexities of Mizuno-Todd-Ye predictor-corrector (MTY-PC) algorithms in SDP and symmetric cone programs by way of curvature integrals. The curvature integral is defined along the central path, reflecting the geometric structure of the central path. Integrating curvature along the central path, we obtain a precise estimate of the number of iterations to solve the problem. It has been shown for LP that the number of iterations is asymptotically precisely estimated with the integral divided by \(\sqrt{\beta}\), where \(\beta\) is the opening parameter of the neighborhood of the central path in MTY-PC algorithms. Furthermore, this estimate agrees quite well with the observed number of iterations of the algorithm even when \(\beta\) is close to one and when applied to solve large LP instances from NETLIB. The purpose of this paper is to develop direct extensions of these two results to SDP and symmetric cone programs. More specifically, we give concrete formulas for curvature integrals in SDP and symmetric cone programs and give asymptotic estimates for iteration complexities. Through numerical experiments with large SDP instances from SDPLIB, we demonstrate that the number of iterations is explained quite well with the integral even for a large step size which is enough to solve practical large problems.

Reviewer: Reviewer (Berlin)

##### MSC:

90C22 | Semidefinite programming |

##### Keywords:

interior-point methods; primal-dual algorithms; path-following methods; iteration complexities; curvature; semidefinite programming; symmetric cone programs
PDF
BibTeX
XML
Cite

\textit{S. Kakihara} et al., Comput. Optim. Appl. 57, No. 3, 623--665 (2014; Zbl 1319.90049)

Full Text:
DOI

##### References:

[1] | Amari, S.-i., Nagaoka, H.: Methods of Information Geometry. Translations of Mathematical Monographs, vol. 191. American Mathematical Society, Providence (2000). Translated from the 1993 Japanese original by Daishi Harada · Zbl 0960.62005 |

[2] | Borchers, B., SDPLIB 1.2, library of semidefinite programming test problems, Optim. Methods Softw., 11/12, 683-690, (1999) · Zbl 0973.90522 |

[3] | Demmel, J.W.: Applied Numerical Linear Algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1997) · Zbl 0879.65017 |

[4] | Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York (1994). Oxford Science Publications. · Zbl 0841.43002 |

[5] | Faybusovich, L., Linear systems in Jordan algebras and primal-dual interior-point algorithms, J. Comput. Appl. Math., 86, 149-175, (1997) · Zbl 0889.65066 |

[6] | Kakihara, S., Ohara, A., Tsuchiya, T.: Information geometry and primal-dual interior-point algorithms. Optimization Online (2010) · Zbl 1322.94055 |

[7] | Kakihara, S.; Ohara, A.; Tsuchiya, T., Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs, J. Optim. Theory Appl., 157, 749-780, (2013) · Zbl 1322.90112 |

[8] | Karmarkar, N., Riemannian geometry underlying interior-point methods for linear programming, No. 114, 51-75, (1990), Providence |

[9] | Monteiro, R.D.C.; Adler, I., Interior path following primal-dual algorithms. I. linear programming, Math. Program., 44, 27-41, (1989) · Zbl 0676.90038 |

[10] | Monteiro, R.D.C.; Tsuchiya, T., Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming, SIAM J. Optim., 9, 551-577, (1999) · Zbl 0960.65072 |

[11] | Monteiro, R.D.C.; Tsuchiya, T., A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms, Math. Program., 115, 105-149, (2008) · Zbl 1151.90023 |

[12] | Monteiro, R.D.C.; Zhang, Y., A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming, Math. Program., 81, 281-299, (1998) · Zbl 0919.90109 |

[13] | Muramatsu, M., On a commutative class of search directions for linear programming over symmetric cones, J. Optim. Theory Appl., 112, 595-625, (2002) · Zbl 0994.90095 |

[14] | Ohara, A.; Tsuchiya, T., An information geometric approach to polynomial-time interior-point algorithms: complexity bound via curvature integral, 1055, (2007) |

[15] | Schmieta, S.H.; Alizadeh, F., Extension of primal-dual interior point algorithms to symmetric cones, Math. Program., 96, 409-438, (2003) · Zbl 1023.90083 |

[16] | Sonnevend, G.; Stoer, J.; Zhao, G., On the complexity of following the central path of linear programs by linear extrapolation. II, Math. Program., 52, 527-553, (1992) · Zbl 0742.90056 |

[17] | Todd, M.J.; Toh, K.C.; Tütüncü, R.H., On the Nesterov-Todd direction in semidefinite programming, SIAM J. Optim., 8, 769-796, (1998) · Zbl 0913.90217 |

[18] | Zhao, G.; Stoer, J., Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals, Appl. Math. Optim., 27, 85-103, (1993) · Zbl 0768.90056 |

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.