Manopt.jl

Страница в процессе перевода.

Manopt.jl — это пакет, предоставляющий решатели для задач оптимизации, определенных на римановых многообразиях. Реализация основана на интерфейсе ManifoldsBase.jl и, следовательно, может использоваться для всех многообразий, определенных в Manifolds, или любых других многообразий, реализованных с использованием этого интерфейса.

Установка: OptimizationManopt.jl

Чтобы использовать интерфейс Optimization.jl для Manopt, установите пакет OptimizationManopt:

import Pkg;
Pkg.add("OptimizationManopt");

Методы

Для пакета OptimizationManopt доступны следующие методы:

GradientDescentOptimizer: соответствует методу gradient_descent в Manopt.
NelderMeadOptimizer: соответствует методу NelderMead в Manopt.
ConjugateGradientDescentOptimizer: соответствует методу conjugate_gradient_descent в Manopt.
ParticleSwarmOptimizer: соответствует методу particle_swarm в Manopt.
QuasiNewtonOptimizer: соответствует методу quasi_Newton в Manopt.
CMAESOptimizer: соответствует методу cma_es в Manopt.
ConvexBundleOptimizer: соответствует методу convex_bundle_method в Manopt.
FrankWolfeOptimizer: соответствует методу FrankWolfe в Manopt.

Общие именованные аргументы maxiters, maxtime и abstol поддерживаются всеми оптимизаторами. Специфичные для решателей именованные аргументы из Manopt можно передать в функцию solve или в OptimizationProblem.

Note Многообразие должно передаваться в OptimizationProblem в именованном аргументе manifold.

Примеры

Функцию Розенброка на евклидовом многообразии можно оптимизировать с помощью GradientDescentOptimizer следующим образом:

using Optimization, OptimizationManopt, Manifolds, LinearAlgebra
rosenbrock(x, p) = (p[1] - x[1])^2 + p[2] * (x[2] - x[1]^2)^2
x0 = zeros(2)
p = [1.0, 100.0]

R2 = Euclidean(2)

stepsize = Manopt.ArmijoLinesearch(R2)
opt = OptimizationManopt.GradientDescentOptimizer()

optf = OptimizationFunction(rosenbrock, Optimization.AutoZygote())

prob = OptimizationProblem(
    optf, x0, p; manifold = R2, stepsize = stepsize)

sol = Optimization.solve(prob, opt)

retcode: Failure
u: 2-element Vector{Float64}:
 0.8165527190561593
 0.6672818138967234

Задачу Кархера о нахождении среднего значения с прямоугольными ограничениями на многообразии SPD можно решить с помощью алгоритма Франка-Вульфа следующим образом:

M = SymmetricPositiveDefinite(5)
m = 100
σ = 0.005
q = Matrix{Float64}(I, 5, 5) .+ 2.0
data2 = [exp(M, q, σ * rand(M; vector_at = q)) for i in 1:m]

f(x, p = nothing) = sum(distance(M, x, data2[i])^2 for i in 1:m)
optf = OptimizationFunction(f, Optimization.AutoZygote())
prob = OptimizationProblem(optf, data2[1]; manifold = M, maxiters = 1000)

function closed_form_solution!(M::SymmetricPositiveDefinite, q, L, U, p, X)
    # извлекаем p^1/2 и p^{-1/2}
    (p_sqrt_inv, p_sqrt) = Manifolds.spd_sqrt_and_sqrt_inv(p)
    # Вычисляем D и Q
    e2 = eigen(p_sqrt_inv * X * p_sqrt_inv) # разлагаем Sk = QDQ'
    D = Diagonal(1.0 .* (e2.values .< 0))
    Q = e2.vectors

    Uprime = Q' * p_sqrt_inv * U * p_sqrt_inv * Q
    Lprime = Q' * p_sqrt_inv * L * p_sqrt_inv * Q
    P = cholesky(Hermitian(Uprime - Lprime))
    z = P.U' * D * P.U + Lprime
    copyto!(M, q, p_sqrt * Q * z * Q' * p_sqrt)
    return q
end
N = m
U = mean(data2)
L = inv(sum(1 / N * inv(matrix) for matrix in data2))

optf = OptimizationFunction(f, Optimization.AutoZygote())
prob = OptimizationProblem(optf, U; manifold = M, maxiters = 1000)

sol = Optimization.solve(
    prob, opt, sub_problem = (M, q, p, X) -> closed_form_solution!(M, q, L, U, p, X))

retcode: Failure
u: 5×5 Matrix{Float64}:
 2.99909  1.9993   1.99918  1.9994   1.99959
 1.9993   2.99959  1.99939  1.99956  1.99968
 1.99918  1.99939  2.99923  1.99942  1.99954
 1.9994   1.99956  1.99942  2.99963  1.99984
 1.99959  1.99968  1.99954  1.99984  2.9999

Этот пример основан на примере в Manopt и статье Вебер и Сра, 2022.

Следующий пример адаптирован из примера отношения Релея в ManoptExamples.jl. Мы решаем задачу отношения Релея на сферическом многообразии:

using Optimization, OptimizationManopt
using Manifolds, LinearAlgebra
using Manopt

n = 1000
A = Symmetric(randn(n, n) / n)
manifold = Sphere(n - 1)

cost(x, p = nothing) = -x' * A * x
egrad(G, x, p = nothing) = (G .= -2 * A * x)

optf = OptimizationFunction(cost, grad = egrad)
x0 = rand(manifold)
prob = OptimizationProblem(optf, x0, manifold = manifold)

sol = solve(prob, GradientDescentOptimizer())

retcode: Failure
u: 1000-element Vector{Float64}:
  0.01762169728569332
  0.036453437409565484
 -0.07994375379576305
  0.017944451655274165
 -0.09196598746916287
 -0.009986191362713108
  0.01745879680206771
 -0.01212935641985748
 -0.007594723449626095
 -0.011600811811304991
  ⋮
 -0.011948665669623807
 -0.010008666373949848
 -0.021777767128275824
  0.01509374676118785
  0.06237839083527088
 -0.00657276323355566
 -0.03315533312952052
  0.008965243051950903
 -0.037907481632190904

Проверим, действительно ли это соответствует минимальному собственному значению матрицы A.

@show eigmin(A)
@show sol.objective

-0.06285476047155444