Exact Matrix Factorization Updates for Nonlinear Programming

References

• Abbott J, Mulders T (2001) How tight is Hadamard’s bound? Experiment. Math. 10(3):331–336.Crossref, Google Scholar
• Bailey DH, Borwein JM (2015) High-precision arithmetic in mathematical physics. Math. 3(2):337–367.Crossref, Google Scholar
• Bareiss EH (1968) Sylvester’s identity and multistep integer-preserving Gaussian elimination. Math. Comput. 22(103):565–578.Google Scholar
• Bareiss EH (1972) Computational solutions of matrix problems over an integral domain. IMA J. Appl. Math. 10(1):68–104.Crossref, Google Scholar
• Bennett JM (1965) Triangular factors of modified matrices. Numerische Mathematik 7(3):217–221.Crossref, Google Scholar
• Choi IC, Monma CL, Shanno DF (1990) Further development of a primal-dual interior point method. ORSA J. Comput. 2(4):304–311.Link, Google Scholar
• Conn AR, Gould NI, Toint PL (1991) Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Programming 50(1):177–195.Crossref, Google Scholar
• Cook W, Steffy DE (2011) Solving very sparse rational systems of equations. ACM Trans. Math. Software 37(4):1–21.Crossref, Google Scholar
• Cullum J, Brayton R (1979) Some remarks on the symmetric rank-one update. J. Optim. Theory Appl. 29(4):493–519.Crossref, Google Scholar
• Davis TA, Hager WW (2001) Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22(4):997–1013.Crossref, Google Scholar
• Davis TA, Hager WW (2005) Row modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 26(3):621–639.Crossref, Google Scholar
• Deng L (2010) Multiple-rank updates to matrix factorizations for nonlinear analysis and circuit design. PhD thesis. https://www.proquest.com/docview/2443877082?pq-origsite=gscholar&fromopenview=true.Google Scholar
• Diaz-Hernandez G, Fernández BR, Romano-Moreno E, Lara JL (2021) An improved model for fast and reliable harbour wave agitation assessment. Coastal. Engrg. 170:104011.Crossref, Google Scholar
• Drgoňa J, Klaučo M, Janeček F, Kvasnica M (2017) Optimal control of a laboratory binary distillation column via regionless explicit MPC. Comput. Chemical Engrg. 96:139–148.Crossref, Google Scholar
• Edmonds J (1967) Systems of distinct representatives and linear algebra. J. Res. National Bureau Standards Section B 71(4):241–245.Crossref, Google Scholar
• Elble JM, Sahinidis NV (2012) A review of the LU update in the simplex algorithm. Internat. J. Math. Oper. Res. 4(4):366–399.Crossref, Google Scholar
• Elsner L, Rozsa P (1981) On eigenvectors and adjoints of modified matrices. Linear Multilinear Algebra 10(3):235–247.Crossref, Google Scholar
• Escobedo AR (2016) Foundational factorization algorithms for the efficient roundoff-error-free solution of optimization problems. Unpublished PhD thesis, Texas A&M University, College Station, TX.Google Scholar
• Escobedo AR (2023) Exact matrix factorization updates for nonlinear programming. http://dx.doi.org/10.1287/ijoc.2021.0331.cd, https://github.com/INFORMSJoC/2021.0331.Google Scholar
• Escobedo AR, Moreno-Centeno E (2015) Roundoff-error-free algorithms for solving linear systems via Cholesky and LU factorizations. INFORMS J. Comput. 27(4):677–689.Link, Google Scholar
• Escobedo AR, Moreno-Centeno E (2017) Roundoff-error-free basis updates of LU factorizations for the efficient validation of optimality certificates. SIAM J. Matrix Anal. Appl. 38(3):829–853.Crossref, Google Scholar
• Escobedo AR, Moreno-Centeno E, Lourenco C (2018) Solution of dense linear systems via roundoff-error-free factorization algorithms: Theoretical connections and computational comparisons. ACM Trans. Math. Software 44(4):1–24.Crossref, Google Scholar
• Fine S, Scheinberg K (2001) Efficient SVM training using low-rank kernel representations. J. Machine Learn. Res. 2:243–264.Google Scholar
• Fletcher R, Matthews S (1985) A stable algorithm for updating triangular factors under a rank one change. Math. Comput. 45(172):471–485.Crossref, Google Scholar
• Fletcher R, Powell MJ (1974) On the modification of LDL factorizations. Math. Comput. 28(128):1067–1087.Google Scholar
• Gamrath G, Anderson D, Bestuzheva K, Chen WK, Eifler L, Gasse M, Gemander P, et al. (2020) The SCIP optimization suite 7.0.Google Scholar
• Gärtner B, Schönherr S (2000) An efficient, exact, and generic quadratic programming solver for geometric optimization. Proc. 16th Annual Sympos. Comput. Geometry (Association for Computing Machinery, New York), 110–118.Google Scholar
• Gill PE, Wong E (2015) Methods for convex and general quadratic programming. Math. Programming Comput. 7(1):71–112.Crossref, Google Scholar
• Gill PE, Saunders MA, Shinnerl JR (1996) On the stability of Cholesky factorization for symmetric quasidefinite systems. SIAM J. Matrix Anal. Appl. 17(1):35–46.Crossref, Google Scholar
• Gill PE, Golub GH, Murray W, Saunders MA (1974) Methods for modifying matrix factorizations. Math. Comput. 28(126):505–535.Crossref, Google Scholar
• Gill PE, Murray W, Saunders MA, Wright MH (1987) Maintaining LU factors of a general sparse matrix. Linear Algebra Appl. 88–89:239–270.Crossref, Google Scholar
• Gleixner A, Miltenberger M, Müller B (2015) SoPlex: The sequential object-oriented simplex class library, http://soplex.zib.de.Google Scholar
• Gleixner AM (2015) Exact and fast algorithms for mixed-integer nonlinear programming. Unpublished PhD thesis, Technischen Universit, Berlin.Google Scholar
• Griewank A, Walther A (2002) On constrained optimization by adjoint based quasi-Newton methods. Optim. Methods Software 17(5):869–889.Crossref, Google Scholar
• Griewank A, Walther A, Korzec M (2007) Maintaining factorized KKT systems subject to rank-one updates of Hessians and Jacobians. Optim. Methods Software 22(2):279–295.Crossref, Google Scholar
• Hammarling S, Lucas C (2008) Updating the QR factorization and the least squares problem. Technical report, University of Manchester, Manchester, UK.Google Scholar
• Herceg M, Jones C, Morari M (2015) Dominant speed factors of active set methods for fast MPC. Optimal Control Appl. Methods 36(5):608–627.Crossref, Google Scholar
• Herholz P, Alexa M (2018) Factor once: Reusing Cholesky factorizations on sub-meshes. ACM Trans. Graphics 37(6):1–9.Crossref, Google Scholar
• Herholz P, Sorkine-Hornung O (2020) Sparse Cholesky updates for interactive mesh parameterization. ACM Trans. Graphics 39(6):1–14.Crossref, Google Scholar
• Higham NJ (2009) Cholesky factorization. Wiley Interdisciplinary Rev. Comput. Statist. 1(2):251–254.Crossref, Google Scholar
• Higham NJ (2011) Gaussian elimination. Wiley Interdisciplinary Rev. Comput. Statist. 3(3):230–238.Crossref, Google Scholar
• Hock W, Schittkowski K (1980) Test examples for nonlinear programming codes. J. Optim. Theory Appl. 30(1):127–129.Crossref, Google Scholar
• Kiełbasiński A, Schwetlick H (1988) Numerische Lineare Algebra: Eine Computerorientierte Einführung (Deutscher Verlag der Wissenschaften, Berlin).Google Scholar
• Kirches C, Bock HG, Schlöder JP, Sager S (2011) A factorization with update procedures for a KKT matrix arising in direct optimal control. Math. Programming Comput. 3(4):319–348.Crossref, Google Scholar
• Knuth DE (1981) The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 2nd ed. (Addison-Wesley Professional, Boston).Google Scholar
• Lee HR, Saunders BD (1995) Fraction free Gaussian elimination for sparse matrices. J. Symbolic Comput. 19(5):393–402.Crossref, Google Scholar
• Lekhovytskiy DI (2018) Adaptive lattice filters for systems of space-time processing of non-stationary Gaussian processes. Radioelectronics Comm. Systems 61(11):477–514.Crossref, Google Scholar
• Lourenco C, Chen J, Moreno-Centeno E, Davis TA (2020) User guide for SLIP LU, a sparse left-looking integer preserving LU factorization version 1.0.2.Google Scholar
• Lourenco C, Escobedo AR, Moreno-Centeno E, Davis TA (2019) Exact solution of sparse linear systems via left-looking roundoff-error-free LU factorization in time proportional to arithmetic work. SIAM J. Matrix Anal. Appl. 40(2):609–638.Crossref, Google Scholar
• Lourenco CJ (2020) Efficient algorithms for the exact solution of sparse linear systems in time proportional to arithmetic work. Unpublished PhD thesis, Texas A&M University.Google Scholar
• Magron V, Constantinides G, Donaldson A (2017) Certified roundoff error bounds using semidefinite programming. ACM Trans. Math. Software 43(4):1–31.Crossref, Google Scholar
• Mehrotra S (1992) Deferred rank one updates in o (n3L) interior point algorithm. J. Oper. Res. Soc. Japan 35(4):345–352.Google Scholar
• Minka TP (2013) Expectation propagation for approximate Bayesian inference. Preprint, submitted January 10, https://arxiv.org/abs/1301.2294.Google Scholar
• Oh H, Hu Z (2018) Multiple-rank modification of symmetric eigenvalue problem. MethodsX 5:103–117.Crossref, Google Scholar
• Ojeda F, Suykens JA, De Moor B (2008) Low rank updated LS-SVM classifiers for fast variable selection. Neural Networks 21(2–3):437–449.Crossref, Google Scholar
• Olszanskyj SJ, Lebak JM, Bojanczyk AW (1994) Rank-k modification methods for recursive least squares problems. Numerical Algorithms 7(2):325–354.Crossref, Google Scholar
• Osborne M, Sun L (1999) A new approach to symmetric rank-one updating. IMA J. Numerical Anal. 19(4):497–507.Crossref, Google Scholar
• Pan PQ (2015) The variant of the face algorithm is unstable. Southeast University, Nanjing, China. https://www.researchgate.net/profile/Ping-Qi-Pan/publication/316285252_THE_VARIANT_OF_THE_FACE_ALGORITHM_IS_UNSTABLE/links/58fac6f90f7e9ba3ba50397b/THE-VARIANT-OF-THE-FACE-ALGORITHM-IS-UNSTABLE.pdf.Google Scholar
• Pan P-Q (2020) A new face algorithm using LU factorization for linear programming. https://optimization-online.org/wp-content/uploads/2020/11/8085.pdf.Google Scholar
• Puranik Y, Sahinidis NV (2017) Bounds tightening based on optimality conditions for nonconvex box-constrained optimization. J. Global Optim. 67(1–2):59–77.Crossref, Google Scholar
• Sarra SA (2011) Radial basis function approximation methods with extended precision floating point arithmetic. Engrg. Anal. Boundary Elements 35(1):68–76.Crossref, Google Scholar
• Schönhage DDA, Strassen V (1971) Schnelle multiplikation grosser zahlen. Comput. 7(3–4):281–292.Crossref, Google Scholar
• Seeger M (2008) Low rank updates for the Cholesky decomposition. Technical report, University of California, Berkeley, CA.Google Scholar
• Seeger M, Steinke F, Tsuda K (2007) Bayesian inference and optimal design in the sparse linear model. Artificial Intelligence and Statistics (PMLR, New York), 444–451.Google Scholar
• Stange P, Griewank A, Bollhöfer M (2007) On the efficient update of rectangular LU-factorizations subject to low rank modifications. Electronic Trans. Numerical Anal. 26:161–177.Google Scholar
• Weber T, Sager S, Gleixner A (2019) Solving quadratic programs to high precision using scaled iterative refinement. Math. Programming Comput. 11(3):421–455.Crossref, Google Scholar
• Wright S, Nocedal J (1999) Numerical Optimization (Springer Science, Berlin).Google Scholar
• Wunderling R (1996) Paralleler und objektorientierter simplex-algorithmus. Unpublished PhD thesis, Technische Universität Berlin, Germany.Google Scholar