not able to factorize matrices for which pivoted LDLs exist

[chriscoey]

Hi, I noticed in your tests at https://github.com/JuliaSmoothOptimizers/LDLFactorizations.jl/blob/06e217573bf8549d69f9fc34e3eb45b1e128d2b8/test/runtests.jl#L27 you have the matrix [0 1; 1 1]. With a different pivot this matrix has an LDL factorization. Matrices that look like this often arise in KKT conditions for the conic problems I am trying to solve. Is there a way to find a pivot that makes a pivoted LDL factorization exist? If not always, then at least fairly reliably?

[dpo]

Does this help: https://doi.org/10.1137/S0895479897321088 ?

[dpo]

Also if you slightly regularize the zero block (to make it negative definite), an LDL' factorization always exists and the performance of your code should not be affected much.

[chriscoey]

Thank you! So if I have a situation like [0 A'; A H] where H is PSD, you suggest replacing the zero block with say -1e-10 * I? is there a reason why negative definite works better than positive definite in the 0 block?

[dpo]

It makes the matrix quasi-definite. If H isn't posdef, you could also add a small multiple of the identity to it. You'll want to use -1.0e-8 * I (square root of machine epsilon) or larger. See, e.g., https://dx.doi.org/10.1007/s12532-012-0035-2 and references in there.

[chriscoey]

Thank you! That was very helpful. I think I know how to proceed, and I'll close the issue.

Would be great if this was automatic in your package. Not sure how feasible that would be.

[dpo]

It's not difficult, but there's the risk that I would shift a zero pivot the wrong way, adding or taking away curvature in the wrong place. However, as you might notice in the paper I quoted above, there are reasons related to optimization for introducing such regularizations at the optimization level. We did something similar for SDP, so I'm quite sure you could argue the same for conic optimization: https://dx.doi.org/10.1080/10556788.2016.1235708.

See also #9.

[dpo]

ps: it's automatic in https://github.com/JuliaSmoothOptimizers/LimitedLDLFactorizations.jl

[chriscoey]

Fascinating. I will think more carefully about the curvature point in the conic context. Thank you!

[chriscoey]

Another question: why have both this package and the limitedldlfactorizations.jl package?

[dpo]

A complete factorization using this package should be more efficient that with LimitedLDLFactorizations, and implementing limited factorizations in this one is probably more difficult.

[chriscoey]

Good to know. Thanks!