On Computing the Nonlinearity Interval in Parametric Semidefinite Optimization

References

• [1] Adler I, Monteiro RDC (1992) A geometric view of parametric linear programming. Algorithmica 8:161–176.Crossref, Google Scholar
• [2] Alfakih A, Wolkowicz H (2000) Matrix completion problems. Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (Springer, New York), 533–545.Crossref, Google Scholar
• [3] Alizadeh F, Haeberly JPA, Overton ML (1997) Complementarity and nondegeneracy in semidefinite programming. Math. Programming 77:111–128.Crossref, Google Scholar
• [4] Alizadeh F, Haeberly JPA, Overton ML (1998) Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Optim. 8(3):746–768.Crossref, Google Scholar
• [5] Basu S, Pollack R, Roy MF (2006) Algorithms in Real Algebraic Geometry (Springer, New York).Crossref, Google Scholar
• [6] Bates DJ, Hauenstein JD, Peterson C, Sommese AJ (2009) A numerical local dimension test for points on the solution set of a system of polynomial equations. SIAM J. Numer. Anal. 47(5):3608–3623.Crossref, Google Scholar
• [7] Bates DJ, Hauenstein JD, Sommese AJ, Wampler CW (2006) Bertini: Software for numerical algebraic geometry. Accessed August 26, 2019, https://bertini.nd.edu/.Google Scholar
• [8] Bates DJ, Hauenstein JD, Sommese AJ, Wampler CW (2008) Adaptive multiprecision path tracking. SIAM J. Numer. Anal. 46(2):722–746.Crossref, Google Scholar
• [9] Bates DJ, Sommese AJ, Hauenstein JD, Wampler CW (2013) Numerically Solving Polynomial Systems with Bertini (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [10] Berkelaar AB, Jansen B, Roos C, Terlaky T (1996) Sensitivity analysis in (degenerate) quadratic programming. Technical Report 96-26, Delft University of Technology, Delft, Netherlands.Google Scholar
• [11] Berkelaar AB, Roos C, Terlaky T (1997) The optimal set and optimal partition approach to linear and quadratic programming. Gal T, Greenberg HJ, eds. Advances in Sensitivity Analysis and Parametric Programming. International Series in Operations Research & Management Science, vol. 6 (Springer, New York), 159–202.Crossref, Google Scholar
• [12] Blekherman G, Parrilo PA, Thomas RR (2012) Semidefinite Optimization and Convex Algebraic Geometry (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [13] Bonnans JF, Ramírez CH (2005) Perturbation analysis of second-order cone programming problems. Math. Programming 104:205–227.Crossref, Google Scholar
• [14] Bonnans JF, Shapiro A (1998) Optimization problems with perturbations: A guided tour. SIAM Rev. 40(2):228–264.Crossref, Google Scholar
• [15] Bonnans JF, Shapiro A (2000) Perturbation Analysis of Optimization Problems (Springer, New York).Crossref, Google Scholar
• [16] Butcher JC (2003) Numerical Methods for Ordinary Differential Equations (John Wiley & Sons, New York).Crossref, Google Scholar
• [17] Cheung YL, Schurr S, Wolkowicz H (2013) Preprocessing and regularization for degenerate semidefinite programs. Bailey DH, Bauschke HH, Borwein P, Garvan F, Théra M, Vanderwerff JD, Wolkowicz H, eds. Computational and Analytical Mathematics (Springer, New York), 251–303.Crossref, Google Scholar
• [18] Cifuentes D, Agarwal S, Parrilo P, Thomas R (2017) On the local stability of semidefinite relaxations. Preprint, submitted October 11, https://arxiv.org/abs/1710.04287.Google Scholar
• [19] Davidenko D (1953) On a new method of numerical solution of systems of nonlinear equations (in Russian). Doklady Akademii Nauk USSR 88:601–602.Google Scholar
• [20] de Klerk E (2002) Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Applied Optimization, vol. 65 (Springer, New York).Crossref, Google Scholar
• [21] de Klerk E, Roos C, Terlaky T (1997) Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper. Res. Lett. 20(5):213–221.Crossref, Google Scholar
• [22] de Klerk E, Roos C, Terlaky T (1998) Infeasible-start semidefinite programming algorithms via self-dual embeddings. Pardalos PM, Wolkowicz H, eds. Topics in Semidefinite and Interior Point Methods. Fields Institute Communications, vol. 18 (American Mathematical Society, Providence, RI), 215–236.Crossref, Google Scholar
• [23] Dieudonné J (1960) Foundations of Modern Analysis (Academic Press, Inc., New York).Google Scholar
• [24] Fiacco AV (1976) Sensitivity analysis for nonlinear programming using penalty methods. Math. Programming 10:287–311.Crossref, Google Scholar
• [25] Fiacco AV (1983) Introduction to Sensitivity and Stability Analysis in Nonlinear Programming (Academic Press, Inc., New York).Google Scholar
• [26] Fiacco AV, McCormick GP (1990) Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [27] Goldfarb D, Scheinberg K (1999) On parametric semidefinite programming. Appl. Numer. Math. 29(3):361–377.Crossref, Google Scholar
• [28] Haeberly JP (1998) Remarks on nondegeneracy in mixed semidefinite-quadratic programming. Unpublished memorandum, available from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.43.7501&rep=rep1&type=pdf.Google Scholar
• [29] Halická M, de Klerk E, Roos C (2002) On the convergence of the central path in semidefinite optimization. SIAM J. Optim. 12(4):1090–1099.Crossref, Google Scholar
• [30] Hauenstein JD, Sommese AJ (2017) What is numerical algebraic geometry? J. Symbolic Comput. 79(3):499–507.Crossref, Google Scholar
• [31] Hauenstein JD, Tang T (2018) On semidefinite programming under perturbations with unknown boundaries. Working paper, University of Notre Dame, Notre Dame, IN. Available at https://www3.nd.edu/~jhauenst/preprints/htSDPperturb.pdf.Google Scholar
• [32] Hauenstein JD, Wampler CW (2013) Isosingular sets and deflation. Foundations Comput. Math. 13(3):371–403.Crossref, Google Scholar
• [33] Hauenstein JD, Haywood I, Liddell AC Jr (2014) An a posteriori certification algorithm for Newton homotopies. Proc. 39th Internat. Sympos. Symbolic Algebraic Comput. (Association for Computing Machinery, New York), 248–255.Google Scholar
• [34] Hogan WW (1973) Point-to-set maps in mathematical programming. SIAM Rev. 15(3):591–603.Crossref, Google Scholar
• [35] Horn RA, Johnson CR (2012) Matrix Analysis, 2 ed. (Cambridge University Press, New York).Crossref, Google Scholar
• [36] Jansen B, Roos C, Terlaky T (1993) An interior point method approach to postoptimal and parametric analysis in linear programming. Technical Report 92-21, Delft University of Technology, Delft, Netherlands.Google Scholar
• [37] Kalaba RE, Zagustin E, Holbrow W, Huss R (1977) A modification of Davidenko’s method for nonlinear systems. Comput. Math. Appl. 3(4):315–319.Crossref, Google Scholar
• [38] Kojima M (1980) Strongly stable stationary solutions in nonlinear programs. Robinson SM, ed. Analysis and Computation of Fixed Points (Academic Press, New York), 93–138.Crossref, Google Scholar
• [39] Krantz SG, Parks HR (2002) A Primer of Real Analytic Functions (Springer, New York).Crossref, Google Scholar
• [40] Lee JM (2013) Introduction to Smooth Manifolds (Springer, New York).Google Scholar
• [41] Mohammad-Nezhad A, Terlaky T (2020) On the identification of the optimal partition for semidefinite optimization. INFOR Inform. Systems Oper. Res. 58(2):225–263.Crossref, Google Scholar
• [42] Mohammad-Nezhad A, Terlaky T (2020) Parametric analysis of semidefinite optimization. Optimization 69(1):187–216.Crossref, Google Scholar
• [43] Mohammad-Nezhad A, Terlaky T (2021) On the sensitivity of the optimal partition for parametric second-order conic optimization. Math. Programming 189:491–525.Crossref, Google Scholar
• [44] Munkres JR (2000) Topology (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• [45] Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [46] Nie J, Ranestad K, Sturmfels B (2010) The algebraic degree of semidefinite programming. Math. Programming 122:379–405.Crossref, Google Scholar
• [47] Ortega J, Rheinboldt W (1970) Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, Inc., San Diego).Google Scholar
• [48] Robinson SM (1982) Generalized equations and their solutions, part II: Applications to nonlinear programming. Guignard M, ed. Optimality and Stability in Mathematical Programming (Springer, Berlin), 200–221.Crossref, Google Scholar
• [49] Rockafellar R (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [50] Rockafellar R, Dontchev A (2014) Implicit Functions and Solution Mappings: A View from Variational Analysis (Springer, New York).Google Scholar
• [51] Rockafellar R, Wets RJB (2009) Variational Analysis, vol. 317 (Springer, New York).Google Scholar
• [52] Shapiro A (1997) First and second order analysis of nonlinear semidefinite programs. Math. Programming 77:301–320.Crossref, Google Scholar
• [53] Sommese AJ, Wampler CW (2005) The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (World Scientific, Singapore).Crossref, Google Scholar
• [54] Sylvester JJ (1851) LX. On a remarkable discovery in the theory of canonical forms and of hyperdeterminants. Lond. Edinburgh, Dublin Philos. Magazine J. Sci. 2(12):391–410.Crossref, Google Scholar
• [55] Todd MJ (2001) Semidefinite optimization. Acta Numerica 10:515–560.Crossref, Google Scholar
• [56] Wampler CW, Hauenstein JD, Sommese AJ (2011) Mechanism mobility and a local dimension test. Mechanism Machine Theory 46(9):1193–1206.Crossref, Google Scholar
• [57] Yildirim EA (2004) Unifying optimal partition approach to sensitivity analysis in conic optimization. J. Optim. Theory Appl. 122:405–423.Crossref, Google Scholar