Optimization Online


A basis-free null space method for solving generalized saddle point problems

Douglas Mendes (gogotchi***at***gmail.com)
Maria A. Diniz-Ehrhardt (cheti***at***ime.unicamp.br)
Lucas G. Pedroso (pedroso.lgp***at***gmail.com)

Abstract: Using an augmented Lagrangian matrix approach, we analytically solve in this paper a broad class of linear systems that includes symmetric and nonsymmetric problems in saddle point form. To this end, some mild assumptions are made and a preconditioning is specially designed to improve the sensitivity of the systems before the calculation of their solutions. In this way, they can be properly employed for computational purposes. As an example of such a procedure, we develop a direct method for solving the symmetric saddle point problem. Then we show that our method is intrinsically related with the null space method, but it doesn't depend on finding a basis of the null space of the $(2,1)$ block of the saddle point systems. For this reason, the proposed method can be seen as a basis-free null space method. This method is also extended to nonsymmetric problems. To the best of our knowledge, the analytical solution of the nonsymmetric linear systems considered here is not known. So it is of major interest, since it can lead to the development of efficient algorithms, besides our own.

Keywords: direct methods, null space methods, saddle point problems, indefinite linear systems, analytical solutions, matrix inversion, conditioning, preconditioning

Category 1: Applications -- Science and Engineering (Optimization of Systems modeled by PDEs )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Institute of Mathematics, Statistics and Computing Science, University of Campinas, Campinas, 13083-859, SP, Brazil; Department of Mathematics, Federal University of Paraná, Curitiba, 81531-980, PR, Brazil; 08/Set/2015

Download: [PDF]

Entry Submitted: 09/08/2015
Entry Accepted: 09/08/2015
Entry Last Modified: 11/03/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society