Function classes
The following exported types model interpolation constraints for common classes of scalar functions. Parameters are supplied through an OrderedDict, matching the examples in PEPit.jl/examples.
PEPit.AbstractFunction — Type
AbstractFunctionAbstract supertype for function and operator classes that can participate in a PEP.
Concrete subtypes represent interpolation models for classes of scalar functions or operators. They wrap a PEPFunction, expose oracle methods such as gradient!, value!, stationary_point!, or fixed_point!, and implement add_class_constraints! to add the class-specific interpolation constraints before the SDP is solved.
Implementation
New function or operator classes should subtype AbstractFunction, store an internal PEPFunction, forward oracle calls to it, and implement add_class_constraints!. The concrete class is then passed to declare_function!.
PEPit.ConvexFunction — Type
ConvexFunction(param=OrderedDict(); reuse_gradient=false)Interpolation class of convex, closed, and proper (CCP) functions (convex functions whose epigraphs are non-empty closed sets).
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
General CCP functions are not characterized by any parameter, so param may be left empty.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, subgradient, and function value, the following constraint is added for every pair $i \neq j$:
\[f_i - f_j \geqslant \langle g_j, x_i - x_j \rangle.\]
Julia usage
problem = PEP()
f = declare_function!(problem, ConvexFunction, OrderedDict())Fields
_PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
See also declare_function!, StronglyConvexFunction, SmoothConvexFunction, and ConvexLipschitzFunction.
PEPit.ConvexLipschitzFunction — Type
ConvexLipschitzFunction(param; reuse_gradient=false)Interpolation class of convex, closed, and proper (CCP) functions that are $M$-Lipschitz continuous.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["M"]: Lipschitz continuity parameter $M$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, subgradient, and function value, the following constraints are added (see [1]):
\[\begin{aligned} f_i - f_j & \geqslant \langle g_j, x_i - x_j \rangle && \text{for all } i \neq j, \\ \|g_i\|^2 & \leqslant M^2 && \text{for all } i \text{ (added when } M < \infty\text{)}. \end{aligned}\]
Julia usage
problem = PEP()
param = OrderedDict("M" => 1.0)
f = declare_function!(problem, ConvexLipschitzFunction, param)With M == Inf the Lipschitz bound adds no constraint, so the class coincides with ConvexFunction; the constructor emits a warning in that case.
Fields
M::Float64: Lipschitz continuity parameter $M$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, ConvexFunction, and SmoothConvexLipschitzFunction.
PEPit.SmoothFunction — Type
SmoothFunction(param; reuse_gradient=true)Interpolation class of $L$-smooth (not necessarily convex) functions.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["L"]: smoothness parameter $L$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, gradient, and function value, the following constraint is added for every pair $i \neq j$ (see [1]):
\[f_i - f_j \geqslant -\frac{L}{4} \|x_i - x_j\|^2 + \frac{1}{2} \langle g_i + g_j, x_i - x_j \rangle + \frac{1}{4L} \|g_i - g_j\|^2.\]
Julia usage
problem = PEP()
param = OrderedDict("L" => 1.0)
f = declare_function!(problem, SmoothFunction, param)Smooth functions are necessarily differentiable, hence reuse_gradient is set to true. With L == Inf the class implies no constraint and contains all differentiable functions.
Fields
L::Float64: smoothness parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, SmoothConvexFunction, and SmoothStronglyConvexFunction.
PEPit.SmoothConvexFunction — Type
SmoothConvexFunction(param; reuse_gradient=true)Interpolation class of $L$-smooth convex functions.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["L"]: smoothness parameter $L$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, gradient, and function value, the following constraint is added for every pair $i \neq j$ (see [1, Theorem 4] with $\mu = 0$):
\[f_i - f_j \geqslant \langle g_j, x_i - x_j \rangle + \frac{1}{2L} \|g_i - g_j\|^2.\]
Julia usage
problem = PEP()
param = OrderedDict("L" => 1.0)
f = declare_function!(problem, SmoothConvexFunction, param)Smooth convex functions are necessarily differentiable, hence reuse_gradient is set to true. To model a convex function that is not smooth, use ConvexFunction rather than L == Inf.
Fields
L::Float64: smoothness parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, ConvexFunction, and SmoothStronglyConvexFunction.
PEPit.SmoothStronglyConvexFunction — Type
SmoothStronglyConvexFunction(param; reuse_gradient=true)Interpolation class of $L$-smooth $\mu$-strongly convex functions.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["mu"]: strong convexity parameter $\mu$.param["L"]: smoothness parameter $L$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, gradient, and function value, the following constraint is added for every pair $i \neq j$ (see [1, Theorem 4]):
\[f_i - f_j \geqslant \langle g_j, x_i - x_j \rangle + \frac{1}{2L} \|g_i - g_j\|^2 + \frac{\mu}{2 \left(1 - \mu/L\right)} \left\| x_i - x_j - \frac{1}{L} (g_i - g_j) \right\|^2.\]
Julia usage
problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
f = declare_function!(problem, SmoothStronglyConvexFunction, param)Smooth strongly convex functions are necessarily differentiable, hence reuse_gradient is set to true. To model a strongly convex function that is not smooth, use StronglyConvexFunction rather than L == Inf.
Fields
mu::Float64: strong convexity parameter $\mu$.L::Float64: smoothness parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, SmoothConvexFunction, and StronglyConvexFunction.
PEPit.StronglyConvexFunction — Type
StronglyConvexFunction(param; reuse_gradient=false)Interpolation class of $\mu$-strongly convex closed proper functions (strongly convex functions whose epigraphs are non-empty closed sets).
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["mu"]: strong convexity parameter $\mu$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, subgradient, and function value, the following constraint is added for every pair $i \neq j$ (see [1]):
\[f_i - f_j \geqslant \langle g_j, x_i - x_j \rangle + \frac{\mu}{2} \|x_i - x_j\|^2.\]
Julia usage
problem = PEP()
param = OrderedDict("mu" => 0.1)
f = declare_function!(problem, StronglyConvexFunction, param)Fields
mu::Float64: strong convexity parameter $\mu$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, ConvexFunction, and SmoothStronglyConvexFunction.
PEPit.ConvexIndicatorFunction — Type
ConvexIndicatorFunction(param=OrderedDict(); reuse_gradient=false)Interpolation class of closed convex indicator functions, optionally with a bounded feasible set (through its diameter $D$ and/or its radius $R$).
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["D"](optional, defaultInf): upper bound $D$ on the diameter of the feasible set.param["R"](optional, defaultInf): upper bound $R$ on the radius of the feasible set.param["center"](optional, defaultnothing): centerPointused by the radius constraint.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$, where $g_i$ is a subgradient of the indicator at the (feasible) point $x_i$, the following constraints are added (see [1]):
\[\begin{aligned} f_i & = 0 && \text{for all } i, \\ 0 & \geqslant \langle g_j, x_i - x_j \rangle && \text{for all } i \neq j, \\ \|x_i - x_j\|^2 & \leqslant D^2 && \text{for all } i \neq j \text{ (added when } D < \infty\text{)}, \\ \|x_i - c\|^2 & \leqslant R^2 && \text{for all } i \text{ (added when } R < \infty\text{)}, \end{aligned}\]
where $c$ is the center of the radius constraint.
Julia usage
problem = PEP()
param = OrderedDict("D" => 1.0)
f = declare_function!(problem, ConvexIndicatorFunction, param)When R < Inf and no "center" is supplied, the constructor automatically creates a fresh Point to act as the (otherwise unspecified) center $c$.
Fields
D::Float64: diameter bound $D$.R::Float64: radius bound $R$.center::Union{Point,Nothing}: center of the radius constraint._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, ConvexFunction, and ConvexSupportFunction.
PEPit.ConvexQGFunction — Type
ConvexQGFunction(param; reuse_gradient=false)Interpolation class of convex and quadratically upper bounded ($\text{QG}^+$ [1]) functions, that is, convex functions satisfying $f(x) - f_\star \leqslant \frac{L}{2} \|x - x_\star\|^2$ for all $x$.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["L"]: quadratic upper bound parameter $L$.
Interpolation conditions
A stationary point $(x_\star, g_\star = 0, f_\star)$ is created automatically if none was requested through stationary_point!. Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, subgradient, and function value, the following constraints are added (see [1]):
\[\begin{aligned} f_\star - f_j & \geqslant \langle g_j, x_\star - x_j \rangle + \frac{1}{2L} \|g_j\|^2 && \text{for all } j \text{ with } x_j \neq x_\star, \\ f_i - f_j & \geqslant \langle g_j, x_i - x_j \rangle && \text{for all } i \neq j. \end{aligned}\]
Julia usage
problem = PEP()
param = OrderedDict("L" => 1.0)
f = declare_function!(problem, ConvexQGFunction, param)Fields
L::Float64: quadratic upper bound parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, stationary_point!, and ConvexFunction.
PEPit.ConvexSupportFunction — Type
ConvexSupportFunction(param=OrderedDict(); reuse_gradient=false)Interpolation class of closed convex support functions, optionally with a bounded Lipschitz constant $M$ (equivalently, support functions of sets contained in a ball of radius $M$).
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["M"](optional, defaultInf): upper bound $M$ on the Lipschitz constant.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$, where $g_i$ is a subgradient of the support function at $x_i$ (that is, a maximizing element of the underlying set), the following constraints are added (see [1]):
\[\begin{aligned} \langle g_i, x_i \rangle - f_i & = 0 && \text{for all } i, \\ \|g_i\|^2 & \leqslant M^2 && \text{for all } i \text{ (added when } M < \infty\text{)}, \\ \langle x_j, g_i - g_j \rangle & \leqslant 0 && \text{for all } i \neq j. \end{aligned}\]
Julia usage
problem = PEP()
param = OrderedDict("M" => 1.0)
f = declare_function!(problem, ConvexSupportFunction, param)Fields
M::Float64: Lipschitz constant bound $M$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, ConvexFunction, and ConvexIndicatorFunction.
PEPit.RsiEbFunction — Type
RsiEbFunction(param; reuse_gradient=false)Interpolation class of functions verifying the "lower" restricted secant inequality ($\text{RSI}^-$) and the "upper" error bound ($\text{EB}^+$).
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["mu"]: restricted secant inequality parameter $\mu$.param["L"]: error bound parameter $L$.
Interpolation conditions
A stationary point $(x_\star, g_\star = 0, f_\star)$ is created automatically if none was requested through stationary_point!. Associating with each oracle call $j$ the triplet $(x_j, g_j, f_j)$ of point, subgradient, and function value, the following constraints are added for every stationary triplet and every $j$ with $x_j \neq x_\star$:
\[\begin{aligned} \langle g_\star - g_j, x_\star - x_j \rangle & \geqslant \mu \|x_\star - x_j\|^2 && (\text{RSI}^-), \\ \|g_\star - g_j\|^2 & \leqslant L^2 \|x_\star - x_j\|^2 && (\text{EB}^+). \end{aligned}\]
Julia usage
problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
f = declare_function!(problem, RsiEbFunction, param)Fields
mu::Float64: restricted secant inequality parameter $\mu$.L::Float64: error bound parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
A definition of the class of $\text{RSI}^-$ and $\text{EB}^+$ functions can be found in [1].
See also declare_function! and stationary_point!.
PEPit.SmoothConvexLipschitzFunction — Type
SmoothConvexLipschitzFunction(param; reuse_gradient=true)Interpolation class of $L$-smooth convex functions that are $M$-Lipschitz continuous.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["L"]: smoothness parameter $L$.param["M"]: Lipschitz continuity parameter $M$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, gradient, and function value, the following constraints are added (see [1]):
\[\begin{aligned} f_i - f_j & \geqslant \langle g_j, x_i - x_j \rangle + \frac{1}{2L} \|g_i - g_j\|^2 && \text{for all } i \neq j, \\ \|g_i\|^2 & \leqslant M^2 && \text{for all } i. \end{aligned}\]
Julia usage
problem = PEP()
param = OrderedDict("L" => 1.0, "M" => 1.0)
f = declare_function!(problem, SmoothConvexLipschitzFunction, param)Smooth convex Lipschitz continuous functions are necessarily differentiable, hence reuse_gradient is set to true. To drop the smoothness requirement, use ConvexLipschitzFunction rather than L == Inf.
Fields
L::Float64: smoothness parameter $L$.M::Float64: Lipschitz continuity parameter $M$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, SmoothConvexFunction, and ConvexLipschitzFunction.
PEPit.SmoothStronglyConvexQuadraticFunction — Type
SmoothStronglyConvexQuadraticFunction(param; reuse_gradient=true)Interpolation class of $L$-smooth $\mu$-strongly convex quadratic functions, that is, functions of the form $f(x) = \frac{1}{2} \langle x - x_\star, H (x - x_\star) \rangle + f_\star$ with $\mu I \preceq H \preceq L I$.
Overrides add_class_constraints! to add the interpolation conditions of the class when solve! builds the SDP.
Class parameters
param["mu"]: strong convexity parameter $\mu$.param["L"]: smoothness parameter $L$.
Interpolation conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ of point, gradient, and function value, and denoting by $(x_\star, 0, f_\star)$ the stationary point of the quadratic, the following constraints are added (see [1]):
\[\begin{aligned} f_i - f_\star & = \tfrac{1}{2} \langle g_i, x_i - x_\star \rangle && \text{for all } i, \\ \langle g_j, x_i - x_\star \rangle & = \langle g_i, x_j - x_\star \rangle && \text{for all } i < j, \end{aligned}\]
together with the PSD constraint $T \succeq 0$, where $T$ is the matrix of expressions with entries
\[T_{ij} = (L + \mu) \langle g_i, x_j - x_\star \rangle - \langle g_i, g_j \rangle - \mu L \langle x_i - x_\star, x_j - x_\star \rangle,\]
which is the Gram-space formulation of $(L I - H)(H - \mu I) \succeq 0$.
Julia usage
problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
f = declare_function!(problem, SmoothStronglyConvexQuadraticFunction, param)The constructor automatically creates the (unique) stationary point of the quadratic; stationary_point! returns that same point instead of creating a new one. Smooth strongly convex quadratic functions are necessarily differentiable, hence reuse_gradient is set to true.
Fields
mu::Float64: strong convexity parameter $\mu$.L::Float64: smoothness parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, stationary_point!, SmoothStronglyConvexFunction, and PSDMatrix.
PEPit.SmoothQuadraticLojasiewiczFunctionCheap — Type
SmoothQuadraticLojasiewiczFunctionCheap(param; reuse_gradient=true)Class of $L$-smooth (not necessarily convex) functions that also satisfy a quadratic Łojasiewicz inequality (sometimes also referred to as a Polyak-Łojasiewicz inequality) with parameter $\mu$. Extensive descriptions of such classes of functions can be found in [1, 2]. The conditions implemented here are presented in [4, Proposition 3.2] (for alpha to be chosen) and [4, Proposition 3.4] with smoothness conditions from [3].
Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.
Smooth functions satisfying a Łojasiewicz property do not enjoy known interpolation conditions. The conditions implemented in this class are necessary but a priori not sufficient for interpolation. Hence, the numerical results obtained when using this class might be non-tight upper bounds.
Class parameters
param["mu"]: quadratic Łojasiewicz parameter $\mu$ (with $0 \leqslant \mu \leqslant L$).param["L"]: smoothness parameter $L$.param["alpha"](optional, defaultnothing): relaxation parameter $\alpha \in [0, 2\mu/(2L+\mu)]$.
Necessary conditions
A stationary point $(x_\star, g_\star = 0, f_\star)$ is created automatically if none was requested through stationary_point!. Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$, the following constraints are added:
\[\begin{aligned} \frac{1}{2L} \|g_i\|^2 \leqslant f_i - f_\star & \leqslant \frac{1}{2\mu} \|g_i\|^2 && \text{for all } i \text{ with } x_i \neq x_\star, \\ f_i - f_j & \geqslant \frac{1}{2} \langle g_i + g_j, x_i - x_j \rangle + \frac{1}{4L} \|g_i - g_j\|^2 - \frac{L}{4} \|x_i - x_j\|^2 && \text{for all } i \neq j. \end{aligned}\]
When alpha is provided, the smoothness conditions are strengthened, for all $i \neq j$, into (see [4, Proposition 3.2]):
\[f_i - f_j \geqslant \frac{1}{2} \langle g_i + g_j, x_i - x_j \rangle + \frac{1}{4L} \|g_i - g_j\|^2 - \frac{L}{4} \|x_i - x_j\|^2 + c_\alpha \left[ (1-\alpha)^2 (L+\mu) \left( f_i - f_\star - \frac{\|g_i\|^2}{2L} \right) - (L-\mu) \left( f_j - f_\star + \frac{\|g_j\|^2}{2L} \right) \right],\]
with $c_\alpha = \dfrac{\alpha}{(1-\alpha)\,(2\mu - (L+\mu)\alpha)}$.
Julia usage
problem = PEP()
param = OrderedDict("mu" => 0.5, "L" => 1.0, "alpha" => 0.4)
f = declare_function!(problem, SmoothQuadraticLojasiewiczFunctionCheap, param)Fields
mu::Float64: quadratic Łojasiewicz parameter $\mu$.L::Float64: smoothness parameter $L$.alpha::Union{Float64,Nothing}: relaxation parameter $\alpha$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, stationary_point!, SmoothFunction, and SmoothQuadraticLojasiewiczFunctionExpensive.
PEPit.SmoothQuadraticLojasiewiczFunctionExpensive — Type
SmoothQuadraticLojasiewiczFunctionExpensive(param; reuse_gradient=true)Class of $L$-smooth (not necessarily convex) functions that also satisfy a quadratic Łojasiewicz inequality (sometimes also referred to as a Polyak-Łojasiewicz inequality) with parameter $\mu$. Extensive descriptions of such classes of functions can be found in [1, 2]. The conditions implemented here are presented in [3, Proposition 3.4]; compared with SmoothQuadraticLojasiewiczFunctionCheap, they are tighter but more expensive (two $2 \times 2$ PSD blocks per ordered pair of oracle points).
Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.
Smooth functions satisfying a Łojasiewicz property do not enjoy known interpolation conditions. The conditions implemented in this class are necessary but a priori not sufficient for interpolation. Hence, the numerical results obtained when using this class might be non-tight upper bounds.
Class parameters
param["mu"]: quadratic Łojasiewicz parameter $\mu$ (with $0 \leqslant \mu \leqslant L$).param["L"]: smoothness parameter $L$.
Necessary conditions
A stationary point $(x_\star, g_\star = 0, f_\star)$ is created automatically if none was requested through stationary_point!. Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$, the two-sided Łojasiewicz bounds are added first:
\[\frac{1}{2L} \|g_i\|^2 \leqslant f_i - f_\star \leqslant \frac{1}{2\mu} \|g_i\|^2 \qquad \text{for all } i \text{ with } x_i \neq x_\star.\]
Then, for every ordered pair $i \neq j$, defining the negated smoothness surplus and the Łojasiewicz surpluses
\[\begin{aligned} A & = -(f_i - f_j) + \frac{1}{2} \langle g_i + g_j, x_i - x_j \rangle + \frac{1}{4L} \|g_i - g_j\|^2 - \frac{L}{4} \|x_i - x_j\|^2, \\ B & = (L + \mu) \left( f_i - f_\star - \frac{1}{2L} \|g_i\|^2 \right), \qquad C = (L - \mu) \left( f_j - f_\star + \frac{1}{2L} \|g_j\|^2 \right), \end{aligned}\]
two slack Expressions $s_{12}, s_{22}$ are created and the two coupled PSD constraints of [3, Proposition 3.4] are imposed, with $D = B - C - (L + 3\mu) A$:
\[\begin{pmatrix} -(2L+\mu) A & s_{12} \\ s_{12} & s_{22} \end{pmatrix} \succeq 0, \quad \begin{pmatrix} -(2L+\mu) A - \frac{4\mu}{2L+\mu} s_{12} - D & s_{12} - \frac{\mu}{2L+\mu} s_{22} - \frac{L+\mu}{2} A + B \\ s_{12} - \frac{\mu}{2L+\mu} s_{22} - \frac{L+\mu}{2} A + B & s_{22} - B \end{pmatrix} \succeq 0.\]
Julia usage
problem = PEP()
param = OrderedDict("mu" => 0.1, "L" => 1.0)
f = declare_function!(problem, SmoothQuadraticLojasiewiczFunctionExpensive, param)Fields
mu::Float64: quadratic Łojasiewicz parameter $\mu$.L::Float64: smoothness parameter $L$._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, stationary_point!, SmoothFunction, and SmoothQuadraticLojasiewiczFunctionCheap.
PEPit.BlockSmoothConvexFunctionCheap — Type
BlockSmoothConvexFunctionCheap(param; reuse_gradient=true)Class of convex functions that are smooth by blocks (with one smoothness parameter $L_k$ per block of a BlockPartition), modeled through a cheap set of necessary interpolation constraints.
Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.
Functions that are smooth by blocks and convex generally do not enjoy known interpolation conditions. The conditions implemented in this class are necessary but a priori not sufficient for interpolation. Hence, the numerical results obtained when using this class might be non-tight upper bounds.
Class parameters
param["partition"]: theBlockPartitionof the variables.param["L"]: smoothness parameters (a vector with one entry per block, or a scalar for a single block).
Necessary conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ and denoting by $v^{(k)}$ the block-$k$ component of a point $v$ (see get_block), the following constraint is added for every pair $i \neq j$ and every block $k$ (see [1]):
\[f_i - f_j \geqslant \langle g_j, x_i - x_j \rangle + \frac{1}{2 L_k} \left\| g_i^{(k)} - g_j^{(k)} \right\|^2.\]
Julia usage
problem = PEP()
partition = declare_block_partition!(problem, 3)
param = OrderedDict("partition" => partition, "L" => [1.0, 4.0, 10.0])
f = declare_function!(problem, BlockSmoothConvexFunctionCheap, param)Smooth convex functions by blocks are necessarily differentiable, hence reuse_gradient is set to true.
Fields
partition::BlockPartition: partitioning of the variables.L::Vector{Float64}: smoothness parameters, one per block._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, declare_block_partition!, and BlockSmoothConvexFunctionExpensive.
PEPit.BlockSmoothConvexFunctionExpensive — Type
BlockSmoothConvexFunctionExpensive(param; reuse_gradient=true)Class of convex functions that are smooth by blocks (with one smoothness parameter $L_k$ per block of a BlockPartition), modeled through the strengthened necessary interpolation constraints of [2, Section 3.1]. Compared with BlockSmoothConvexFunctionCheap, the constraints are tighter but significantly more expensive (they involve one PSD block per triplet of oracle points and pair of blocks).
Overrides add_class_constraints! to add the conditions of the class when solve! builds the SDP.
Functions that are smooth by blocks and convex generally do not enjoy known interpolation conditions. The conditions implemented in this class are necessary but a priori not sufficient for interpolation. Hence, the numerical results obtained when using this class might be non-tight upper bounds.
Class parameters
param["partition"]: theBlockPartitionof the variables.param["L"]: smoothness parameters (a vector with one entry per block, or a scalar for a single block).
Necessary conditions
Associating with each oracle call $i$ the triplet $(x_i, g_i, f_i)$ and denoting by $v^{(m)}$ the block-$m$ component of a point $v$, the following holds for every triplet of oracle points $(i, j, k)$ and every pair of blocks $(m, l)$: defining the block-$m$ smooth-convex surpluses
\[\begin{aligned} A & = f_i - f_k - \langle g_k, x_i - x_k \rangle - \frac{1}{2 L_m} \|g_i^{(m)} - g_k^{(m)}\|^2, \\ B & = f_i - f_j - \langle g_j, x_i - x_j \rangle - \frac{1}{2 L_m} \|g_i^{(m)} - g_j^{(m)}\|^2, \\ C & = \frac{1}{2 L_m} \|g_j^{(m)} - g_k^{(m)}\|^2 - \frac{1}{2 L_l} \|g_j^{(l)} - g_k^{(l)}\|^2, \end{aligned}\]
there exists a scalar slack $\lambda \geqslant 0$ such that
\[\begin{pmatrix} A & \tfrac{1}{2}(A + B + C) - \lambda \\ \tfrac{1}{2}(A + B + C) - \lambda & B \end{pmatrix} \succeq 0.\]
The slack $\lambda$ is modeled by a fresh Expression and the $2 \times 2$ condition by a PSDMatrix; see [2, Section 3.1].
Julia usage
problem = PEP()
partition = declare_block_partition!(problem, 3)
param = OrderedDict("partition" => partition, "L" => [1.0, 4.0, 10.0])
f = declare_function!(problem, BlockSmoothConvexFunctionExpensive, param)Smooth convex functions by blocks are necessarily differentiable, hence reuse_gradient is set to true.
Fields
partition::BlockPartition: partitioning of the variables.L::Vector{Float64}: smoothness parameters, one per block._PEPit_func: internalPEPFunctionstoring oracle calls and constraints.
References
See also declare_function!, declare_block_partition!, and BlockSmoothConvexFunctionCheap.