×

Error bounds and singularity degree in semidefinite programming. (English) Zbl 1462.90086

Summary: In semidefinite programming a proposed optimal solution may be quite poor in spite of having sufficiently small residual in the optimality conditions. This issue may be framed in terms of the discrepancy between forward error (the unmeasurable “true error”) and backward error (the measurable violation of optimality conditions). In [ibid. 10, No. 4, 1228–1248 (2000; Zbl 0999.90027)], J. F. Sturm provided an upper bound on forward error in terms of backward error and singularity degree. In this work we provide a method to bound the maximum rank over all optimal solutions and use this result to obtain a lower bound on forward error for a class of convergent sequences. This lower bound complements the upper bound of Sturm. The results of Sturm imply that semidefinite programs with slow convergence necessarily have large singularity degree. Here we show that large singularity degree is, in some sense, also a sufficient condition for slow convergence for a family of external-type “central” paths. Our results are supported by numerical observations.

MSC:

90C22 Semidefinite programming

Citations:

Zbl 0999.90027

Software:

frlib
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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
[2] W. Barrett, C.R. Johnson, and P. Tarazaga, The real positive definite completion problem for a simple cycle, Linear Algebra Appl., 192 (1993), pp. 3-31. · Zbl 0786.15027
[3] J.M. Borwein and H. Wolkowicz, Characterization of optimality for the abstract convex program with finite-dimensional range, J. Aust. Math. Soc. Ser. A, 30 (1980), pp. 390-411. · Zbl 0469.90088
[4] J.M. Borwein and H. Wolkowicz, Facial reduction for a cone-convex programming problem, J. Aust. Math. Soc. Ser. A, 30 (1980), pp. 369-380. · Zbl 0464.90086
[5] J.M. 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, in Honor of Jonathan Borwein’s 60th Birthday, D.H. Bailey, H.H. Bauschke, P. Borwein, F. Garvan, M. Thera, J. Vanderwerff, and H. Wolkowicz, eds., Springer Proc. Math. Stat. 50, Springer, Cham, 2013, pp. 225-276. · 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, C. Roos, and T. Terlaky, Infeasible-start semidefinite programming algorithms via self-dual embeddings, in Topics in Semidefinite and Interior-Point Methods, Fields Inst. Commun. 18, American Mathematical Society, Providence, RI, 1998, pp. 215-236. · Zbl 0905.90155
[9] X.V. Doan, S. Kruk, and H. Wolkowicz, A robust algorithm for semidefinite programming, Optim. Methods Softw., 27 (2012), pp. 667-693. · Zbl 1274.90257
[10] D. Drusvyatskiy, G. Li, and H. Wolkowicz, A note on alternating projections for ill-posed semidefinite feasibility problems, Math. Program., 162, (2017), pp. 537-548. · Zbl 1360.90188
[11] D. Drusvyatskiy and H. Wolkowicz, The many faces of degeneracy in conic optimization, Found. Trends Optim., 3 (2017), pp. 77-170.
[12] K. Fan, On a theorem of Weyl concerning eigenvalues of linear transformations ii, Proc. Natl. Acad. Sci. USA, 36 (1950), pp. 31-35. · Zbl 0041.00602
[13] N.I.M. Gould, D.P. Robinson, and H. Sue Thorne, On solving trust-region and other regularised subproblems in optimization, Math. Program. Comput., 2 (2010), pp. 21-57. · Zbl 1193.65098
[14] A.J. Hoffman and H.W. Wielandt, The variation of the spectrum of a normal matrix, Duke Math., 20 (1953), pp. 37-39. · Zbl 0051.00903
[15] S. Kruk, M. Muramatsu, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, The Gauss-Newton direction in semidefinite programming, Optim. Methods Softw., 15 (2001), pp. 1-28. · Zbl 1017.90076
[16] Z-Q. Luo, J.F. Sturm, and S. Zhang, Conic convex programming and self-dual embedding, Optim. Methods Softw., 14 (2000), pp. 169-218. · Zbl 1072.90559
[17] A. Mohammad-Nezhad and T. Terlaky, On the identification of the optimal partition for semidefinite optimization, INFOR Inf. Syst. Oper. Res., 58 (2020), pp. 225-263. · Zbl 1509.90137
[18] R.D.C. Monteiro and M.J. Todd, Path-following methods, in Handbook of Semidefinite Programming, Kluwer Academic Publishers, Boston, MA, 2000, pp. 267-306. · Zbl 0957.90523
[19] Y. Nesterov and B.T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program., 108 (2006), pp. 177-205. · Zbl 1142.90500
[20] Y.E. Nesterov, M.J. Todd, and Y. Ye, Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems, Math. Program., 84 (1999), pp. 227-267. · Zbl 0971.90061
[21] G. Pataki, Strong duality in conic linear programming: Facial reduction and extended duals, in Computational and Analytical Mathematics, D. Bailey, H.H. Bauschke, F. Garvan, M. Thera, J. D. Vanderwerff, and H. Wolkowicz, eds., Springer Proc. Math. Stat. 50, Springer, New York, 2013, pp. 613-634. · Zbl 1282.90231
[22] F. Permenter, H. Friberg, and E. Andersen, Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach, SIAM J. Optim., 27 (2017), pp. 1257-1282. · Zbl 1368.90123
[23] F. Permenter and P. Parrilo, Partial facial reduction: Simplified, equivalent SDPs via approximations of the PSD cone, Math. Program., 171 (2018), pp. 1-54. · Zbl 1405.90098
[24] F.A. Potra and R. Sheng, A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming, SIAM J. Optim., 8 (1998), pp. 1007-1028. · Zbl 0917.65058
[25] R.T. Rockafellar, Convex Analysis, Princeton Math. Ser. 28 Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401
[26] J.E. Spingarn and R.T. Rockafellar, The generic nature of optimality conditions in nonlinear programming, Math. Oper. Res., 4 (1979), pp. 425-430. · Zbl 0423.90071
[27] S. Sremac, H.J. Woerdeman, and H. Wolkowicz, Maximum determinant positive definite Toeplitz completions, in Operator Theory, Analysis and the State Space Approach: In Honor of Rien Kaashoek, Birkhäuser/Springer, Cham, 2018, pp. 421-441. · Zbl 1426.15044
[28] S. Sremac, Error Bounds and Singularity Degree in Semidefinite Programming, UWSpace, 2020, http://hdl.handle.net/10012/15583.
[29] J.F. Sturm, Error bounds for linear matrix inequalities, SIAM J. Optim., 10 (2000), pp. 1228-1248. · Zbl 0999.90027
[30] L. Tunçel, Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, Fields Inst. Monogr. 27, American Mathematical Society, Providence, RI, 2010. · Zbl 1207.90005
[31] H. Waki and M. Muramatsu, Facial reduction algorithms for conic optimization problems, J. Optim. Theory Appl., 158 (2013), pp. 188-215. · Zbl 1272.90048
[32] H. Waki, M. Nakata, and M. Muramatsu, Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization, Comput. Optim. Appl., 53 (2012), pp. 823-844. · Zbl 1264.90162
[33] H. Wei and H. Wolkowicz, Generating and measuring instances of hard semidefinite programs, Math. Program., 125 (2010), pp. 31-45. · Zbl 1198.90317
[34] H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Handbook of Semidefinite Programming, Internat. Ser. Oper. Res. Management Sci. 27. Kluwer Academic Publishers, Boston, MA, 2000. · Zbl 0962.90001
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.