Re: KKT constraint preconditioner


In article <9ab618ca-5b8e-43c3-a8db-149bb14e10d3@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
laverneth@xxxxxxxxx writes:
I want to solve a full KKT system of the form
[A C ]
[CT 0 ]
with A is a n,n matrix, and C is a n,m matrix representing m
constraints on the n primal variables,
and CT is its transpose.

I am trying to solve this method with an iterative method (namely
BiCGSTAB), and thus I need a good preconditioner.
Often, the constraint precondionner is described in the litterature
and I tried to implement it.
It involves approximate solves with the m,m system CT *C. I tried to
use a SAINV factorization on that system which has the great advantage
to avoid forming the matrix CT*C explicitly (see 1) for reference).

However, in my case C has not full column rank and Ct*C is therefore
indefinite and SAINV factorization breaks down because of exactly zero
pivots. Has anyone an idea to avoid such zero pivots in the
factorization ? Should I use an other factorization ?

Anyway in some special cases (I am dealing with structural mechanics
problems) C may have full column rank and the iterative method works
very well.

Thank you very much for any (possibly helpfull ;-)) comment !

References:
1) Preconditioning KKT systems: meyer.math.ncsu.edu/Meyer/PS_Files/
KKT.pdf

if C is rank deficinet, then the KKT matrix is singualr, hence
your system, since inhomogeneous, might have no solution at all.
In your special case which you described a help might be to eliminate
one of the two constraints whose gradients are (almost) parallel
Gordon Sande already gave you the tip
"use elastic mode" (this is the term used in the LP -context and
which now is also used in nonlinear programming ,for example SNOPT
and donlp2 use this) : you add artificial variables s(i) and force them
to become zero by adding them to the objective function and making them
bounded from below :
f(x) -> f(x) + K*sum s(i) K fixed sufficiently large
(larger than the duals of the original problem)
s(i) >=0

c_j(x) = 0 -> c_j(x)+s(i)-s(i+1) =0
c_k(x) >=0 -> c_k(x)+ s(i) >=0 (yes, "+")

This trick makes the problem always feasible and always Mangasarian-Fromowitz-regular.
but, of course, you must treat the positivity constraint special by projection
not as an active constraint in the KKT system, since then you are back at
rank deficiency (as said: only MFCQ regular, not LICQ)
hth
peter


.