Barrier method for problems with a block structure of the minimization matrix

[sergey-mogilnikov-kpbs]

It seems there is a issue in Cholesky decomposition, but I am not sure ...

I have tried to solve large QP problems. Quadratic matrix has a block's structure. Any block is full dense matrix. Each submatrix (block) is on the diagonal of the matrix. Illustrative example as follow:

NAME Quad3
ROWS
 L  r1
 L  r2
 N  r3
COLUMNS
    x1        r1                  -1   r2                  -1
    x2        r1                  -2   r2                  -1
    x3        r1                  -3   r2                  -1
    x3        r3                   2
    x4        r1                  -4   r2                  -1
    x4        r3                 0.6
    x5        r1                  -5   r2                  -1
    x5        r3                 2.2
    x6        r1                  -6   r2                  -1
    x6        r3                   1
    x7        r1                  -7   r2                  -1
    x7        r3                 4.8
    x8        r1                  -8   r2                  -1
    x8        r3               -2.88
    x9        r1                  -9   r2                  -1
    x9        r3               -0.72
    x10       r1                 -10   r2                  -1
    x10       r3                -9.6
RHS
    RHS1      r1                -100   r2                 -13
    RHS1      r3               -3.44
BOUNDS
 UP BND1      x1               1E+10
 UP BND1      x2               1E+10
 UP BND1      x3               1E+10
 UP BND1      x4               1E+10
 UP BND1      x5               1E+10
 UP BND1      x6               1E+10
 UP BND1      x7               1E+10
 UP BND1      x8               1E+10
 UP BND1      x9               1E+10
 UP BND1      x10              1E+10
QUADOBJ
    x1  x1  2
    x2  x2  2
    x3  x3  2
    x3  x4  0.6
    x3  x5  0.2
    x3  x6  -1
    x4  x4  0.18
    x4  x5  0.06
    x4  x6  -0.3
    x5  x5  2.02
    x5  x6  1.9
    x6  x6  2.5
    x7  x7  10
    x7  x8  -4.8
    x7  x9  -1.2
    x7  x10  -16
    x8  x8  2.88
    x8  x9  0.72
    x8  x10  9.6
    x9  x9  0.18
    x9  x10  2.4
    x10  x10  32
ENDATA

There are 4 blocks:

• block 1: variable x1
• block 2: variable x2
• block 3: variables x3, x4, x5, x6
• block 4: variables x7, x8, x9, x10

As I undestand each block can be decomposed independantly for this type of matrix...
So, Cholesky matrix should had 22 or less the 22 nonzero elements. ?

Clp claims that "35 elements in sparse Cholesky, flop count 189". What is a problem? Sorting? Or it issue evaluation numbers of nonzero elements? It is an issue for large problem...

---

Real problems have ~6 millions nonzero in Q matrix.

• Clp with barrier menthod claims about Cholesky 1E09 nonzero elements. Solver takes 12GB of memory and hang up.
• Some problems were solved with simplex method. Parameter slp was used; but I can't find it in clp on ? command. Why?
• Clp with Mumps claims that "finish coding MUMPS KKT!". Swiching kkt off does not help. Can it be really used?

[jjhforrest]

Not an expert in barrier or KKT methods (which need to be used for Quadratic objectives). Using KKT the Cholesky has 14 rows and 35 seems reasonable. The default ordering is pretty bad so I may look into finishing coding for Mumps KKT (and Ufl).