API

accelerated_reflected_gradient(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The accelerated reflected gradient iterate.

Description

Given a constant step-size $\chi > 0$ and initial vectors $\mathbf{x}_1,\mathbf{x}_0 \in \mathbb{R}^n$, the basic $k$-th iterate of the accelerated reflected gradient (ARG) is the following [7]:

\[\begin{align*} \mathbf{y}_k &= 2\mathbf{x}_k - \mathbf{x}_{k-1} + \frac{1}{k+1} (\mathbf{x}_0 - \mathbf{x}_k) - \frac{1}{k}(\mathbf{x}_k - \mathbf{x}_{k-1}) \\ \mathbf{x}_{k+1} &= \text{prox}_{g,\mathcal{S}}\left(\mathbf{x}_k - \chi \mathbf{F}(\mathbf{y}_k) + \frac{1}{k+1}(\mathbf{x}_0 - \mathbf{x}_k)\right) \end{align*}\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the ARG algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{12L}\right)$.

adaptive_golden_ratio_algorithm(
    F;
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

Adaptive golden ratio algorithm

Description

The Adaptive Golden Ratio Algorithm (aGRAAL) algorithm is a variation of the Golden Ratio Algorithm, with adaptive step size. Following [8], let $\theta_0 = 1$, $\rho = 1/\phi + 1/ \phi^2$, where $\phi \in (0,\varphi]$ and $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. Moreover, let $\bar{\chi} \gg 0$ be a constant (arbitrarily large) step-size. Given the initial terms $\mathbf{x}_0,\mathbf{x}_1 \in \mathbb{R}^n$, $\mathbf{y}_0 = \mathbf{x}_1$, and $\chi_0 > 0$, the $k$-th iterate for aGRAAL is the following:

\[\begin{align*} \chi_k &= \min\left\{\rho\chi_{k-1}, \frac{\phi\theta_k \|\mathbf{x}_k -\mathbf{x}_{k-1}\|^2}{4\chi_{k-1}\|\mathbf{F}(\mathbf{x}_k) -\mathbf{F}(\mathbf{x}_{k-1})\|^2}, \bar{\chi}\right\} \\ \mathbf{x}_{k+1}, \mathbf{y}_{k+1} &= \texttt{golden\_ratio\_algorithm}(\mathbf{x}_k, \mathbf{y}_k, \chi_k, \phi) \\ \theta_{k+1} &= \phi\frac{\chi_k}{\chi_{k-1}} \end{align*}\]

The convergence guarantees discussed for GRAAL also hold for aGRAAL.

constrained_fast_optimistic_gradient_descent_ascent(
    F;
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

Constrained fast optimistic gradient descent-ascent iterate

Description

Given a constant step-size $\chi > 0$ and initial vectors $\mathbf{x}_1 \in \mathcal{S}$, $\mathbf{z}_1 \in N_{\mathcal{S}}(\mathbf{x}_1)$, $\mathbf{x}_0, \mathbf{y}_0 \in \mathbb{R}^n$, the basic $k$-th iterate of Constrained Fast Optimistic Gradient Descent Ascent (CFOGDA) is the following [9]:

\[\begin{align*} \mathbf{y}_k &= \mathbf{x}_k + \frac{k}{k+\alpha}(\mathbf{x}_k - \mathbf{x}_{k-1}) - \chi \frac{\alpha}{k+\alpha}(\mathbf{F}(\mathbf{y}_{k-1}) + \mathbf{z}_k) \\ \mathbf{x}_{k+1} &= \text{prox}_{g,\mathcal{S}}\left(\mathbf{y}_k - \chi\left(1 + \frac{k}{k+\alpha}\right)(\mathbf{F}(\mathbf{y}_k) - \mathbf{F} (\mathbf{y}_{k-1}) - \zeta_k)\right) \\ \mathbf{z}_{k+1} &= \frac{k+\alpha}{\chi (2k+\alpha)}( \mathbf{y}_k - \mathbf{x}_{k+1}) - (\mathbf{F}(\mathbf{y}_k) - \mathbf{F}(\mathbf{y}_{k-1}) - \zeta_k) \end{align*}\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the CFOGDA algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{4L}\right)$ and $\alpha > 2$.

extra_anchored_gradient(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The extra-anchored gradient iterate.

Description

Given a constant step-size $\chi > 0$ and an initial vector $\mathbf{x}_0 \in \mathbb{R}^n$, the $k$-th iterate of extra anchored gradient (EAG) algorithm is [10]:

\[\begin{align*} \mathbf{y}_k &= \text{prox}_{g,\mathcal{S}}\left(\mathbf{x}_k - \chi \mathbf{F}(\mathbf{x}_k) + \frac{1}{k+1}(\mathbf{x}_0 - \mathbf{x}_k)\right) \\ \mathbf{x}_{k+1} &= \text{prox}_{g,\mathcal{S}}\left(\mathbf{x}_k - \chi \mathbf{F}(\mathbf{y}_k) + \frac{1}{k+1}(\mathbf{x}_0 - \mathbf{x}_k)\right) \end{align*}\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the EAG algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{\sqrt{3}L} \right)$.

extragradient(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The extragradient iterate

Description

Given a constant step-size $\chi > 0$ and an initial vector $\mathbf{x}_0 \in \mathbb{R}^n$, the $k$-th iterate of the extragradient algorithm (EG) is [11]:

\[\begin{align*} \mathbf{y}_k &= \text{prox}_{\mathcal{S}}(\mathbf{x}_k - \chi \mathbf{F} (\mathbf{x}_k)) \\ \mathbf{x}_{k+1} &= \text{prox}_{\mathcal{S}}(\mathbf{y}_k - \chi \mathbf{F} (\mathbf{x}_k)) \end{align*}\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the EGD algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{L}\right)$.

fast_optimistic_gradient_descent_ascent(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

(Explicit) fast optimistic gradient descent-ascent iterate

Description

Given a constant step-size $\chi > 0$ and initial vectors $\mathbf{x}_1,\mathbf{x}_0, \mathbf{y}_0 \in \mathbb{R}^n$, the basic $k$-th iterate of the explicit fast OGDA (FOGDA) is the following [12]:

\[\begin{align*} \mathbf{y}_k &= \mathbf{x}_k + \frac{k}{k+\alpha}(\mathbf{x}_k - \mathbf{x}_{k-1}) - \chi \frac{\alpha}{k+\alpha} \mathbf{F}(\mathbf{y}_{k-1}) \\ \mathbf{x}_{k+1} &= \mathbf{y}_k - \chi \frac{2k+\alpha} {k+\alpha} (\mathbf{F}(\mathbf{y}_k) - \mathbf{F}(\mathbf{y}_{k-1})) \end{align*}\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the ARG algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{4L}\right)$ and $\alpha > 2$.

forward_backward_forward(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The forward-backward-forward iterate.

Description

Given a constant step-size $\chi > 0$ and an initial vector $\mathbf{x}_0 \in \mathbb{R}^n$, the $k$-th iterate of Forward-Backward-Forward (FBF) algorithm is [13]:

\[\begin{align*} \mathbf{y}_k &= \text{prox}_{\mathcal{S}}(\mathbf{x}_k - \chi F(\mathbf{x}_k)) \\ \mathbf{x}_{k+1} &= \mathbf{y}_k - \chi (F(\mathbf{y}_k) - \chi F(\mathbf{x}_k)) \end{align*}\]

where $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the FBF algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{L}\right)$.

forward_reflected_backward(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The forward-reflected-backward iterate.

Description

Given a constant step-size $\chi > 0$ and initial vectors $\mathbf{x}_1,\mathbf{x}_0 \in \mathbb{R}^n$, the basic $k$-th iterate of the Forward-Reflected-Backward (FRB) is the following [14]:

\[\mathbf{x}_{k+1} = \text{prox}_{g,\mathcal{S}}(\mathbf{x}_k - \chi (2\mathbf{F} (\mathbf{x}_k) + \mathbf{F}(\mathbf{x}_{k-1})))\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of the FRB algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{2L}\right)$.

golden_ratio_algorithm(
    F;
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

Golden ratio algorithm iterate

Description

Given a constant step-size $\chi > 0$ and initial vectors $\mathbf{x}_0,\mathbf{y}_0 \in \mathbb{R}^n$, the basic $k$-th iterate the golden ratio algorithm (GRAAL) is the following [8]:

\[\begin{align*} \mathbf{y}_{k+1} &= \frac{(\phi - 1)\mathbf{x}_k + \phi\mathbf{y}_k}{\phi} \\ \mathbf{x}_{k+1} &= \text{prox}_{g,\mathcal{S}}(\mathbf{y}_{k+1} - \chi \mathbf{F}(\mathbf{x}_k)) \end{align*}\]

The convergence of GRAAL algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constants $L < +\infty$, when $\chi \in \left(0,\frac{\varphi}{2L} \right]$ and $\phi \in (1,\varphi]$, where $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio.

hybrid_golden_ratio_algorithm_1(
    F;
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

Hybrid golden ratio algorithm I

Description

The HGRAAL-1 algorithm [15] is a variation of the Adaptive Golden Ratio Algorithm. Let $\theta_0 = 1$, $\rho = 1/\phi + 1/\phi^2$, where $\phi \in (0,\varphi]$ and $\varphi = \frac{1+\sqrt{5}}{2}$ is the golden ratio. The residual at point $\mathbf{x}_k$ is given by $J : \mathbb{R}^n \to \mathbb{R}$, defined as follows:

\[J(\mathbf{x}_k) = \|\mathbf{x}_k - \text{prox}_{g,\mathcal{S}} (\mathbf{x}_k - \mathbf{F}(\mathbf{x}_k))\|\]

Moreover, let $\bar{\chi} \gg 0$ be a constant (arbitrarily large) step-size. Given the initial terms $\mathbf{x}_0,\mathbf{x}_1 \in\mathbb{R}^n$, $\mathbf{y}_0 = \mathbf{x}_1$, and $\chi_0 > 0$, the $k$-th iterate for HGRAAL-1 is the following:

\[\begin{align*} \chi_k &= \min\left\{\rho\chi_{k-1}, \frac{\phi\theta_k \|\mathbf{x}_k -\mathbf{x}_{k-1}\|^2}{4\chi_{k-1}\|\mathbf{F}(\mathbf{x}_k) -\mathbf{F}(\mathbf{x}_{k-1})\|^2}, \bar{\chi}\right\} \\ c_k &= \left(\langle J(\mathbf{x}_k) - J(\mathbf{x}_{k-1}) > 0 \rangle \text{ and } \langle f_k \rangle \right) \text{ or } \left\langle \min\{J(\mathbf{x}_{k-1}), J(\mathbf{x}_k)\} < J(\mathbf{x}_k) + \frac{1}{\bar{k}} \right\rangle \\ f_k &= \text{not $\langle c_k \rangle$} \\ \bar{k} &= \begin{cases} \bar{k}+1 & \text{if $c_k$ is true} \\ \bar{k} & \text{otherwise} \end{cases} \\ \mathbf{y}_{k+1} &= \begin{cases} \dfrac{(\phi - 1)\mathbf{x}_k + \phi\mathbf{y}_k}{\phi} & \text{if $c_k$ is true} \\ \mathbf{x}_k & \text{otherwise} \end{cases} \\ \mathbf{x}_{k+1} &= \text{prox}_{g,\mathcal{S}}(\mathbf{y}_{k+1} - \chi_k \mathbf{F}(\mathbf{x}_k)) \\ \theta_{k+1} &= \phi\frac{\chi_k}{\chi_{k-1}} \end{align*}\]

popov(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The Popov's method iterate

Description

Given a constant step-size $\chi > 0$ and an initial vectors $\mathbf{x}_0,\mathbf{y}_0 \in \mathbb{R}^n$, the $k$-th iterate of Popov's Method (PM) is [16]:

\[\begin{align*} \mathbf{y}_{k+1} &= \text{prox}_{g,\mathcal{S}}(\mathbf{x}_k - \chi \mathbf{F} (\mathbf{y}_k)) \\ \mathbf{x}_{k+1} &= \text{prox}_{g,\mathcal{S}}(\mathbf{y}_{k+1} - \chi \mathbf{F}(\mathbf{x}_k)) \end{align*}\]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of PM is guaranteed for Lipschitz monotone operators, with Lipschitz constant $L < +\infty$, when $\chi \in \left(0,\frac{1}{2L}\right)$.

projected_reflected_gradient(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The projected reflected gradient iterate.

Description

Given a constant step-size $\chi > 0$ and initial vectors $\mathbf{x}_1,\mathbf{x}_0 \in \mathbb{R}^n$, the basic $k$-th iterate of the projected reflected gradient (PRG) is the following [17]:

\[\mathbf{x}_{k+1} = \text{prox}_{g,\mathcal{S}}(\mathbf{x}_k - \chi \mathbf{F}(2\mathbf{x}_k - \mathbf{x}_{k-1})) \]

where $g : \mathbb{R}^n \to \mathbb{R}$ is a scalar convex (possibly non-smooth) function, while $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of PRG algorithm is guaranteed for Lipschitz monotone operators, with Lipschitz constants $L < +\infty$, when $\chi \in (0,(\sqrt{2} - 1)/L)$. Differently from the EGD iteration, the PRGD has the advantage of requiring a single proximal operator evaluation.

prox(
    y::AbstractArray{VariableRef},
    model::Model;
    g=nothing,
    norm_cone=MOI.SecondOrderCone,
)

The proximal operator iterate.

Arguments

• y::AbstractVector{VariableRef} - the container of JuMP.VariableRef associated to model, i.e., $\mathbf{y}$.
• model::Model - the JuMP.Model describing the projection set $\mathcal{S}$.

Keywords

• g::Function=nothing - a function of the form x::AbstractVector{VariableRef} -> Real, i.e., the scalar function $g : \mathbb{R}^n \to \mathbb{R}$.
• norm_cone=MOI.SecondOrderCone - the cone related to the norm characterizing the proximal operator.

proximal_gradient(
    F; 
    g = x -> 0,
    y::Union{Nothing, AbstractArray{VariableRef}} = nothing,
    model::Union{Nothing, Model} = nothing,
    norm_cone=MOI.SecondOrderCone,
    analytical_prox = identity
)

The proximal gradient iterate.

Description

Given a constant step-size $\chi > 0$ and an initial vector $\mathbf{x}_0 \in \mathbb{R}^n$, the basic $k$-th iterate of the proximal gradient (PG) algorithm is [18]:

\[\mathbf{x}_{k+1} = \text{prox}_{g,\mathcal{S}}(\mathbf{x}_k - \chi \mathbf{F}(\mathbf{x}_k))\]

where $\mathbf{F} : \mathbb{R}^n \to \mathbb{R}^n$ is the VI mapping. The convergence of PG is guaranteed for Lipschitz strongly monotone operators, with monotone constant $\mu > 0$ and Lipshitz constants $L < +\infty$, when $\chi \in (0, 2\mu/L^2)$.