plot_sparsity (generic function with 1 method)Accelerations for quadratic functions and symmetric problems
This example illustrates how to exploit symmetry to reduce the dimension of the problem via SubspaceLMO. Moreover, active set based algorithms can be accelerated by using the specialized structure ActiveSetQuadraticProductCaching.
The specific problem we consider here comes from quantum information and some context can be found here. Formally, we want to find the distance between a tensor of size m^N and the N-partite local polytope which is defined by its vertices
\[d^{\vec{a}^{(1)}\ldots \vec{a}^{(N)}}_{x_1\ldots x_N}\coloneqq\prod_{n=1}^Na^{(n)}_{x_n}\]
labeled by $\vec{a}^{(n)}=a^{(n)}_1\ldots a^{(n)}_m$ for $n\in[1,N]$, where $a^{(n)}_x=\pm1$. In the bipartite case (N=2), this polytope is affinely equivalent to the cut polytope.
Import and setup
We first import the necessary packages.
import Combinatorics
import FrankWolfe
import LinearAlgebra
import TullioThen we can define our custom LMO, together with the method compute_extreme_point, which simply enumerates the vertices $d^{\vec{a}^{(1)}}$ defined above. This structure is specialized for the case N=5 and contains pre-allocated fields used to accelerate the enumeration. Note that the output type (full tensor) is quite naive, but this is enough to illustrate the syntax in this toy example.
struct BellCorrelationsLMO{T} <: FrankWolfe.LinearMinimizationOracle
m::Int # size of the tensor
tmp1::Array{T, 1}
tmp2::Array{T, 2}
tmp3::Array{T, 3}
tmp4::Array{T, 4}
end
function FrankWolfe.compute_extreme_point(lmo::BellCorrelationsLMO{T}, A::Array{T, 5}; kwargs...) where {T <: Number}
ax = [ones(T, lmo.m) for n in 1:5]
sc1 = zero(T)
sc2 = one(T)
axm = [zeros(T, lmo.m) for n in 1:5]
scm = typemax(T)
L = 2^lmo.m
aux = zeros(Int, lmo.m)
for λa5 in 0:(L÷2)-1
digits!(aux, λa5, base=2)
ax[5] .= 2aux .- 1
Tullio.@tullio lmo.tmp4[x1, x2, x3, x4] = A[x1, x2, x3, x4, x5] * ax[5][x5]
for λa4 in 0:L-1
digits!(aux, λa4, base=2)
ax[4] .= 2aux .- 1
Tullio.@tullio lmo.tmp3[x1, x2, x3] = lmo.tmp4[x1, x2, x3, x4] * ax[4][x4]
for λa3 in 0:L-1
digits!(aux, λa3, base=2)
ax[3] .= 2aux .- 1
Tullio.@tullio lmo.tmp2[x1, x2] = lmo.tmp3[x1, x2, x3] * ax[3][x3]
for λa2 in 0:L-1
digits!(aux, λa2, base=2)
ax[2] .= 2aux .- 1
LinearAlgebra.mul!(lmo.tmp1, lmo.tmp2, ax[2])
for x1 in 1:lmo.m
ax[1][x1] = lmo.tmp1[x1] > zero(T) ? -one(T) : one(T)
end
sc = LinearAlgebra.dot(ax[1], lmo.tmp1)
if sc < scm
scm = sc
for n in 1:5
axm[n] .= ax[n]
end
end
end
end
end
end
return [axm[1][x1]*axm[2][x2]*axm[3][x3]*axm[4][x4]*axm[5][x5] for x1 in 1:lmo.m, x2 in 1:lmo.m, x3 in 1:lmo.m, x4 in 1:lmo.m, x5 in 1:lmo.m]
endThen we define our specific instance, coming from a GHZ state measured with measurements forming a regular polygon on the equator of the Bloch sphere. See this article for definitions and references.
function correlation_tensor_GHZ_polygon(::Type{T}, N::Int, m::Int) where {T <: Number}
res = zeros(T, m*ones(Int, N)...)
tab_cos = [cos(x*T(pi)/m) for x in 0:N*m]
tab_cos[abs.(tab_cos) .< Base.rtoldefault(T)] .= zero(T)
for ci in CartesianIndices(res)
res[ci] = tab_cos[sum(ci.I)-N+1]
end
return res
end
T = Float64
verbose = true
max_iteration = 10^4
m = 5
p = 0.23correlation_tensor_GHZ_polygon(T, 5, m)
x0 = zeros(T, size(p))The objective function is simply $\frac12\|x-p\|_2^2$, which we decompose in different terms for speed.
normp2 = LinearAlgebra.dot(p, p) / 2
f = let p = p, normp2 = normp2
x -> LinearAlgebra.dot(x, x) / 2 - LinearAlgebra.dot(p, x) + normp2
end
grad! = let p = p
(storage, x) -> begin
@inbounds for i in eachindex(x)
storage[i] = x[i] - p[i]
end
end
endNaive run
If we run the blended pairwise conditional gradient algorithm without modifications, convergence is not reached in 10000 iterations.
lmo_naive = BellCorrelationsLMO{T}(m, zeros(T, m), zeros(T, m, m), zeros(T, m, m, m), zeros(T, m, m, m, m))
as_naive = FrankWolfe.ActiveSet([(one(T), x0)])
@time FrankWolfe.blended_pairwise_conditional_gradient(f, grad!, lmo_naive, as_naive; verbose, lazy=true, line_search=FrankWolfe.Shortstep(one(T)), max_iteration)
Blended Pairwise Conditional Gradient Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: Array{Float64, 5} LAZY: true lazy_tolerance: 2.0
LMO: Main.BellCorrelationsLMO{Float64}
----------------------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec #ActiveSet
----------------------------------------------------------------------------------------------------------------
I 1 4.132812e+01 -4.029553e+01 8.162365e+01 0.000000e+00 Inf 1
LD 46 1.102219e+01 -2.889653e+01 3.991872e+01 4.440863e+00 1.035835e+01 46
LD 103 4.741326e+00 -1.484609e+01 1.958742e+01 7.929356e+00 1.298971e+01 79
LD 217 1.129314e+00 -5.004581e+00 6.133895e+00 1.267516e+01 1.712010e+01 126
LD 351 7.257875e-01 -2.271567e+00 2.997354e+00 1.598270e+01 2.196124e+01 157
P 1000 4.532655e-01 -2.544089e+00 2.997354e+00 3.135924e+01 3.188853e+01 310
LD 1621 2.613257e-01 -1.230782e+00 1.492108e+00 4.508058e+01 3.595783e+01 445
P 2000 2.268145e-01 -1.265294e+00 1.492108e+00 4.542643e+01 4.402724e+01 440
P 3000 1.381013e-01 -1.354007e+00 1.492108e+00 5.298590e+01 5.661884e+01 496
P 4000 6.040867e-02 -1.431699e+00 1.492108e+00 6.567176e+01 6.090898e+01 610
LD 4415 3.072837e-02 -4.006321e-01 4.313605e-01 7.060261e+01 6.253309e+01 647
P 5000 1.738588e-02 -4.139746e-01 4.313605e-01 7.094533e+01 7.047681e+01 627
LD 5663 1.229003e-02 -1.045655e-01 1.168556e-01 7.123272e+01 7.949999e+01 625
P 6000 1.113787e-02 -1.057177e-01 1.168556e-01 7.146956e+01 8.395182e+01 625
P 7000 9.735387e-03 -1.071202e-01 1.168556e-01 7.191560e+01 9.733633e+01 625
LD 7469 9.517109e-03 -2.020889e-02 2.972600e-02 7.212597e+01 1.035549e+02 625
P 8000 9.392674e-03 -2.033332e-02 2.972600e-02 7.251704e+01 1.103189e+02 625
P 9000 9.304994e-03 -2.042100e-02 2.972600e-02 7.295571e+01 1.233625e+02 625
LD 9490 9.290088e-03 1.701123e-03 7.588965e-03 7.317992e+01 1.296804e+02 625
P 10000 9.282251e-03 1.693286e-03 7.588965e-03 7.350181e+01 1.360511e+02 625
Last 10001 9.282230e-03 3.629714e-03 5.652516e-03 7.359617e+01 1.358902e+02 625
----------------------------------------------------------------------------------------------------------------
PP 10001 9.282230e-03 3.629714e-03 5.652516e-03 7.368942e+01 1.357183e+02 625
----------------------------------------------------------------------------------------------------------------
73.776763 seconds (378.65 M allocations: 45.133 GiB, 11.57% gc time, 0.17% compilation time)Faster active set for quadratic functions
A first acceleration can be obtained by using the active set specialized for the quadratic objective function, whose gradient is here $x-p$, explaining the hessian and linear part provided as arguments. The speedup is obtained by pre-computing some scalar products to quickly obtained, in each iteration, the best and worst atoms currently in the active set.
asq_naive = FrankWolfe.ActiveSetQuadraticProductCaching([(one(T), x0)], LinearAlgebra.I, -p)
@time FrankWolfe.blended_pairwise_conditional_gradient(f, grad!, lmo_naive, asq_naive; verbose, lazy=true, line_search=FrankWolfe.Shortstep(one(T)), max_iteration)
Blended Pairwise Conditional Gradient Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: Array{Float64, 5} LAZY: true lazy_tolerance: 2.0
LMO: Main.BellCorrelationsLMO{Float64}
----------------------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec #ActiveSet
----------------------------------------------------------------------------------------------------------------
I 1 4.132812e+01 -4.029553e+01 8.162365e+01 0.000000e+00 Inf 1
LD 46 1.102219e+01 -2.889653e+01 3.991872e+01 4.463457e+00 1.030591e+01 46
LD 104 4.682362e+00 -1.505762e+01 1.973998e+01 7.918368e+00 1.313402e+01 79
LD 217 1.153286e+00 -4.834945e+00 5.988231e+00 1.265460e+01 1.714792e+01 126
LD 361 7.246254e-01 -2.234291e+00 2.958916e+00 1.600865e+01 2.255031e+01 158
P 1000 4.580028e-01 -2.500913e+00 2.958916e+00 3.070756e+01 3.256528e+01 305
LD 1759 2.293608e-01 -1.236982e+00 1.466343e+00 4.691729e+01 3.749151e+01 460
P 2000 2.035603e-01 -1.262782e+00 1.466343e+00 4.701129e+01 4.254297e+01 458
P 3000 1.211665e-01 -1.345176e+00 1.466343e+00 5.244972e+01 5.719764e+01 500
P 4000 4.749301e-02 -1.418850e+00 1.466343e+00 6.608284e+01 6.053009e+01 632
LD 4227 3.237072e-02 -3.805380e-01 4.129088e-01 6.850353e+01 6.170485e+01 654
P 5000 1.624641e-02 -3.966624e-01 4.129088e-01 6.861375e+01 7.287170e+01 625
LD 5566 1.241685e-02 -1.000254e-01 1.124422e-01 6.863372e+01 8.109716e+01 625
P 6000 1.102951e-02 -1.014127e-01 1.124422e-01 6.874592e+01 8.727791e+01 625
P 7000 9.754199e-03 -1.026880e-01 1.124422e-01 6.877848e+01 1.017760e+02 625
LD 7558 9.511291e-03 -1.988317e-02 2.939446e-02 6.879804e+01 1.098578e+02 625
P 8000 9.410900e-03 -1.998356e-02 2.939446e-02 6.889759e+01 1.161144e+02 625
P 9000 9.314629e-03 -2.007983e-02 2.939446e-02 6.893020e+01 1.305669e+02 625
LD 9702 9.291671e-03 1.444824e-03 7.846848e-03 6.895411e+01 1.407023e+02 625
P 10000 9.286464e-03 1.439616e-03 7.846848e-03 6.910981e+01 1.446973e+02 625
Last 10001 9.286436e-03 2.102908e-03 7.183528e-03 6.920337e+01 1.445161e+02 625
----------------------------------------------------------------------------------------------------------------
PP 10001 9.286436e-03 2.102908e-03 7.183528e-03 6.929689e+01 1.443211e+02 625
----------------------------------------------------------------------------------------------------------------
69.383795 seconds (374.84 M allocations: 44.687 GiB, 12.31% gc time, 0.18% compilation time)In this small example, the acceleration is quite minimal, but as soon as one of the following conditions is met, significant speedups (factor ten at least) can be expected:
- quite expensive scalar product between atoms, for instance, due to a high dimension (say, more than 10000),
- high number of atoms in the active set (say, more than 1000),
- high number of iterations (say, more than 100000), spending most of the time redistributing the weights in the active set.
Dimension reduction via symmetrization
Permutation of the tensor axes
It is easy to see that our specific instance remains invariant under permutation of the dimensions of the tensor. This means that all computations can be performed in the symmetric subspace, which leads to an important speedup, owing to the reduced dimension (hence reduced size of the final active set and reduced number of iterations).
The way to operate this in the FrankWolfe package is to use a symmetrized LMO, which basically does the following:
- symmetrize the gradient, which is not necessary here as the gradient remains symmetric throughout the algorithm,
- call the standard LMO,
- symmetrize its output, which amounts to averaging over its orbit with respect to the group considered (here the symmetric group permuting the dimensions of the tensor).
function reynolds_permutedims(atom::Array{T, N}, lmo::BellCorrelationsLMO{T}) where {T <: Number, N}
res = zeros(T, size(atom))
for per in Combinatorics.permutations(1:N)
res .+= permutedims(atom, per)
end
res ./= factorial(N)
return res
endNote that the second argument lmo is not used here but could in principle be exploited to obtain a very small speedup by precomputing and storing Combinatorics.permutations(1:N) in a dedicated field of our custom LMO.
lmo_permutedims = FrankWolfe.SubspaceLMO(lmo_naive, reynolds_permutedims)
asq_permutedims = FrankWolfe.ActiveSetQuadraticProductCaching([(one(T), x0)], LinearAlgebra.I, -p)
@time FrankWolfe.blended_pairwise_conditional_gradient(f, grad!, lmo_permutedims, asq_permutedims; verbose, lazy=true, line_search=FrankWolfe.Shortstep(one(T)), max_iteration)
Blended Pairwise Conditional Gradient Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: Array{Float64, 5} LAZY: true lazy_tolerance: 2.0
LMO: FrankWolfe.SubspaceLMO{Main.BellCorrelationsLMO{Float64}, typeof(Main.reynolds_permutedims), FrankWolfe.var"#10#11"}
----------------------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec #ActiveSet
----------------------------------------------------------------------------------------------------------------
I 1 4.132812e+01 -4.029553e+01 8.162365e+01 0.000000e+00 Inf 1
LD 11 1.153403e+01 -2.734161e+01 3.887563e+01 7.517550e-01 1.463243e+01 9
LD 29 3.294910e+00 -1.375281e+01 1.704772e+01 1.291467e+00 2.245509e+01 13
LD 47 1.630202e+00 -6.744183e+00 8.374385e+00 1.616807e+00 2.906964e+01 15
LD 100 4.530833e-01 -2.912142e+00 3.365226e+00 2.611597e+00 3.829074e+01 23
LD 175 1.770240e-01 -1.434036e+00 1.611060e+00 3.108879e+00 5.629038e+01 23
LD 268 8.360800e-02 -6.726422e-01 7.562502e-01 3.781037e+00 7.088002e+01 29
LD 555 2.209150e-02 -2.970870e-01 3.191785e-01 4.459667e+00 1.244488e+02 30
LD 773 1.139297e-02 -6.500159e-02 7.639456e-02 4.552551e+00 1.697949e+02 26
P 1000 9.617158e-03 -6.677740e-02 7.639456e-02 4.645673e+00 2.152541e+02 26
LD 1086 9.450474e-03 -9.519297e-03 1.896977e-02 4.658424e+00 2.331260e+02 26
LD 1500 9.283632e-03 4.858918e-03 4.424714e-03 4.756143e+00 3.153816e+02 26
LD 1900 9.274785e-03 8.183461e-03 1.091323e-03 4.915744e+00 3.865132e+02 26
P 2000 9.274488e-03 8.183165e-03 1.091323e-03 5.005690e+00 3.995453e+02 26
LD 2326 9.274249e-03 9.015738e-03 2.585111e-04 5.014305e+00 4.638729e+02 26
LD 2740 9.274216e-03 9.214614e-03 5.960203e-05 5.112013e+00 5.359924e+02 26
P 3000 9.274214e-03 9.214612e-03 5.960203e-05 5.205469e+00 5.763170e+02 26
LD 3178 9.274214e-03 9.262304e-03 1.190966e-05 5.210275e+00 6.099486e+02 26
LD 3636 9.274214e-03 9.271595e-03 2.619296e-06 5.309049e+00 6.848684e+02 26
P 4000 9.274214e-03 9.271595e-03 2.619296e-06 5.468461e+00 7.314673e+02 26
LD 4064 9.274214e-03 9.273578e-03 6.357779e-07 5.470419e+00 7.429046e+02 26
LD 4470 9.274214e-03 9.274066e-03 1.484091e-07 5.568250e+00 8.027657e+02 26
LD 4865 9.274214e-03 9.274179e-03 3.537488e-08 5.665542e+00 8.586998e+02 26
Last 4865 9.274214e-03 9.274179e-03 3.537488e-08 5.918851e+00 8.219501e+02 26
----------------------------------------------------------------------------------------------------------------
PP 4865 9.274214e-03 9.274179e-03 3.537488e-08 6.004013e+00 8.102914e+02 26
----------------------------------------------------------------------------------------------------------------
6.159839 seconds (31.77 M allocations: 3.930 GiB, 13.28% gc time, 2.08% compilation time)Now, convergence is reached within 10000 iterations, and the size of the final active set is considerably smaller than before, thanks to the reduced dimension.
Uniqueness pattern
In this specific case, there is a bigger symmetry group that we can exploit. Its action roughly allows us to work in the subspace respecting the structure of the objective point p, that is, to average over tensor entries that have the same value in p. Although quite general, this kind of symmetry is not always applicable, and great care has to be taken when using it, in particular, to ensure that there exists a suitable group action whose Reynolds operator corresponds to this averaging procedure. In our current case, the theoretical study enabling this further symmetrization can be found here.
function build_reynolds_unique(p::Array{T, N}) where {T <: Number, N}
ptol = round.(p; digits=8)
ptol[ptol .== zero(T)] .= zero(T) # transform -0.0 into 0.0 as isequal(0.0, -0.0) is false
uniquetol = unique(ptol[:])
indices = [ptol .== u for u in uniquetol]
return function(A::Array{T, N}, lmo)
res = zeros(T, size(A))
for ind in indices
@view(res[ind]) .= sum(A[ind]) / sum(ind) # average over ind
end
return res
end
end
lmo_unique = FrankWolfe.SubspaceLMO(lmo_naive, build_reynolds_unique(p))
asq_unique = FrankWolfe.ActiveSetQuadraticProductCaching([(one(T), x0)], LinearAlgebra.I, -p)
@time FrankWolfe.blended_pairwise_conditional_gradient(f, grad!, lmo_unique, asq_unique; verbose, lazy=true, line_search=FrankWolfe.Shortstep(one(T)), max_iteration)
Blended Pairwise Conditional Gradient Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: Array{Float64, 5} LAZY: true lazy_tolerance: 2.0
LMO: FrankWolfe.SubspaceLMO{Main.BellCorrelationsLMO{Float64}, Main.var"#43#45"{5, Float64, Vector{BitArray{5}}}, FrankWolfe.var"#10#11"}
----------------------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec #ActiveSet
----------------------------------------------------------------------------------------------------------------
I 1 4.132812e+01 -4.029553e+01 8.162365e+01 0.000000e+00 Inf 1
LD 4 2.991558e+00 -4.896575e+00 7.888134e+00 2.346687e-01 1.704531e+01 3
LD 19 4.246112e-01 -2.691388e+00 3.115999e+00 3.631704e-01 5.231704e+01 3
LD 64 1.802165e-01 -4.514355e-01 6.316521e-01 8.022867e-01 7.977198e+01 5
LD 81 2.002637e-02 -1.558821e-01 1.759085e-01 1.060704e+00 7.636439e+01 5
LD 118 1.364017e-02 -4.146471e-02 5.510488e-02 1.212412e+00 9.732665e+01 3
LD 189 9.505756e-03 -8.772067e-03 1.827782e-02 1.386622e+00 1.363024e+02 4
LD 204 9.297335e-03 2.741829e-03 6.555506e-03 1.472995e+00 1.384933e+02 4
LD 219 9.278805e-03 6.432857e-03 2.845948e-03 1.559475e+00 1.404318e+02 4
LD 237 9.274768e-03 8.268553e-03 1.006215e-03 1.711585e+00 1.384681e+02 4
LD 255 9.274310e-03 8.844241e-03 4.300684e-04 1.798510e+00 1.417840e+02 4
LD 270 9.274227e-03 9.117815e-03 1.564121e-04 1.885367e+00 1.432082e+02 4
LD 288 9.274216e-03 9.207613e-03 6.660359e-05 1.972119e+00 1.460358e+02 4
LD 303 9.274214e-03 9.249991e-03 2.422305e-05 2.058542e+00 1.471916e+02 4
LD 321 9.274214e-03 9.263899e-03 1.031492e-05 2.206542e+00 1.454765e+02 4
LD 336 9.274214e-03 9.270465e-03 3.748623e-06 2.293407e+00 1.465069e+02 4
LD 354 9.274214e-03 9.272618e-03 1.595962e-06 2.380157e+00 1.487297e+02 4
LD 369 9.274214e-03 9.273636e-03 5.784864e-07 2.466614e+00 1.495978e+02 4
LD 384 9.274214e-03 9.273964e-03 2.499339e-07 2.553228e+00 1.503978e+02 4
LD 397 9.274214e-03 9.274104e-03 1.101735e-07 2.700780e+00 1.469946e+02 4
LD 412 9.274214e-03 9.274166e-03 4.841374e-08 2.787539e+00 1.478006e+02 4
Last 412 9.274214e-03 9.274166e-03 4.841374e-08 2.959467e+00 1.392142e+02 4
----------------------------------------------------------------------------------------------------------------
PP 412 9.274214e-03 9.274166e-03 4.841374e-08 3.045605e+00 1.352769e+02 4
----------------------------------------------------------------------------------------------------------------
3.133786 seconds (16.52 M allocations: 1.955 GiB, 13.24% gc time, 3.74% compilation time)Reduction of the memory footprint of the iterate
In the previous run, the dimension reduction is mathematically exploited to accelerate the algorithm, but it is not used to effectively work in a subspace of reduced dimension. Indeed, the iterate, although symmetric, was still a full tensor. As a last example of the speedup obtainable through symmetry reduction, we show how to map the computations into a space whose physical dimension is also reduced during the algorithm. This makes all in-place operations marginally faster, which can lead, in bigger instances, to significant accelerations, especially for active set based algorithms in the regime where many lazy iterations are performed. We refer to the example symmetric.jl for a small benchmark with symmetric matrices.
function build_deflate_inflate(p::Array{T, N}) where {T <: Number, N}
ptol = round.(p; digits=8)
ptol[ptol .== zero(T)] .= zero(T) # transform -0.0 into 0.0 as isequal(0.0, -0.0) is false
uniquetol = unique(ptol[:])
dim = length(uniquetol) # reduced dimension
indices = [ptol .== u for u in uniquetol]
mul = [sum(ind) for ind in indices] # multiplicities, used to have matching scalar products
sqmul = sqrt.(mul) # precomputed for speed
return function(A::Array{T, N}, lmo)
vec = zeros(T, dim)
for (i, ind) in enumerate(indices)
vec[i] = sum(A[ind]) / sqmul[i]
end
return FrankWolfe.SubspaceVector(A, vec)
end, function(x::FrankWolfe.SubspaceVector, lmo)
for (i, ind) in enumerate(indices)
@view(x.data[ind]) .= x.vec[i] / sqmul[i]
end
return x.data
end
end
deflate, inflate = build_deflate_inflate(p)
p_deflate = deflate(p, nothing)
x0_deflate = deflate(x0, nothing)
f_deflate = let p_deflate = p_deflate, normp2 = normp2
x -> LinearAlgebra.dot(x, x) / 2 - LinearAlgebra.dot(p_deflate, x) + normp2
end
grad_deflate! = let p_deflate = p_deflate
(storage, x) -> begin
@inbounds for i in eachindex(x)
storage[i] = x[i] - p_deflate[i]
end
end
endNote that the objective function and its gradient have to be explicitly rewritten. In this simple example, their shape remains unchanged, but in general this may need some reformulation, which falls to the user.
lmo_deflate = FrankWolfe.SubspaceLMO(lmo_naive, deflate, inflate)
asq_deflate = FrankWolfe.ActiveSetQuadraticProductCaching([(one(T), x0_deflate)], LinearAlgebra.I, -p_deflate)
@time FrankWolfe.blended_pairwise_conditional_gradient(f_deflate, grad_deflate!, lmo_deflate, asq_deflate; verbose, lazy=true, line_search=FrankWolfe.Shortstep(one(T)), max_iteration)
Blended Pairwise Conditional Gradient Algorithm.
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
GRADIENTTYPE: FrankWolfe.SubspaceVector{false, Float64, Array{Float64, 5}, Vector{Float64}} LAZY: true lazy_tolerance: 2.0
LMO: FrankWolfe.SubspaceLMO{Main.BellCorrelationsLMO{Float64}, Main.var"#47#50"{5, Float64, Vector{Float64}, Vector{BitArray{5}}, Int64}, Main.var"#48#51"{Vector{Float64}, Vector{BitArray{5}}}}
----------------------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec #ActiveSet
----------------------------------------------------------------------------------------------------------------
I 1 4.132812e+01 -4.029553e+01 8.162365e+01 0.000000e+00 Inf 1
LD 4 2.991558e+00 -4.896575e+00 7.888134e+00 1.710583e-01 2.338384e+01 3
LD 13 2.369634e-01 -2.280882e+00 2.517846e+00 4.641085e-01 2.801069e+01 4
LD 19 1.668285e-01 -3.158581e-01 4.826866e-01 7.280088e-01 2.609859e+01 5
LD 32 1.699135e-02 -5.050512e-02 6.749647e-02 9.716287e-01 3.293439e+01 5
LD 108 9.519110e-03 -6.845621e-03 1.636473e-02 1.144027e+00 9.440337e+01 4
LD 121 9.297134e-03 3.819920e-03 5.477214e-03 1.230072e+00 9.836819e+01 4
LD 130 9.276520e-03 7.486464e-03 1.790056e-03 1.383241e+00 9.398220e+01 4
LD 139 9.274453e-03 8.643094e-03 6.313589e-04 1.469654e+00 9.458009e+01 4
LD 148 9.274257e-03 8.982108e-03 2.921491e-04 1.556046e+00 9.511285e+01 4
LD 161 9.274223e-03 9.143488e-03 1.307348e-04 1.642017e+00 9.805014e+01 4
LD 174 9.274215e-03 9.222314e-03 5.190121e-05 1.727995e+00 1.006947e+02 4
LD 187 9.274214e-03 9.250977e-03 2.323707e-05 1.881839e+00 9.937087e+01 4
LD 202 9.274214e-03 9.265798e-03 8.416106e-06 1.968246e+00 1.026294e+02 4
LD 215 9.274214e-03 9.270455e-03 3.759433e-06 2.054464e+00 1.046501e+02 4
LD 228 9.274214e-03 9.272829e-03 1.384972e-06 2.140502e+00 1.065171e+02 4
LD 244 9.274214e-03 9.273611e-03 6.025805e-07 2.226452e+00 1.095914e+02 4
LD 257 9.274214e-03 9.273974e-03 2.395475e-07 2.373606e+00 1.082741e+02 4
LD 270 9.274214e-03 9.274107e-03 1.073458e-07 2.459992e+00 1.097564e+02 4
LD 285 9.274214e-03 9.274175e-03 3.860101e-08 2.546202e+00 1.119314e+02 4
Last 285 9.274214e-03 9.274175e-03 3.860101e-08 2.717900e+00 1.048604e+02 4
----------------------------------------------------------------------------------------------------------------
PP 285 9.274214e-03 9.274175e-03 3.860101e-08 2.870194e+00 9.929643e+01 4
----------------------------------------------------------------------------------------------------------------
2.964379 seconds (15.43 M allocations: 1.825 GiB, 13.38% gc time, 4.49% compilation time)This page was generated using Literate.jl.