Difference Of Convex Algorithm
wc_difference_of_convex_algorithm(mu1, mu2, L1, L2, n, alpha=0; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_difference_of_convex_algorithm.
Consider the minimization problem
\[F_\star \triangleq \min_x f_1(x)-f_2(x),\]
where $f_1$ and $f_2$ are convex functions, respectively $L_1$-smooth and $\mu_1$-strongly convex and $L_2$-smooth and $\mu_2$-strongly convex.
Performance metric
This code computes a worst-case guarantee for DCA (difference-of-convex algorithm, also known as the convex-concave procedure). That is, it computes the smallest possible $\tau(n, \mu_1, L_1,\mu_2, L_2)$ such that the guarantee
\[\min_{t\leqslant n} \|\nabla f_1(x_t)-\nabla f_2(x_t)\|^2 \leqslant \tau(n, \mu_1, L_1,\mu_2, L_2) (f_1(x_0)-f_2(x_0)-F_\star)\]
is valid, where $x_n$ is the n-th iterates obtained with DCA.
Algorithm
DCA is described as follows, for $t \in \{ 0, \dots, n-1\}$,
\[x_{t+1} \in \mathrm{argmin}_x\,\{ f_1(x) - \langle \nabla f_2(x_t), x\rangle\},\]
Theoretical guarantee
The results are compared with [1, Theorem 3]; a more complete picture can be obtained from [2], also by possibly allowing for non-convex functions $f_1$ and $f_2$ (i.e., possibly negative values for $\mu_1$, $\mu_2$).
References
Arguments
mu1: strong convexity parameter for f1.mu2: strong convexity parameter for f2.L1: smoothness parameter for f1.L2: smoothness parameter for f2.n: number of iterations.alpha: algorithm parameter used in the update rule.solver: JuMP optimizer constructor used to solve the generated SDP.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case value.theoretical_tau: reference theoretical value [1, Theorem 3].
Julia usage
pepit_tau, theoretical_tau = wc_difference_of_convex_algorithm(mu1, mu2, L1, L2, 5, 0; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.491131, 0.491131)