A Semismooth Newton-Type Method for the Nearest Doubly Stochastic Matrix Problem

References

• [1] Al-Homidan S, Wolkowicz H (2005) Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming. Linear Algebra Appl. 406:109–141.Crossref, Google Scholar
• [2] Bai Z, Chu D, Tan R (2007) Computing the nearest doubly stochastic matrix with a prescribed entry. SIAM J. Sci. Comput. 29(2):635–655.Crossref, Google Scholar
• [3] Barrios J, Cruz JB, Ferreira OP, Németh SZ (2016) A semi-smooth Newton method for a special piecewise linear system with application to positively constrained convex quadratic programming. J. Comput. Appl. Math. 301:91–100.Crossref, Google Scholar
• [4] Bertsimas D, Tsitsiklis J (1997) Introduction to Linear Optimization (Athena Scientific, Belmont, MA).Google Scholar
• [5] Best M (2017) Quadratic Programming with Computer Programs, Advances in Applied Mathematics (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• [6] Boland N, Goh C, Mees A (1991) An algorithm for solving quadratic network flow problems. Appl. Math. Lett. 4(4):61–64.Crossref, Google Scholar
• [7] Borwein J, Lewis A (1992) Partially finite convex programming, part I, duality theory. Math. Programming 57:15–48.Crossref, Google Scholar
• [8] Borwein J, Wolkowicz H (1986) A simple constraint qualification in infinite-dimensional programming. Math. Programming 35:83–96.Crossref, Google Scholar
• [9] Brualdi R (1988) Some applications of doubly stochastic matrices. Linear Algebra Appl. 107:77–100.Crossref, Google Scholar
• [10] Brualdi R, Ryser H (1991) Combinatorial matrix theory. Encyclopedia of Mathematics and Its Applications (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [11] Brugnano L, Casulli V (2008) Iterative solution of piecewise linear systems. SIAM J. Sci. Comput. 30(1):463–472.Crossref, Google Scholar
• [12] Brugnano L, Casulli V (2009) Iterative solution of piecewise linear systems and applications to flows in porous media. SIAM J. Sci. Comput. 31(3):1858–1873.Crossref, Google Scholar
• [13] Brugnano L, Sestini A (2009) Iterative solution of piecewise linear systems for the numerical solution of obstacle problems. Preprint, submitted December 16, https://arxiv.org/abs/0912.3222.Google Scholar
• [14] Chen J, Agarwal RP (2010) On Newton-type approach for piecewise linear systems. Linear Algebra Appl. 433(7):1463–1471.Crossref, Google Scholar
• [15] Chen X, Qi H, Tseng P (2003) Analysis of nonsmooth symmetric-matrix-valued functions with applications to semidefinite complementarity problems. SIAM J. Optim. 13(4):960–985.Crossref, Google Scholar
• [16] Clarke F (1990) Optimization and Nonsmooth Analysis, Classics in Applied Mathematics, vol. 5, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [17] Clarke FH (1993–1994) Analyse non lisse et optimisation, Cours de 3ème cycle, Ecole doctorale de mathématiques, Université Paul Sabatier.Google Scholar
• [18] Cook W, Cunningham W, Pulleyblank W, Schrijver A (1998) Combinatorial Optimization, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons Inc., New York).Google Scholar
• [19] Cottle R, Pang JS, Stone R (2009) The Linear Complementarity Problem, Classics in Applied Mathematics, vol. 60 (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [20] Cvetković D, Rowlinson P, Simić SK (2007) Signless Laplacians of finite graphs. Linear Algebra Appl. 423(1):155–171.Crossref, Google Scholar
• [21] Dan H, Yamashita N, Fukushima M (2002) Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions. Optim. Methods Software 17(4):605–626.Crossref, Google Scholar
• [22] den Hertog D (1994) Interior Point Approach to Linear, Quadratic and Convex Programming: Algorithms and Complexity, Mathematics and Its Applications, vol. 277 (Kluwer Academic Publishers Group, Dordrecht, Netherlands).Crossref, Google Scholar
• [23] Deutsch F, Li W, Ward JD (1997) A dual approach to constrained interpolation from a convex subset of Hilbert space. J. Approximation Theory 90(3):385–414.Crossref, Google Scholar
• [24] Fan J, Yuan Y (2005) On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption. Comput. 74:23–39.Crossref, Google Scholar
• [25] Fernández J, Verón M (2017) Newton’s Method: An Updated Approach of Kantorovich’s Theory (Birkhäuser).Crossref, Google Scholar
• [26] Fischer A, Kanzow C (1996) On finite termination of an iterative method for linear complementarity problems. Math. Programming 74:279–292.Crossref, Google Scholar
• [27] Gauvin J (1977) A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming. Math. Programming 12:136–138.Crossref, Google Scholar
• [28] Goh C, Boland N, Mees A (1992) An algorithm for solving quadratic cost network flow optimization problems. Optimization, vol. 1–2 (World Scientific Publishing, River Edge, NJ), 284–293.Google Scholar
• [29] Graham N, Hu H, Im H, Li X, Wolkowicz H (2022) A restricted dual Peaceman-Rachford splitting method for a strengthened DNN relaxation for QAP. INFORMS J. Comput. 34(4):2125–2143.Link, Google Scholar
• [30] Grant M, Boyd S, Ye Y (2006) Disciplined convex programming. Global Optimization, Nonconvex Optimization and Its Applications, vol. 84 (Springer, New York), 155–210.Crossref, Google Scholar
• [31] He B, Xu M, Yuan X (2011) Solving large-scale least squares semidefinite programming by alternating direction methods. SIAM J. Matrix Anal. Appl. 32(1):136–152.Crossref, Google Scholar
• [32] Hessert R, Mallik S (2021) Moore-Penrose inverses of the signless Laplacian and edge-Laplacian of graphs. Discrete Math. 344(8):112451.Crossref, Google Scholar
• [33] Hintermüller M, Ito K, Kunisch K (2002) The primal-dual active set strategy as a semismooth Newton method. SIAM J. Optim. 13(3):865–888.Crossref, Google Scholar
• [34] Hoffman A (1952) On approximate solutions of systems of linear inequalities. J. Res. National Bureau Standards 49(4):263–265.Crossref, Google Scholar
• [35] Hueso J, Martinez E, Torregrosa J (2009) Modified Newton’s method for systems of nonlinear equations with singular Jacobian. J. Comput. Appl. Math. 224(1):77–83.Crossref, Google Scholar
• [36] Hungerländer P, Rendl F (2016) An infeasible active set method with combinatorial line search for convex quadratic problems with bound constraints. Technical Report TR–AAUK–M–O–16–08–03, Optimization Group, Alpen-Adria Universität Klagenfurt, Mathematics, Austria.Google Scholar
• [37] Imbert C (2002) Support functions of clarke’s generalized jacobian and of its plenary hull. Nonlinear Anal. Theory Methods Appl. 29(8):1111–1125.Crossref, Google Scholar
• [38] Kelley C, Xue Z (1993) Inexact Newton methods for singular problems. Optim. Methods Software 2(3–4):249–267.Crossref, Google Scholar
• [39] Lawson C, Hanson R (1995) Solving Least Squares Problems, Classics in Applied Mathematics, vol. 15 (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [40] Levenberg K (1944) A method for the solution of certain problems in least squares. Quart. Appl. Math. 2(2):164–168.Crossref, Google Scholar
• [41] Li X, Sun D, Toh K (2020) On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope. Math. Programming 179:419–446.Crossref, Google Scholar
• [42] Louck JD (1997) Doubly stochastic matrices in quantum mechanics. Foundations Phys. 27:1085–1104.Crossref, Google Scholar
• [43] Malick J, Sendov HS (2006) Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices. Set-Valued Anal. 14:273–293.Crossref, Google Scholar
• [44] Mangasarian O, Fromovitz S (1967) The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17(1):37–47.Crossref, Google Scholar
• [45] Marcus M (1960) Some properties and applications of doubly stochastic matrices. Amer. Math. Monthly 67(3):215–221.Crossref, Google Scholar
• [46] Marquardt D (1963) An algorithm for least-squares estimation of nonlinear inequalities. SIAM J. Appl. Math. 11(2):431–441.Crossref, Google Scholar
• [47] Micchelli C, Smith P, Swetits J, Ward J (1985) Constrained Lp approximation Constructive Approximation 1:93–102.Google Scholar
• [48] Mordukhovich BS (2006) Variational Analysis and Generalized Differentiation I: Basic Theory, vol. 330 (Springer Science & Business Media, New York).Crossref, Google Scholar
• [49] Mosek ApS (2019) The MOSEK optimization toolbox for MATLAB manual. Version 9.0. http://docs.mosek.com/9.0/toolbox/index.html.Google Scholar
• [50] Qi H, Sun D (2006) A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28(2):360–385.Crossref, Google Scholar
• [51] Qi L, Sun J (1993) A nonsmooth version of Newton’s method. Math. Programming 58:353–367.Crossref, Google Scholar
• [52] Rademacher H (1919) Uber partielle und totale differenzierbarkeit i. Mathematische Annalen 89:340–359.Crossref, Google Scholar
• [53] Smith P, Wolkowicz H (1986) A nonlinear equation for linear programming. Math. Programming 34:235–238.Crossref, Google Scholar
• [54] Sun D, Sun J (2002) Semismooth matrix-valued functions. Math. Oper. Res. 27(1):150–169.Link, Google Scholar
• [55] Tam B, Wu S (2010) On the reduced signless Laplacian spectrum of a degree maximal graph. Linear Algebra Appl. 432(7):1734–1756.Crossref, Google Scholar
• [56] Ulbrich M (2011) Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces (SIAM, Philadelphia).Crossref, Google Scholar
• [57] Yamashita N, Fukushima M (2001) On the rate of convergence of the Levenberg-Marquardt method. Topics in Numerical Analysis (Springer, Berlin), 239–249.Crossref, Google Scholar
• [58] Yuan X, Yan S (2011) A finite Newton algorithm for non-degenerate piecewise linear systems. Proc. 14th Internat. Conf. Artificial Intelligence Statist. JMLR Workshop Conf. Proc., 841–854.Google Scholar