Хордальная декомпозиция
artpgchПрименение хордальной декомпозиции для повышения производительности оптимизации
Введение
В задачах математической оптимизации с положительно полуопределёнными ограничениями, размерность матричных переменных часто становится критическим фактором, ограничивающим вычислительную эффективность. Однако многие практические задачи характеризуются выраженной разреженностью матриц, что открывает возможность применения специализированных методов декомпозиции.
Хордальная декомпозиция — это метод разложения одного большого PSD‑ограничения на набор меньших PSD‑ограничений и несколько ограничений в виде линейных равенств.
PSD-ограничение (Positive Semidefinite constraint) — это ограничение в математической оптимизации, требующее, чтобы матрица переменных была положительно полуопределённой, иными словами, матрица описывает форму, которая никогда не даёт отрицательных значений, если её использовать в квадратичной форме. Если исходное PSD‑ограничение является разреженным, то декомпозированная задача может решаться быстрее, чем исходная.
PSD-ограничение — это гарантия того, что квадратичная форма, задаваемая матрицей, всегда неотрицательна. Это фундаментальное требование для физической реализуемости многих систем — от финансовых моделей до инженерных конструкций.
В данном примере представлено, как использовать библиотеки:
JuMP, MathOptChordalDecomposition, SCS, SparseArrays
для повышения производительности моделей с PSD‑ограничениями.
Исходные данные
Импортируем и присоединим необходимые библиотеки.
import Pkg
Pkg.add(["JuMP", "MathOptChordalDecomposition", "SCS", "SparseArrays"])
using JuMP, MathOptChordalDecomposition, SCS, SparseArrays
Чтобы продемонстрировать преимущества хордальной декомпозиции, мы используем заранее подготовленную модель из файла data.dat-s.
модель = read_from_file(joinpath(@__DIR__, "data.dat-s"))
Эта модель имеет 124 переменных решения и одно PSD-ограничение. Это PSD-ограничение является разреженным, что означает, что многие элементы матрицы равны нулю.
Чтобы просмотреть матрицу, используем функцию all_constraints для получения списка ограничений, а затем используем функцию constraint_object для получения формы ограничения в виде функции и множества:
S = MOI.PositiveSemidefiniteConeTriangle
constraints = all_constraints(модель, Vector{AffExpr}, S)
огр = constraint_object(constraints[1]);
огр.set
Ограничения представлены в виде вектора.
огр.func
Используя функцию reshape_vector, преобразуем ограничения в вид матрицы.
F = reshape_vector(огр.func, SymmetricMatrixShape(огр.set.side_dimension))
Используя функцию SparseArrays.sparse, преобразуем матрицу F в разреженную матрицу A:
A = SparseArrays.sparse(F)
Разреженная матрица содержит 422 ненулевых элемента, что соответствует плотности 2,7%:
SparseArrays.nnz(A) / size(A, 1)^2
Скорость вычислений
SCS — это решатель первого порядка, который не использует разреженность PSD-ограничений. Запустим решение этой задачи и посмотрим, сколько времени это заняло:
set_optimizer(модель, SCS.Optimizer)
@time optimize!(модель)
Используем SCS.Optimizer как аргумент MathOptChordalDecomposition.Optimizer. Запустим решение и измерим время решения.
set_optimizer(модель, () -> MathOptChordalDecomposition.Optimizer(SCS.Optimizer))
@time optimize!(модель)
Теперь время решения заняло менее одной секунды. Такое различие в производительности обусловлено применением хордальной декомпозиции. Декомпозированная задача ввела новые переменные (теперь их 1155 вместо 124) и ограничения (теперь стало 115 PSD-ограничений вместо одного), но каждое PSD-ограничение стало меньше исходного.
декомпозиция = unsafe_backend(модель)
Вычислим количество PSD-ограничений каждого размера:
количество = Dict{Int,Int}()
for ci in MOI.get(декомпозиция, MOI.ListOfConstraintIndices{MOI.VectorOfVariables,S}())
set = MOI.get(декомпозиция, MOI.ConstraintSet(), ci)
n = set.side_dimension
количество[n] = get(количество, n, 0) + 1
end
количество
Самое большое PSD-ограничение теперь имеет размер 10, что значительно меньше исходной матрицы 124×124.
Заключение
Проведённое исследование демонстрирует эффективность хордальной декомпозиции как метода ускорения решения задач полуопределённого программирования с разреженными матричными ограничениями.
Перспективы дальнейших исследований включают адаптацию метода для задач со смешанной структурой (комбинация PSD-ограничений с другими типами ограничений), оптимизацию алгоритмов построения хордальных расширений для особых классов разреженных матриц, а также разработку критериев оценки целесообразности декомпозиции на основе анализа структуры задачи.
Реализация метода обеспечивает воспроизводимость результатов и создаёт основу для интеграции хордальной декомпозиции в рабочие процессы исследователей и инженеров, работающих с крупномасштабными задачами оптимизации.