plot_sparsity (generic function with 1 method)Difference-of-Convex Algorithm with Frank-Wolfe
This example shows the optimization of a difference-of-convex problem of the form:
\[min\limits_{x \in \mathcal{X}} \phi(x) = f(x) - g(x)\]
with $f$, $g$ convex functions with access to subgradients and $f$ smooth.
The DCA-FW algorithm constructs local convex models of $\phi$ by linearizing $g$ and approximately optimizes them with FW. It is a local method that converges to a stationary point
using FrankWolfe
using LinearAlgebra
using Random
using SparseArrays
using StableRNGs
using RandomThe convex functions $f$, $g$ will be generated as random convex quadratics:
\[\begin{align} f(x) & = \frac12 x^\top A x + a^\top x + c \\ g(x) & = \frac12 x^\top B x + b^\top x + d \end{align}\]
Setting up the problem functions and data
const n = 500 # Reduced dimension
# Generate random positive definite matrices to ensure convexity
function generate_problem_data(rng)
A_raw = randn(rng, n, n)
A_raw ./= opnorm(A_raw)
A = A_raw' * A_raw + 0.1 * I
B_raw = randn(rng, n, n)
B_raw ./= opnorm(B_raw)
B = B_raw' * B_raw + 0.1 * I
a = randn(rng, n)
b = randn(rng, n)
c = randn(rng)
d = -359434.0
return A, B, a, b, c, d
end
const rng = StableRNGs.StableRNG(1)
const A, B, a, b, c, d = generate_problem_data(rng)([0.3664716461545845 0.007434201971305436 … 0.004451785375884828 0.015514411527022811; 0.007434201971305436 0.34822813947414366 … 0.013654308840956027 -0.025910486878046406; … ; 0.004451785375884828 0.013654308840956027 … 0.38062614047229715 0.011896910948147422; 0.015514411527022811 -0.025910486878046406 … 0.011896910948147422 0.3429933792454246], [0.3685823592850499 0.0036477368657639015 … -0.01474711849204955 -0.009390758842324272; 0.0036477368657639015 0.36832277324228335 … -0.00470842392230871 0.01931972691415084; … ; -0.01474711849204955 -0.00470842392230871 … 0.3718244447067386 -0.007058980450873015; -0.009390758842324272 0.01931972691415084 … -0.007058980450873015 0.3697697085359214], [-0.5056985849854947, 1.8254695540945816, 1.1686948924955953, 0.025865043318803068, 0.7618207158940428, -1.9599078996573032, -0.28701522778989075, -1.210555966368952, -0.3476555815275666, 0.36622748810084865 … -1.2418975260665193, -2.042717239142079, -0.977247840514734, -0.9480533072182336, 0.2354971732415276, 1.1489207372892907, 0.26713737924876685, -0.11111819389928967, 1.2106291210589706, -0.36135542009200855], [-1.7352231531269595, -1.0889348569606767, -1.9696069675033783, -0.6944538146281424, 0.12594479576421444, 2.43890963984164, -0.3332102207771672, -1.598587279152474, 0.8970898814075347, 0.7441204116527911 … -0.07885951683533911, 0.921491279700674, 0.8755353895807455, 0.4142785039140312, 1.0607172005644177, -0.9845905380360871, 0.7603797972500105, 1.0314248598279463, -1.0727076372535254, -0.1591576537893938], -0.6622940864130684, -359434.0)We can now define the two functions
function f(x)
return 0.5 * FrankWolfe.fast_dot(x, A, x) + dot(a, x) + c
end
function grad_f!(storage, x)
mul!(storage, A, x)
storage .+= a
return nothing
end
function g(x)
return 0.5 * FrankWolfe.fast_dot(x, B, x) + dot(b, x) + d
end
function grad_g!(storage, x)
mul!(storage, B, x)
storage .+= b
return nothing
end
# True objective function for verification
# It is not needed by the solver
function phi(x)
return f(x) - g(x)
end
lmo = FrankWolfe.KSparseLMO(5, 1000.0)
x0 = FrankWolfe.compute_extreme_point(lmo, randn(n))
res_dca = FrankWolfe.dca_fw(
f,
grad_f!,
g,
grad_g!,
lmo,
copy(x0),
max_iteration=200, # Outer iterations
max_inner_iteration=10000, # Inner iterations
epsilon=1e-5, # Tolerance for DCA gap
line_search=FrankWolfe.Secant(),
verbose=true,
trajectory=true,
verbose_inner=false,
print_iter=10,
use_corrective_fw=true,
use_dca_early_stopping=true,
grad_f_workspace=collect(x0),
grad_g_workspace=collect(x0),
)
res_boost = FrankWolfe.dca_fw(
f,
grad_f!,
g,
grad_g!,
lmo,
copy(x0),
boosted=true,
max_iteration=200, # Outer iterations
max_inner_iteration=10000, # Inner iterations
epsilon=1e-5, # Tolerance for DCA gap
line_search=FrankWolfe.Secant(),
verbose=true,
trajectory=true,
verbose_inner=false,
print_iter=10,
use_corrective_fw=true,
use_dca_early_stopping=true,
grad_f_workspace=collect(x0),
grad_g_workspace=collect(x0),
)(x = [85 ] = -527.341
[284] = 780.792
[313] = -1000.0
[348] = 939.759
[369] = -752.108
[486] = -1000.0, primal = 10279.682429701206, dca_gap = 0.679962090223853, iterations = 200, status = FrankWolfe.STATUS_MAXITER, traj_data = Any[(1, 262240.8388926737, 206673.48945768765, 55567.34943498608, 0.000232109), (2, 232480.171130082, 205323.08132330378, 27157.0898067782, 0.001089151), (3, 214433.24504336232, 197208.00572002697, 17225.239323335343, 0.001556355), (4, 199167.2470560674, 185627.82374713136, 13539.423308936024, 0.002074516), (5, 182000.38725134358, 167197.14654277608, 14803.240708567499, 0.002582762), (6, 164349.01456049876, 150441.96964651145, 13907.044913987298, 0.003123697), (7, 147512.85044971353, 131562.76880367586, 15950.081646037654, 0.003693956), (8, 142521.18375956157, 137171.39510788993, 5349.788651671628, 0.004138927), (9, 139713.61392422643, 136924.65804265282, 2788.955881573621, 0.004970901), (10, 138049.97053157684, 136780.5388951477, 1269.4316364291417, 0.005639097) … (192, 10290.712936831522, 10289.178455452178, 1.5344813793438234, 0.04848169), (193, 10289.195223265677, 10288.41528339026, 0.7799398754162118, 0.048646609), (194, 10287.719647930353, 10286.803355771115, 0.9162921592375912, 0.048834752), (195, 10286.284728522645, 10285.509938247222, 0.7747902754235838, 0.049001213), (196, 10284.889445685549, 10284.134679336086, 0.754766349462443, 0.049161495), (197, 10283.532645116327, 10282.797355512463, 0.7352896038646577, 0.049333043), (198, 10282.213303359109, 10281.537958753937, 0.6753446051718967, 0.049494657), (199, 10280.93031481118, 10280.127745220738, 0.8025695904413692, 0.049671233), (200, 10279.682429701206, 10279.002467610982, 0.679962090223853, 0.049850203), (200, 10279.682429701206, 10279.002467610982, 0.679962090223853, 0.050151917)])Plotting the resulting trajectory
We modify the y axis to highlight that we are plotting the DCA gap, not the FW gap
data = [res_dca.traj_data, res_boost.traj_data]
label = ["DCA-FW", "DCA-FW-B"]
p_res = plot_trajectories(data, label, marker_shapes=[:o, :x])
ylabel!(p_res.subplots[3], "DCA gap")display(p_res)This page was generated using Literate.jl.