Re: KKT constraint preconditioner

On 2008-04-23 11:11:31 -0300, toni.lassila@xxxxxxxxx (Toni Lassila) said:

On Wed, 23 Apr 2008 06:31:08 -0700 (PDT), laverneth@xxxxxxxxx wrote:

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 ?

Why do you have linearly dependent constraints?

When getting rid of the redundent constraints is too much trouble the
usual trick is to add artificial varaibles that are constrained to be
zero. The artificials often have other uses.

x -> [ x_s, x_a ] where x_s are the existing structural variables and x_a
are the artificial variables. Then C -> [ C, I ]. The new C is of full
rank. And so on. Usually this is found in chapter 2 of books on LP.
If comes after chapter 1 reviews matrix algebra.



.

Relevant Pages

  • Re: KKT constraint preconditioner
    ... use a SAINV factorization on that system which has the great advantage ... indefinite and SAINV factorization breaks down because of exactly zero ... Has anyone an idea to avoid such zero pivots in the ... Why do you have linearly dependent constraints? ...
    (sci.math.num-analysis)
  • Re: KKT constraint preconditioner
    ... constraints on the n primal variables, ... use a SAINV factorization on that system which has the great advantage ... to avoid forming the matrix CT*C explicitly for reference). ... Why do you have linearly dependent constraints? ...
    (sci.math.num-analysis)
  • Re: KKT constraint preconditioner
    ... use a SAINV factorization on that system which has the great advantage ... to avoid forming the matrix CT*C explicitly for reference). ... Why do you have linearly dependent constraints? ... I have intersecting interfaces with constraints on dofs on each side ...
    (sci.math.num-analysis)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... = 3 is a feasible solution to this constraints set... ... Feasibility in a math program is not such a naively simple affair as ... Diaby's model is something like this (I have changed right sides to zero as ... general this approach may not result in obtaining optimal solution - afer ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... >> completely explained why the y_'s can be taken to be zero. ... >> the optimal solution must be in the subspace where each y_is ... Since these constraints are ... >> David Moews ...
    (comp.theory)
Loading