Davis-Yin with Delay#

Davis-Yin Splitting is an algorithm to find a zero of the sum of three operators [1]. The Davis-Yin algorithm with parameters \((\lambda, \gamma)>0\) is described as

\[\begin{split}\begin{align*} \mat{c}{x_{k+1} \hl z_k^1 \\ z_k^2 \\ z_k^3} &= \mat{c|cc}{I & - \lambda \gamma I & - \lambda \gamma I & - \lambda \gamma I \hl I & - \gamma I & 0 & 0\\ I & - \gamma I & 0 & 0\\ I & -2 \gamma I & - I\gamma & I\gamma} \mat{c}{x_{k} \hl w_k^1 \\ w_k^2}, & \mat{c}{w_k^1 \\ w_k^2 \\ w_k^3} \in \mat{c}{F_1(z_k^1) \\ F_2(z_k^2) \\ F_3(z_k^2)}. \end{align*}\end{split}\]

This example analyzes the Davis-Yin splitting method under time delays. The operator \(F_2\) is evaluated remotely: there is an \(h\) step time delay to reach \(F_2\), and another \(h\) time steps are required to acquire the evaulation of \(F_2\).

All operators are subdifferentials of functions in \(S_{m, L}\).

\(F_1\) is p.c.c.
\(F_2 \in S_{1, 1.5}\)
\(F_3 \in S_{0, L_3}\) for a paramter \(0 < L \leq \infty\).

The non-delayed Davis-Yin can only achieve linear convergence if \(L_3 < \infty\) (Theorem 1, 2 of [2]).

Analysis is performed with orders for Davis-Yin with delays \(h \in \{0, \ldots, 4\}\). The parameters \(\gamma = 1/{L_3}, \lambda = 1\) are used to define the algorithm \(L_3\) is swept in the range \([10^{-2}, 10^{-3}]\). Figure 1 plots the outcome of an Analysis run using order [2, 0] at every operator. The stability boundary is the line \(\rho=1\). The other curves are the convergence rate \(\rho\) as a monotonically increasing function of delay: \(h=0\) on the bottom in blue and \(h=4\) on top with green. The Davis-Yin algorithm with these parameters is certified as convergent without delay, and is not certified as convergent with delay.

../../_images/davis_yin_delay_dark.png — *Figure 1:* Davis-Yin with \(\gamma = 1/{L_3}\) with delays#

../../_images/davis_yin_delay_light.png — *Figure 1:* Davis-Yin with \(\gamma = 1/{L_3}\) with delays#

Figure 2 plots the same curves with Davis-Yin parameters \(\gamma = 1/(2{L_3}), \lambda = 0.\)

../../_images/davis_yin_delay_half_dark.png — *Figure 2:* Davis-Yin with \(\gamma = 1/(2{L_3})\) with delays#

../../_images/davis_yin_delay_half_light.png — *Figure 2:* Davis-Yin with \(\gamma = 1/(2{L_3})\) with delays#

Code for delayed Davis-Yin analysis at multiple orders, values of \(L_3\), and delays \(h\)#

%sweep of L3
NL = 100;
L_all = logspace(-2, 3, NL);

%define base operators
m = [0, 1, 0];
L = [inf, 1.5, inf];
ops= cell(1, 3);
for i = 1:3
    ops{i} = op_sml(m(i), L(i));    
end

%outer loops
orderlist = {0, 1, [0, 1], [1, 1], 2, [0, 2]};
delaylist = 0:4;
Ndelay = length(delaylist);
Norder = length(orderlist);

rho_best = zeros(NL, 1);
rho_bound = zeros(NL, Norder, Ndelay);
parfor j = 1:NL
    for k = 1:Ndelay
        delay = delaylist(k);
        ops_curr = ops;        
        ops_curr{3}.L = L_all(j);
        
        %davis-yin algorithm
        lambda = 1;        
        gamma = 1/L(2); % or gamma = 1/(2*L(2));
        K = ss([1], [-gamma*lambda, -gamma*lambda, -gamma*lambda], [1; 1; 1], ...
            [-gamma, 0, 0; ...
            -gamma, 0, 0; ...
            -2*gamma, -gamma, -gamma],1);

        %form the system
        network = bridge_channel_delay([0, delay, 0], [0, delay, 0]);
        sys = opt_system(ops_curr, network, K);
    
        %perform analysis at each order
        man = opt_analysis(sys);
        for i = 1:Norder        
            order_curr = repmat({orderlist{i}}, 1, 3);
            sol = man.bisect(order_curr);               
            rho_bound(j, i, k) = sol.rho;    
        end
    end
end


%% plot the result


figure(k)
clf
plot(L_all, squeeze(rho_bound(:, 4, :)), 'linewidth', 2);
hold on
    set(gca, 'Xscale', 'Log')
    ylabel('$\rho$', 'interpreter', 'latex','Fontsize', 14)
    xlabel('$L_3$', 'interpreter', 'latex','Fontsize', 14)
    xlim([L_all(1), L_all(end)])

plot(L_all, ones(size(L_all)), ':', 'LineWidth', 2, 'color', 0.5*[1,1,1])