Main.check_gradients

Exact Optimization with Rational Arithmetic

This example can be found in section 4.3 in the paper. The package allows for exact optimization with rational arithmetic. For this, it suffices to set up the LMO to be rational and choose an appropriate step-size rule as detailed below. For the LMOs included in the package, this simply means initializing the radius with a rational-compatible element type, e.g., 1, rather than a floating-point number, e.g., 1.0. Given that numerators and denominators can become quite large in rational arithmetic, it is strongly advised to base the used rationals on extended-precision integer types such as BigInt, i.e., we use Rational{BigInt}.

The second requirement ensuring that the computation runs in rational arithmetic is a rational-compatible step-size rule. The most basic step-size rule compatible with rational optimization is the agnostic step-size rule with $\gamma_t = 2/(2 + t)$. With this step-size rule, the gradient does not even need to be rational as long as the atom computed by the LMO is of a rational type. Assuming these requirements are met, all iterates and the computed solution will then be rational.

using FrankWolfe
using LinearAlgebra

n = 100
k = n

x = fill(big(1) // 100, n)

f(x) = dot(x, x)
function grad!(storage, x)
@. storage = 2 * x
end
grad! (generic function with 1 method)

pick feasible region radius needs to be integer or rational

lmo = FrankWolfe.ProbabilitySimplexOracle{Rational{BigInt}}(1)
FrankWolfe.ProbabilitySimplexOracle{Rational{BigInt}}(1//1)

compute some initial vertex

x0 = FrankWolfe.compute_extreme_point(lmo, zeros(n));

x, v, primal, dual_gap, trajectory = FrankWolfe.frank_wolfe(
f,
grad!,
lmo,
x0,
max_iteration=k,
line_search=FrankWolfe.Agnostic(),
print_iter=k / 10,
verbose=true,
memory_mode=FrankWolfe.OutplaceEmphasis(),
);

println("\nOutput type of solution: ", eltype(x))

Vanilla Frank-Wolfe Algorithm.
MEMORY_MODE: FrankWolfe.OutplaceEmphasis() STEPSIZE: Agnostic(2) EPSILON: 1.0e-7 MAXITERATION: 100 TYPE: Rational{BigInt}
MOMENTUM: nothing GRADIENTTYPE: Nothing
LMO: FrankWolfe.ProbabilitySimplexOracle{Rational{BigInt}}

-------------------------------------------------------------------------------------------------
Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec
-------------------------------------------------------------------------------------------------
I             1   1.000000e+00  -1.000000e+00   2.000000e+00   0.000000e+00            Inf
FW            10   1.407407e-01  -1.407407e-01   2.814815e-01   1.295124e-01   7.721268e+01
FW            20   6.842105e-02  -6.842105e-02   1.368421e-01   1.317204e-01   1.518368e+02
FW            30   4.521073e-02  -4.521073e-02   9.042146e-02   1.338340e-01   2.241583e+02
FW            40   3.376068e-02  -3.376068e-02   6.752137e-02   1.363180e-01   2.934314e+02
FW            50   2.693878e-02  -2.693878e-02   5.387755e-02   1.388166e-01   3.601874e+02
FW            60   2.241055e-02  -2.241055e-02   4.482109e-02   1.415865e-01   4.237693e+02
FW            70   1.918565e-02  -1.918565e-02   3.837129e-02   1.445020e-01   4.844225e+02
FW            80   1.677215e-02  -1.677215e-02   3.354430e-02   1.473149e-01   5.430545e+02
FW            90   1.489804e-02  -1.489804e-02   2.979609e-02   1.505632e-01   5.977557e+02
FW           100   1.340067e-02  -1.340067e-02   2.680135e-02   1.537524e-01   6.503962e+02
Last           101   1.314422e-02  -1.236767e-02   2.551189e-02   1.548398e-01   6.522872e+02
-------------------------------------------------------------------------------------------------

Output type of solution: BigFloat

Another possible step-size rule is rationalshortstep which computes the step size by minimizing the smoothness inequality as $\gamma_t=\frac{\langle \nabla f(x_t),x_t-v_t\rangle}{2L||x_t-v_t||^2}$. However, as this step size depends on an upper bound on the Lipschitz constant $L$ as well as the inner product with the gradient $\nabla f(x_t)$, both have to be of a rational type.

@time x, v, primal, dual_gap, trajectory = FrankWolfe.frank_wolfe(
f,
grad!,
lmo,
x0,
max_iteration=k,
line_search=FrankWolfe.Shortstep(2 // 1),
print_iter=k / 10,
verbose=true,
memory_mode=FrankWolfe.OutplaceEmphasis(),
);

Vanilla Frank-Wolfe Algorithm.
MEMORY_MODE: FrankWolfe.OutplaceEmphasis() STEPSIZE: Shortstep EPSILON: 1.0e-7 MAXITERATION: 100 TYPE: Rational{BigInt}
MOMENTUM: nothing GRADIENTTYPE: Nothing
LMO: FrankWolfe.ProbabilitySimplexOracle{Rational{BigInt}}

-------------------------------------------------------------------------------------------------
Type     Iteration         Primal           Dual       Dual Gap           Time         It/sec
-------------------------------------------------------------------------------------------------
I             1   1.000000e+00  -1.000000e+00   2.000000e+00   0.000000e+00            Inf
FW            10   1.000000e-01  -1.000000e-01   2.000000e-01   1.282282e-01   7.798596e+01
FW            20   5.000000e-02  -5.000000e-02   1.000000e-01   1.304289e-01   1.533402e+02
FW            30   3.333333e-02  -3.333333e-02   6.666667e-02   1.325700e-01   2.262956e+02
FW            40   2.500000e-02  -2.500000e-02   5.000000e-02   1.347920e-01   2.967536e+02
FW            50   2.000000e-02  -2.000000e-02   4.000000e-02   1.372821e-01   3.642135e+02
FW            60   1.666667e-02  -1.666667e-02   3.333333e-02   1.397531e-01   4.293286e+02
FW            70   1.428571e-02  -1.428571e-02   2.857143e-02   1.423099e-01   4.918842e+02
FW            80   1.250000e-02  -1.250000e-02   2.500000e-02   1.451322e-01   5.512216e+02
FW            90   1.111111e-02  -1.111111e-02   2.222222e-02   1.482542e-01   6.070653e+02
FW           100   1.000000e-02   1.000000e-02   1.889162e-78   1.516980e-01   6.592043e+02
Last           100   1.000000e-02   1.000000e-02   2.159042e-78   1.524985e-01   6.557440e+02
-------------------------------------------------------------------------------------------------
0.342815 seconds (1.01 M allocations: 61.465 MiB, 91.43% compilation time)

Note: at the last step, we exactly close the gap, finding the solution 1//n * ones(n)

This page was generated using Literate.jl.