Semidefinite constraints, fp roundoff errors, and normalization

I am using JuMP with semidefinite constraints, and when my matrix elements become large, roundoff errors also become large, in absolute terms.

JuMP warns when the matrix has absolute asymmetries in the range 1e-10 to 1e-8.

My matrices have relatively small asymmetries due to floating point roundoff, but when the matrix elements grow to be around or above 1e8 or 1e9, the absolute roundoff errors grow to be larger then the selected bound 1e-10.

As a solution, I now add rescalings to my matrices, when they become large. As a heuristic, I let C be the constant in my `Matrix{JuMP.AffExpr}`, and when the scalar value `maximum(abs.(C)) > 1e4`, I divide my matrix by it, before setting the constraint.

If only the relative asymmetry matters, then perhaps JuMP should only warn when the asymmetric part is significant compared to the symmetric part.

If the absolute asymmetry matters, then perhaps JuMP could help by rescaling matrices so that the symmetric part becomes reasonable, thereby reducing the impact of rounding errors.

Any of these would have saved me a bit of worry and debugging.

Thanks

1 Like

You should probably construct your matrices using `LinearAlgebra.Symmetric(C)` to tell JuMP that the matrix is structurally symmetric: see Constraints Â· JuMP

If you can provide a reproducible example, people may have suggestions for improvements.

Both the absolute and relative asymmetries can matter. Where possible, we leave the userâ€™s model alone. Automatic rescaling can cause a number of issues.

In general, if you are having these problems it is a sign that you should reconsider your formulation. What to the elements of 1e9 mean? Change the physical units of your problem so that things are in kilometers instead of meters, or million dollars instead of dollars.

You should probably construct your matrices using `LinearAlgebra.Symmetric(C)` to tell JuMP that the matrix is structurally symmetric: see Constraints Â· JuMP

Thanks! I will do that.

Both the absolute and relative asymmetries can matter. Where possible, we leave the userâ€™s model alone. Automatic rescaling can cause a number of issues.

Firstly: Thanks. I will probably want to manually rescale my matrices.
Secondly: Ok. In that case, I retract my suggestions.

In general, if you are having these problems it is a sign that you should reconsider your formulation. What to the elements of 1e9 mean? Change the physical units of your problem so that things are in kilometers instead of meters, or million dollars instead of dollars.

In the case I have observed, I mostly end up with matrices in the size 1e-2 to 1e4, which seems good to me, and the large values appear only rarely.

The actual values in the matrices are due to a number of choices I would refer to as â€śunphysicalâ€ť. In particular, I first build up a representation of a complete system from representations of subsystems, and the large matrix elements are due to the choice of basis in the algorithm implemented in `MatrixPencils.jl` and used by `ControlSystems.jl` to find a minimal state-space representation for a linear dynamical system.

Unfortunately, I have enough other issues to focus on, and I will not have time to understand if I can have a systematic solution to the choice-of-basis problem for the kinds of systems I am interested in.

1 Like