| Citation: |
Gül Karaduman. ITERATIVE METHOD FOR RANK-DEFICIENT (2,1)-BLOCK KKT SYSTEMS[J]. Journal of Applied Analysis & Computation, 2025, 15(5): 3113-3127. doi: 10.11948/20250010
|
ITERATIVE METHOD FOR RANK-DEFICIENT (2,1)-BLOCK KKT SYSTEMS
-
Abstract
Karush-Kuhn-Tucker (KKT) systems are widely used in scientific and engineering problems. They are characterized by a 2-by-2 block structure coefficient matrix that exhibits various features, such as sparsity, symmetry, non-symmetry, singularity, and nonsingularity. Solving singular (2,1)-block KKT systems presents significant computational challenges due to their inherent complexity. To address this challenge, an iterative method has been introduced explicitly for addressing singular (2,1)-block KKT systems. The proposed method reduces the system size by using only maximum linearly independent rows of (2,1) block matrices and effectively handles the singularity by transforming the row deficiency problem into a reduced form. The effectiveness and efficiency of the proposed iterative method are verified using numerical experiments with various matrices. It has demonstrated the capacity to provide definitive solutions for singular KKT systems and improve computing performance across multiple applications.
-
Keywords:
- Rank deficient /
- iterative solver /
- KKT systems /
- numerical optimization /
- Krylov subspace solvers
-
-
References
[1] H. Aslani and D. Khojasteh Salkuyeh, On the preconditioned APSS iterative method for singular coupled saddle point problems, Mathematical Communications, 2024, 29(1), 21–37. [2] S. Axler, Linear Algebra Done Right, Springer, New York, 2024. DOI: 10.1007/978-3-031-41026-0. [3] M. Benzi, G. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numerica, 2005, 14, 1–137. DOI: 10.1017/S0962492904000212. [4] L. Bergamaschi, J. Gondzio and G. Zilli, Preconditioning indefinite systems in interior point methods for optimization, Computational Optimization and Applications, 2004, 28, 149–171. DOI: 10.1023/B:COAP.0000026882.34332.1b. [5] Y. Cao and S. Yi, A class of Uzawa-PSS iteration methods for nonsingular and singular non-Hermitian saddle point problems, Applied Mathematics and Computation, 2016, 275, 41–49. DOI: 10.1016/j.amc.2015.11.049. [6] G. Cheng and J. C. Li, Class of Uzawa-NPHSS iteration method for solving nonsingular and singular saddle point problems, Linear and Multilinear Algebra, 2022, 70(14), 2706–2738. DOI: 10.1080/03081087.2020.1811628. [7] M. Cui, A sufficient condition for the convergence of the inexact Uzawa algorithm for saddle point problems, Journal of Computational and Applied Mathematics, 2002, 139(2), 189–196. DOI: 10.1016/S0377-0427(01)00430-7. [8] R. Fletcher and T. Johnson, On the stability of null-space methods for KKT systems, SIAM Journal on Matrix Analysis and Applications, 1997, 18(4), 938–958. DOI: 10.1137/S0895479896297732. [9] D. C. Fong and M. Saunders, LSMR: An iterative algorithm for sparse least-squares problems, SIAM Journal on Scientific Computing, 2011, 33(5), 2950–2971. DOI: 10.1137/10079687X. [10] M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, North-Holland, Amsterdam, 1983. [11] G. H. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis, 1965, 2(2), 205–224. DOI: 10.1137/0702016. [12] G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, 2013. [13] R. Kress, Tikhonov Regularization. In: Linear Integral Equations, Applied Mathematical Sciences, vol 82. Springer, Berlin, Heidelberg, 1989. DOI: 10.1007/978-3-642-97146-4_16 .[14] H. W. Kuhn and A. W Tucker, Nonlinear Programming, in: Giorgi, G. Kjeldsen, T. (eds) Traces and Emergence of Nonlinear Programming, Birkhäuser, Basel, 2014. DOI: 10.1007/978-3-0348-0439-4_11 .[15] L. Liao, G. Zhang and X. Wang. Preconditioned iterative method for nonsymmetric saddle point linear systems, Computers & Mathematics with Applications, 2021, 98, 69–80. DOI: 10.1016/j.camwa.2021.07.002. [16] S. Regev, N. Y. Chiang, E. Darve, C. G. Petra, M. A. Saunders, K. Świrydowicz and S. Peleš, HyKKT: A hybrid direct-iterative method for solving KKT linear systems, Optimization Methods and Software, 2023, 38(2), 332–355. DOI: 10.1080/10556788.2022.2124990. [17] U. Rosolia, Y. Lian, E. T. Maddalena, G. Ferrari-Trecate and C. N. Jones, On the optimality and convergence properties of the iterative learning model predictive controller, IEEE Transactions on Automatic Control, 2022, 68(1), 556–563. [18] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, 1986, 7(3), 856–869. DOI: 10.1137/0907058. [19] V. Sarin, Efficient Iterative Methods for Saddle Point Problems, Ph. D. Thesis, University of Illinois at Urbana-Champaign, ProQuest Dissertations Publishing, 1997. [20] M. A. Saunders, Cholesky-based methods for sparse least squares: The benefits of regularization, Linear and Nonlinear Conjugate Gradient-Related Methods, 1996, 100, 92–100. [21] D. S. Watkins, Fundamentals of Matrix Computations, Wiley, New York, 2002. DOI: 10.1002/0471249718. [22] M. Xiao, S. Bo and Z. Wu, Multiple greedy quasi-newton methods for saddle point problems, 6th International Conference on Data-Driven Optimization of Complex Systems (DOCS) IEEE, 2024, 749–754. DOI: 10.1109/DOCS63458.2024.10704381 .[23] X. Y. Xiao and C. S. Wang, A block upper triangular preconditioner with two parameters for saddle-point problems, Computers & Mathematics with Applications, 2024, 160, 15–29. DOI: 10.1016/j.camwa.2024.02.015. -
-
Figures(1) / Tables(3)
Export File
Citation
Gül Karaduman. ITERATIVE METHOD FOR RANK-DEFICIENT (2,1)-BLOCK KKT SYSTEMS[J]. Journal of Applied Analysis & Computation, 2025, 15(5): 3113-3127. doi: 10.11948/20250010
Format
Content
DownLoad:
-
Figure 1.
Left: Relative residual
$ vs. $ $ \mathcal{K} $ $ A, B_1 $ $ B_2\in\mathbb{R}^{m\times {n}} $ $ \tt{GL6\_D\_10} $ $ \tt{GL6\_D\_9} $ $ \tt{GL7d26} $ $ \tt{lp\_ship12s} $ $ vs. $ $ \mathcal{K} $ $ A, B_1 $ $ B_2\in\mathbb{R}^{m\times {n}} $ $ \tt{lp\_scorpion} $ $ \tt{GL6\_D\_8} $ $ \tt{N\_biocarta} $ $ \tt{N\_pid} $