×

zbMATH — the first resource for mathematics

Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach. (English) Zbl 1368.90123

MSC:
90C22 Semidefinite programming
90C25 Convex programming
90C46 Optimality conditions and duality in mathematical programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. A. Abrams, Projections of convex programs with unattained infima, SIAM J. Control, 13 (1975), pp. 706–718. · Zbl 0269.90042
[2] E. Andersen, C. Roos, and T. Terlaky, Notes on duality in second order and p-order cone optimization, Optimization, 51 (2002), pp. 627–643. · Zbl 1040.90047
[3] G. P. Barker and D. Carlson, Cones of diagonally dominant matrices., Pacific J. Math., 57 (1975), pp. 15–32. · Zbl 0283.52005
[4] D. P. Bertsekas, A. Nedić, and A. E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, MA, Belmont, 2003.
[5] J. Borwein and H. Wolkowicz, Regularizing the abstract convex program, J. Math. Anal. Appl., 83 (1981), pp. 495–530. · Zbl 0467.90076
[6] Y.-L. Cheung, S. Schurr, and H. Wolkowicz, Preprocessing and regularization for degenerate semidefinite programs, in Computational and Analytical Mathematics, Springer, New York, 2013, pp. 251–303. · Zbl 1288.90060
[7] E. de Klerk, C. Roos, and T. Terlaky, Initialization in semidefinite programming via a self-dual skew-symmetric embedding, Oper. Res. Lett., 20 (1997), pp. 213–221. · Zbl 0881.90096
[8] E. de Klerk, T. Terlaky, and K. Roos, Self-dual embeddings, in Handbook of Semidefinite Programming, International Series in Operations Research and Management Science 27, Springer, Boston, MA, 2000, pp. 111–138. · Zbl 0957.90526
[9] M. Dür, B. Jargalsaikhan, and G. Still, The Slater condition is generic in linear conic programming, Optimization online: 2012/11/3675.
[10] R. M. Freund, On the behavior of the homogeneous self-dual model for conic convex optimization, Math. Program., 106 (2006), pp. 527–545. · Zbl 1134.90034
[11] H. A. Friberg, Facial reduction heuristics and the motivational example of mixed-integer conic optimization, Optimization online: 2016/02/5324.
[12] A. J. Goldman and A. W. Tucker, Theory of linear programming, in Linear Inequalities and Related Systems, Annals of Mathematics Studies, Princeton University Press, Princeton, NJ, 38 (1956), pp. 53–97. · Zbl 0072.37601
[13] M. Halická, E. de Klerk, and C. Roos, On the convergence of the central path in semidefinite optimization, SIAM J. Optim., 12 (2002), pp. 1090–1099. · Zbl 1035.90100
[14] M. Liu and G. Pataki, Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming, Math. Program. (2017), . · Zbl 1402.90115
[15] B. F. Lourenço, M. Muramatsu, and T. Tsuchiya, Solving SDP Completely with an Interior Point Oracle, preprint, , 2015.
[16] Z.-Q. Luo, J. F. Sturm, and S. Zhang, Duality and Self-Duality for Conic Convex Programming, Technical report 9620/A, Econometric Institute, Erasmus University Rotterdam, 1996.
[17] Z.-Q. Luo, J. F. Sturm, and S. Zhang, Duality Results for Conic Convex Programming, Technical report, Econometric Institute, Erasmus University Rotterdam, 1997.
[18] H. D. Mittelmann, An independent benchmarking of SDP and SOCP solvers, Math. Program., 95 (2003), pp. 407–430. · Zbl 1030.90080
[19] Mosek APS, The MOSEK optimization software. Available online from .
[20] Y. Nesterov, Infeasible start interior-point primal-dual methods in nonlinear programming, CORE Discussion Papers 1995067, Center for Operations Research and Econometrics (CORE), Université catholique de Louvain, 1995.
[21] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd, Operator Splitting for Conic Optimization via Homogeneous Self-Dual Embedding, preprint, , 2013.
[22] G. Pataki, Strong duality in conic linear programming: Facial reduction and extended duals, in Computational and Analytical Mathematics, Springer, New York, 2013, pp. 613–634. · Zbl 1282.90231
[23] G. Pataki and S. Schmieta, The DIMACS library of semidefinite-quadratic-linear programs, 1999, Available online from .
[24] F. Permenter and P. A. Parrilo, Basis selection for SOS programs via facial reduction and polyhedral approximations, in Proceedings of the IEEE Conference on Decision and Control, 2014.
[25] F. Permenter and P. A. Parrilo, Partial Facial Reduction: Simplified, Equivalent SDPs via Inner Approximations of the PSD Cone, preprint, , 2014.
[26] F. A. Potra and R. Sheng, On homogeneous interrior-point algorithms for semidefinite programming, Optim. Methods Softw., 9 (1998), pp. 161–184. · Zbl 0904.90118
[27] H. Ramírez and D. Sossa, On the central paths in symmetric cone programming, J. Optim. Theory Appl., 172 (2017), pp. 649–668. · Zbl 1398.90123
[28] J. Renegar, Incorporating condition measures into the complexity theory of linear programming, SIAM J. Optim., 5 (1995), pp. 506–524. · Zbl 0838.90139
[29] R. T. Rockafellar, Convex Analysis, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. · Zbl 0932.90001
[30] 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
[31] J. F. Sturm, Error bounds for linear matrix inequalities, SIAM J. Optim., 10 (2000), pp. 1228–1248. · Zbl 0999.90027
[32] K.-C. Toh, M. J. Todd, and R. Tütüncü, SDPT3 version 4.0: A MATLAB software for semidefinite-quadratic-linear programming, 2009. Available online from .
[33] H. Waki and M. Muramatsu, Facial reduction algorithms for conic optimization problems, J. Optim. Theory Appl., 158 (2013), pp. 188–215. · Zbl 1272.90048
[34] H. Waki, M. Nakata, and M. Muramatsu, Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization, Comput. Optim. and Appl., 53 (2012), pp. 823–844. · Zbl 1264.90162
[35] Y. Ye, M. J. Todd, and S. Mizuno, An \(\mathcal{O} (\sqrt{nL})\)-iteration homogeneous and self-dual linear programming algorithm, Math. of Oper. Res., 19 (1994), pp. 53–67. · Zbl 0799.90087
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.