What to do about matrix factorisations

[odow]

This issue is a placeholder for us to discuss at the next monthly developer call.

See #2967

This is a follow-up to #1971.

x-ref #2972
x-ref #2967
x-ref #2961
x-ref #2959
x-ref #2956
x-ref #2933

The problem

The QuadtoSOCBridge converts $\frac{1}{2} x' Q x + a^\top x + b \le 0$ into $|U x|_2^2 \le -2 (a^\top x + b)$ aka $[a^\top x + b; -2; Ux] \in RSOC$ where $Q = U^\top U$ for $Q \succeq 0$.

The main difficulty is $Q = U^\top U$ for $Q \succeq 0$.

We currently use a sparse Cholesky in the form of:

factor = LinearAlgebra.cholesky(
    SparseArrays.sparse(LinearAlgebra.Symmetric(Q)),
)

The main downside is that this can fail when $Q$ has a zero Eigen value. We'd like alternatives that are more robust.

Alternatives

LDLFactorizations

https://github.com/JuliaSmoothOptimizers/LDLFactorizations.jl

Pros: it's part of JSO
Cons: LGPL. JuliaSmoothOptimizers/LDLFactorizations.jl#142

CliqueTrees

https://github.com/AlgebraicJulia/CliqueTrees.jl

Pros: quite robust. active developer. MIT
Cons: bus factor = 1

LinearAlgebra.eigen

Pros: robust
Cons: won't work for models with N > 10k or so

Are people solving problems with very large quadratic constraints?

Others

???

Questions

Given there are multiple alternatives, the question is how to integrate them.

• Should we add packages as an explicit dependency? Currently decided "no"
• Should we add packges using Pkg's extension mechanism? Currently decided "yes"
• Which packages should we added?
• What should the order be?
• Should the user be able to control which factorisation is used?
• How to we test the conditional loading?
• Does committing to package extensions mean we need to maintain compatibility going forward?

My experience with package extensions has been bad: https://github.com/jump-dev/JuMP.jl/blob/master/ext/JuMPDimensionalDataExt.jl adds minimal functionality but has many breaking releases https://github.com/jump-dev/JuMP.jl/blob/a43fe85462943d02ab899eae24f5cb8d43c0893b/Project.toml#L23.

My experience with package extensions has been great: https://github.com/lanl-ansi/MathOptAI.jl/tree/main/ext

[samuelsonric]

🚌