×

zbMATH — the first resource for mathematics

\(LDL^T\) direction interior point method for semidefinite programming. (English) Zbl 1453.65136
MSC:
65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] F. Alizadeh, Combinatorial Optimization with Interior Point Methods and Semidefinite Matrices, Ph.D. thesis, University of Minnesota, Minneapolis, 1991.
[2] F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton, Primal-dual interior point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM J. Optim., 8 (1998), pp. 746–768. · Zbl 0911.65047
[3] F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton, Complementarity and nondegeneracy in semidefinite programming, Math. Program., 77 (1997), pp. 111–128. · Zbl 0890.90141
[4] M. F. Anjos and J. B. Lasserre, eds., Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, Internat. Ser. Oper. Res. Management Sci. 166, Springer, New York, 2012. · Zbl 1235.90002
[5] V. I. Arnold, On matrices depending on parameters, Russian Math. Surveys, 26 (1971), pp. 29–43.
[6] H. Y. Benson and R. J. Vanderbei, Solving problems with semidefinite and related constraints using interior-point methods for nonlinear programming, Math. Program. Ser. B, 95 (2003), pp. 279–302. · Zbl 1030.90138
[7] B. Borchers, SDPLIB 1.2, a library of semidefinite programming test problems, Optim. Methods Softw., 11 (1999), pp. 683–690. · Zbl 0973.90522
[8] S. Burer, Semidefinite programming in the space of partial positive semidefinite matrices, SIAM J. Optim., 14 (2003), pp. 139–172. · Zbl 1075.90059
[9] S. Burer, R. D. C. Monteiro, and Y. Zhang, Interior-point algorithms for semidefinite programming based on a nonlinear formulation, Comput. Optim. Appl., 22 (2002), pp. 49–79. · Zbl 1006.90060
[10] S. Burer, R. D. C. Monteiro, and Y. Zhang, Solving a class of semidefinite programs via nonlinear programming, Math. Program. Ser. A, 93 (2002), pp. 97–122. · Zbl 1007.90045
[11] J. da Cruz Neto, O. Ferreira, and R. D. C. Monteiro, Asymptotic behavior of the central path for a special class of degenerate sdp problems, Math. Program., 103 (2005), pp. 487–514. · Zbl 1099.90042
[12] J. Dahl, L. Vandenberghe, and V. Roychowdhury, Covariance selection for non-chordal graphs via chrodal embedding, Optim. Methods Softw., 23 (2008). · Zbl 1151.90514
[13] E. de Klerk, C. Roos, and T. Terlaky, Infeasible-start semidefinite programming algorithms via self dual embeddings, Fields Inst. Commun., 18 (1998), pp. 215–236. · Zbl 0905.90155
[14] E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program. Ser. B, 91 (2002), pp. 201–213. · Zbl 1049.90004
[15] R. Fletcher, Semi-definite matrix constraints in optimization, SIAM J. Control Optim., 23 (1985), pp. 493–513. · Zbl 0567.90088
[16] K. Fujisawa, M. Kojima, and K. Nakata, Exploiting sparsity in primal-dual interior-point method for semidefinite programming, Math. Program., 79 (1997), pp. 235–253. · Zbl 0887.90156
[17] M. Fukuda, M. Kojima, K. Murota, and K. Nakata, Exploiting sparsity in semidefinite programming via matrix completion I: General framework, SIAM J. Optim., 11 (2000), pp. 647–674. · Zbl 1010.90053
[18] D. Goldfarb and K. Scheinberg, Interior point trajectories in semidefinite programming, SIAM J. Optim., 8 (1998), pp. 871–886. · Zbl 0914.90215
[19] G. Golub and C. Van Loan, Matrix Computations, Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, 1996.
[20] N. I. M. Gould and J. Scott, A note on performance profiles for benchmarking software, ACM Trans. Math. Software, 43 (2016), pp. 15:1–15:5, . · Zbl 1369.65202
[21] M. Halicka, Analyticity of the central path at the boundary point in semidefinite programming, European J. Oper. Res., 143 (2002), pp. 311–324. · Zbl 1058.90047
[22] M. Halicka, E. de Klerk, and C. C. Roos, Limiting behavior of the central path in semidefinite optimization, Optim. Methods Softw., 20 (2005), pp. 99–113. · Zbl 1087.90057
[23] C. Helmberg, F. Rendl, R. Vanderbei, and H. Wolkowicz, An interior-point method for semidefinite programming, SIAM J. Optim., 6 (1996), pp. 342–361. · Zbl 0853.65066
[24] N. J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996. · Zbl 0847.65010
[25] M. Kojima, S. Shindoh, and S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7 (1997), pp. 86–125. · Zbl 0872.90098
[26] Z. Lu and R. D. C. Monteiro, Error bounds and limiting behavior of weighted paths associated with the SDP map \(X^{\frac{1}{2}}SX^{\frac{1}{2}}\), SIAM J. Optim., 15 (2004), pp. 348–374. · Zbl 1077.90048
[27] Z. Lu and R. D. C. Monteiro, Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming, Optim. Methods Softw., 22 (2007), pp. 849–870. · Zbl 1189.90116
[28] Z. Q. Luo, J. F. Sturm, and S. Zhang, Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming, SIAM J. Optim., 8 (1998), pp. 59–81. · Zbl 0910.90229
[29] C. B. Moler, Iterative refinement in floating point, J. ACM, 14 (1967), pp. 316–321. · Zbl 0161.35501
[30] R. D. C. Monteiro, Primal-dual path-following algorithms for semidefinite programming, SlAM J. Optim., 7 (1997), pp. 663–678. · Zbl 0913.65051
[31] R. D. C. Monteiro, First- and second-order methods for semidefinite programming, Math. Program., 97 (2003), pp. 209–244.
[32] R. D. C. Monteiro and T. Tsuchiya, Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming, SIAM J. Optim., 9 (1999), pp. 551–577. · Zbl 0960.65072
[33] R. D. C. Monteiro and P. R. Zanjacomo, General interior-point maps and existence of weighted paths for nonlinear semidefinite complementarity probems, Math. Oper. Res., 25 (2000), pp. 381–399. · Zbl 1073.90571
[34] K. Nakata, K. Fujisawa, M. Fukuda, M. Kojima, and K. Murota, Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results, Math. Program. Ser. B, 95 (2003), pp. 303–327. · Zbl 1030.90081
[35] Y. E. Nesterov and A. S. Nemirovskii, Interior Point Polynomial Methods in Convex Programming: Theory and Applications, Stud. Appl. Numer. Math., SIAM, Philadelphia, 1994. · Zbl 0824.90112
[36] Y. E. Nesterov and M. J. Todd, Primal-dual interior-point methods for self-scaled cones, Math. Oper. Res., 22 (1997), pp. 1–42. · Zbl 0871.90064
[37] J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MPS-SIAM Ser. Optim., SIAM, philadelphia, 2001. · Zbl 0986.90075
[38] A. Shapiro, First and second order analysis of nonlinear semidefinite programs, Math. Program., 77 (1997), pp. 301–320. · Zbl 0888.90127
[39] A. Shapiro and M. K. H. Fan, On eigenvalue optimization, SIAM J. Optim., 5 (1995), pp. 552–569. · Zbl 0838.90115
[40] G. Srijuntongsiri and S. A. Vavasis, A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming, , 2004.
[41] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 (1999), pp. 625–653. · Zbl 0973.90526
[42] M. J. Todd, A study of search directions in primal-dual interior-point methods for semidefinite programming, Optim. Methods Softw., 11 (1999), pp. 1–46. · Zbl 0971.90109
[43] M. J. Todd, K. C. Toh, and R. H. Tütüncü, On the Nesterov–Todd direction in semidefinite programming, SIAM J. Optim., 8 (1998), pp. 769–796. · Zbl 0913.90217
[44] K. C. Toh, Solving large scale semidefinite programs via an iterative solver on the augmented systems, SIAM J. Optim., 14 (2004), pp. 670–698. · Zbl 1071.90026
[45] R. H. Tütüncü, K. C. Toh, and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT\(3\), Math. Program. Ser. B, 95 (2003), pp. 189–217. · Zbl 1030.90082
[46] H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Handbook of Semidefinite Programming Theory, Algorithms, and Applications, Internat. Ser. Oper. Res. Management Sci. 27, Springer, New York, 2000. · Zbl 0962.90001
[47] M. Yamashita and K. Nakata, Fast implementation for semidefinite programs with positive matrix completion, Optim. Methods Softw., 30 (2015), pp. 1030–1049. · Zbl 1376.90044
[48] Y. Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming, SIAM J. Optim., 8 (1998), pp. 365–386. · Zbl 0913.65050
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.