Applying chordal decomposition to improve optimization performance
Introduction
In mathematical optimization problems with positively semi-definite constraints, the dimension of matrix variables often becomes a critical factor limiting computational efficiency. However, many practical tasks are characterized by pronounced sparsity of matrices, which opens up the possibility of using specialized decomposition methods.
Chordal decomposition is a method of decomposing one large PSD constraint into a set of smaller PSD constraints and several constraints in the form of linear equalities.
*The PSD constraint (Positive Semidefinite constraint) is a constraint in mathematical optimization that requires the matrix of variables to be positively semi-definite, in other words, the matrix describes a shape that never gives negative values if used in quadratic form. If the original PSD constraint is sparse, then the decomposed problem can be solved faster than the original one.
The PSD constraint is a guarantee that the quadratic shape given by the matrix is always non-negative. This is a fundamental requirement for the physical feasibility of many systems, from financial models to engineering structures.
This example shows how to use the libraries.:
JuMP, MathOptChordalDecomposition, SCS, SparseArrays
to improve the performance of models with PSD limitations.
Initial data
We will import and attach the necessary libraries.
import Pkg
Pkg.add(["JuMP", "MathOptChordalDecomposition", "SCS", "SparseArrays"])
using JuMP, MathOptChordalDecomposition, SCS, SparseArrays
To demonstrate the advantages of chordal decomposition, we use a pre-prepared model from the data.dat-s file.
модель = read_from_file(joinpath(@__DIR__, "data.dat-s"))
This model has 124 decision variables and one PSD constraint. This PSD constraint is sparse, which means that many elements of the matrix are zero.
To view the matrix, use the function all_constraints to get a list of restrictions, and then use the function constraint_object to obtain a constraint form in the form of a function and a set:
S = MOI.PositiveSemidefiniteConeTriangle
constraints = all_constraints(model, Vector{AffExpr}, S)
ogre = constraint_object(constraints[1]);
ogre.set
The constraints are represented as a vector.
ogre.func
Using the function reshape_vector, we transform the constraints into the form of a matrix.
F = reshape_vector(ogr.func, SymmetricMatrixShape(ogr.set.side_dimension))
Using the function SparseArrays.sparse, we transform the matrix F into a sparse matrix A:
A = SparseArrays.sparse(F)
The sparse matrix contains 422 nonzero elements, which corresponds to a density of 2.7%:
SparseArrays.nnz(A) / size(A, 1)^2
Computing speed
SCS is a first—order solver that does not use sparsity of PSD constraints. Let's run the solution to this problem and see how long it took.:
set_optimizer(model, SCS.Optimizer)
@time optimize!(model)
We use SCS.Optimizer as an argument to MathOptChordalDecomposition.Optimizer. Let's launch the solution and measure the solution time.
set_optimizer(model, () -> MathOptChordalDecomposition.Optimizer(SCS.Optimizer))
@time optimize!(model)
Now the decision time took less than one second. This difference in performance is due to the use of chordal decomposition. The decomposed task introduced new variables (now there are 1155 instead of 124) and constraints (now there are 115 PSD constraints instead of one), but each PSD constraint has become smaller than the original one.
decomposition = unsafe backend(model)
Let's calculate the number of PSD constraints of each size:
quantity = Dict{Int,Int}()
for ci in MOI.get(decomposition, MOI.ListOfConstraintIndices{MOI.VectorOfVariables,S}())
set = MOI.get(decomposition, MOI.ConstraintSet(), ci)
n = set.side_dimension
quantity[n] = get(quantity, n, 0) + 1
end
quantity
The largest PSD constraint now has a size of 10, which is significantly smaller than the original 124x124 matrix.
Conclusion
The study demonstrates the effectiveness of chordal decomposition as a method for accelerating the solution of semi-definite programming problems with sparse matrix constraints.
The prospects for further research include adapting the method to problems with a mixed structure (a combination of PSD constraints with other types of constraints), optimizing algorithms for constructing chordal extensions for special classes of sparse matrices, as well as developing criteria for evaluating the feasibility of decomposition based on an analysis of the problem structure.
The implementation of the method ensures reproducibility of the results and creates the basis for integrating chordal decomposition into the work processes of researchers and engineers working with large-scale optimization tasks.