Gradient Flow Strongly Convex
wc_gradient_flow_strongly_convex(mu; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_gradient_flow_strongly_convex.
Consider the convex minimization problem
\[f_\star \triangleq \min_x f(x),\]
where $f$ is $\mu$-strongly convex.
Performance metric
This code computes a worst-case guarantee for a gradient flow. That is, it computes the smallest possible $\tau(\mu)$ such that the guarantee
\[\frac{d}{dt}\mathcal{V}(X_t) \leqslant -\tau(\mu)\mathcal{V}(X_t) ,\]
is valid, where $\mathcal{V}(X_t) = f(X_t) - f(x_\star)$, $X_t$ is the output of the gradient flow, and where $x_\star$ is the minimizer of $f$. In short, for given values of $\mu$, $\tau(\mu)$ is computed as the worst-case value of the derivative $f(X_t)-f_\star$ when $f(X_t) - f(x_\star)\leqslant 1$.
Algorithm
For $t \geqslant 0$,
\[\frac{d}{dt}X_t = -\nabla f(X_t),\]
with some initialization $X_{0}\triangleq x_0$.
Theoretical guarantee
The following **tight** guarantee can be found in [1, Proposition 11]:\[\frac{d}{dt}\mathcal{V}(X_t) \leqslant -2\mu\mathcal{V}(X_t).\]
The detailed approach using PEPs is available in [2, Theorem 2.1].References
Arguments
mu: strong convexity or monotonicity parameter, as used by the modeled class.solver: JuMP optimizer constructor used to solve the generated SDP.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_gradient_flow_strongly_convex(0.1; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (-0.2, -0.2)