PEPit.primitive_steps.epsilon_subgradient_step

PEPit.primitive_steps.epsilon_subgradient_step(x0, f, gamma)

This routines performs a step \(x \leftarrow x_0 - \gamma g_0\) where \(g_0 \in\partial_{\varepsilon} f(x_0)\). That is, \(g_0\) is an \(\varepsilon\)-subgradient of \(f\) at \(x_0\). The set \(\partial_{\varepsilon} f(x_0)\) (referred to as the \(\varepsilon\)-subdifferential) is defined as (see [1, Section 3])

\[\partial_{\varepsilon} f(x)=\left\{g:\, f(z)\geqslant f(x)+\left< g;\, z-x \right>-\varepsilon \right\}.\]

An alternative characterization of \(g_0 \in\partial_{\varepsilon} f(x_0)\) consists in writing

\[f(x_0)+f^*(g_0)-\left< g_0;x_0\right>\leqslant \varepsilon.\]

References

[1] A. Brøndsted, R.T. Rockafellar. On the subdifferentiability of convex functions. Proceedings of the American Mathematical Society 16(4), 605–611 (1965)

Parameters

• x0 (Point) – starting point x0.

• f (Function) – a function.

• gamma (float) – the step size parameter.

Returns

• x (Point) – the output point.

• g0 (Point) – an \(\varepsilon\)-subgradient of f at x0.

• f0 (Expression) – the value of the function f at x0.

• epsilon (Expression) – the value of epsilon.