Norm-Ball Uncertainty Sets

PortfolioOptimisers.NormBallUncertaintySet — Type
struct NormBallUncertaintySet{__T_kappa, __T_L, __T_p, __T_class, __T_val} <: AbstractUncertaintySetResult

Holds a radius, a geometry map and a norm order, so the set is the image of a norm ball under the map, on the mean axis or on the covariance axis.

The map may have fewer columns than the quantity has entries, so the set may be flat, which is what a set confined to an Orthogonal Subspace needs, and it may have no column at all, which is the rank-zero set whose worst case is the nominal quantity. Its worst case is the radius times the dual norm of the map's transpose applied to the exposure, so no consumer factorises anything: the mean builder raises one cone on $\mathbf{L}^{\intercal}\boldsymbol{w}$, and the covariance builder puts $\mathbf{L}^{\intercal}$ where the ellipsoid's Cholesky factor goes. The cone follows the dual norm: a second-order cone at $p = 2$, a norm-one cone at $p = \infty$, a norm-infinity cone at $p = 1$, and power cones otherwise.

class names the axis, and the axis fixes the row count of L and the index a view applies. A MuUncertaintySetClass set carries an $N \times r$ map and takes the plain asset index. A SigmaUncertaintySetClass set carries an $N^{2} \times r$ one, because it bounds a vectorised covariance, so port_opt_view recovers $N$ from the map and maps the asset index through fourth_moment_index_generator before it slices. The robust-return builder refuses a set that carries the covariance tag.

Three existing shapes are diagonal or square cases of this one. The mean BoxUncertaintySet is the $p = \infty$ set with $\mathbf{L} = \operatorname{diag}((\boldsymbol{u} - \boldsymbol{\ell})/2)$ and $\kappa = 1$. The L1UncertaintySet is the $p = 1$ set with $\mathbf{L} = \operatorname{diag}(\boldsymbol{\sigma})$ and $\kappa = \epsilon$. The EllipsoidalUncertaintySet is the $p = 2$ set with $\mathbf{L}$ the lower Cholesky factor of its shape matrix and $\kappa = k$, which is what the converter constructor builds. Each of the three reaches the same weights as the norm ball it corresponds to, and each keeps its own builder.

Mathematical definition

\[\begin{align} U^{p}_{\boldsymbol{z}} &= \left\{ \hat{\boldsymbol{z}} + \mathbf{L}\boldsymbol{u} \, \vert \, \lVert \boldsymbol{u} \rVert_{p} \leq \kappa \right\}\,, \\ \underset{\boldsymbol{z} \in U^{p}_{\boldsymbol{z}}}{\min} \boldsymbol{z}^{\intercal}\boldsymbol{e} &= \hat{\boldsymbol{z}}^{\intercal}\boldsymbol{e} - \kappa \lVert \mathbf{L}^{\intercal}\boldsymbol{e} \rVert_{q}\,, \quad \frac{1}{p} + \frac{1}{q} = 1\,. \end{align}\]

Where:

  • $U^{p}_{\boldsymbol{z}}$: Norm-ball uncertainty set of order $p$ for the quantity $\boldsymbol{z}$.
  • $\boldsymbol{z}$: Uncertain quantity, the mean vector on the mean axis and the vectorised covariance on the covariance axis.
  • $\hat{\boldsymbol{z}}$: Estimated centre of the set.
  • $\mathbf{L}$: Geometry map, $N \times r$ on the mean axis and $N^{2} \times r$ on the covariance axis.
  • $\boldsymbol{u}$: Coordinates in the ball, $r \times 1$.
  • $\kappa \geq 0$: Radius of the ball.
  • $p \geq 1$: Norm order of the ball, $\infty$ admitted.
  • $q$: Dual norm order, $\infty$ at $p = 1$ and $1$ at $p = \infty$.
  • $\boldsymbol{e}$: Exposure the worst case is taken against, the weights on the mean axis and the vectorised lifted weight matrix on the covariance axis.

The second line is Hölder's inequality with equality, which is why the worst case needs no factorisation and holds for a rank-deficient $\mathbf{L}$. A radius of zero, or a map with no column, leaves the nominal quantity. On the covariance axis the worst case is taken jointly with the positive semi-definite constraint, and the consumer states the lifted form it builds.

Fields

  • kappa: Radius $\kappa \geq 0$ of the ball, the multiplier of the dual-norm penalty. 0 leaves the nominal quantity.
  • L: Geometry map $\mathbf{L}$, $N \times r$ on the mean axis and $N^{2} \times r$ on the covariance axis. It may be rank deficient, and r = 0 is admitted and leaves the nominal quantity.
  • p: Norm order $p \geq 1$ of the ball, Inf admitted. The consumer raises the cone of the dual order.
  • class: Axis tag of the set, which sets the row count of the shape matrix or of the geometry map.
  • val: Quantity that the set is a neighbourhood of. It is a vector on the mean axis and a covariance matrix on the covariance axis. nothing lets the consumer use its own quantity. A value has priority over the field of the returns estimator and over the prior.

Constructors

NormBallUncertaintySet(;    kappa::Number,    L::MatNum,    p::Number = 2,    class::AbstractUncertaintySetClass,    val::Option{<:ArrNum} = nothing) -> NormBallUncertaintySetNormBallUncertaintySet(ucs::EllipsoidalUncertaintySet,                       mtx_sqrt::Option{<:AbstractMatrixSquareRootAlgorithm} = EigenFallbackSquareRoot())    -> NormBallUncertaintySet

Keywords correspond to the struct's fields. The second constructor converts a built EllipsoidalUncertaintySet with one square root at construction time: L = matrix_square_root(mtx_sqrt, ucs.sigma), p = 2, and kappa, class and val carried through from k, class and val. It is the route through which every estimator that emits an ellipsoid reaches this type. The default mtx_sqrt = EigenFallbackSquareRoot() takes the Cholesky factor where it exists, and the square root of the eigendecomposition of a singular positive semidefinite matrix otherwise. mtx_sqrt = nothing takes the plain Cholesky factor, which raises a LinearAlgebra.PosDefException on a matrix that is not positive definite. matrix_square_root states each algorithm. At p = 2 the set reads L only through $\mathbf{L}\mathbf{L}^{\intercal}$, so the eigen square root of a singular shape gives the same set as the ellipsoid.

Validation

  • !(kappa isa Bool), else an ArgumentError.
  • isfinite(kappa) and kappa >= 0.
  • !isnan(p) and p >= 1. Inf is admitted.
  • size(L, 1) > 0 and all(isfinite, L). A map with no column is admitted.
  • If class is a SigmaUncertaintySetClass: size(L, 1) is a perfect square, because the map lives on the vectorised covariance.
  • If val is provided: length(val) == size(L, 1). The rule reads a length rather than a size, so it holds on both axes: val is a characteristic vector of length $N$ beside a map of $N$ rows, and an $N \times N$ covariance matrix beside a map of $N^{2}$ rows. On the covariance axis val must also be square.

Examples

julia> NormBallUncertaintySet(; kappa = 2.0, L = [1.0 0.0; 0.0 1.0; 0.5 0.5],                              class = MuUncertaintySetClass())NormBallUncertaintySet  kappa ┼ Float64: 2.0      L ┼ 3×2 Matrix{Float64}      p ┼ Int64: 2  class ┼ MuUncertaintySetClass()    val ┴ nothing

Related

References

  • [173] A. Ben-Tal and A. Nemirovski. Robust Convex Optimization. Mathematics of Operations Research 23, 769–805 (1998). Section 3, Equation 14.
  • [170] D. Goldfarb and G. Iyengar. Robust Portfolio Selection Problems. Mathematics of Operations Research 28, 1–38 (2003). Section 5.
source
PortfolioOptimisers.k_norm_ball — Function
k_norm_ball(km::NormalKUncertaintyAlgorithm, q::Number, X::MatNum, L::MatNum, ::Integer)
k_norm_ball(::GeneralKUncertaintyAlgorithm, q::Number, args...)
k_norm_ball(km::ChiSqKUncertaintyAlgorithm, q::Number, ::Any, L::MatNum, df::Integer)
k_norm_ball(type::Number, args...)

Radius $\kappa$ of a NormBallUncertaintySet, read against a geometry map rather than against a shape matrix.

It is the norm-ball twin of k_ucs, and the two differ on the two algorithms that read the geometry. NormalKUncertaintyAlgorithm solves in the factor rather than inverting a shape, so it serves a rank-deficient map, where a shape matrix would have to be repaired first. ChiSqKUncertaintyAlgorithm takes its degrees of freedom from df, the dimension of the ball, and not from the row count of the map, because a flat set is a confidence region of its own subspace and not of the ambient space. Under ambient = true it reads the row count size(L, 1) instead. GeneralKUncertaintyAlgorithm and a plain number read neither, and absorb the trailing arguments.

Mathematical definition

\[\begin{align} \kappa_{\mathrm{normal}} &= \sqrt{Q_{1-q}\left(\left\lVert \mathbf{L}^{+}\mathbf{x}_{i} \right\rVert_{2}^{2}\right)}\,, \\ \kappa_{\chi^{2}} &= \sqrt{\chi^{2,-1}_{\mathrm{df}}(1 - q)}\,, \\ \kappa_{\mathrm{general}} &= \sqrt{\dfrac{1 - q}{q}}\,. \end{align}\]

Where:

  • $\kappa$: Radius of the ball.
  • $\mathbf{L}^{+}$: Moore-Penrose pseudo-inverse of the geometry map. norm_ball_coordinates applies it, and on a singular square map it drops each direction whose squared singular value is at most $m \epsilon$ times the largest, where $m$ is the row count of the map and $\epsilon$ is the machine epsilon.
  • $\mathbf{x}_{i}$: One sampled estimation error, the $i$-th row of $\mathbf{X}$.
  • $Q_{1-q}$: Empirical quantile at $1 - q$.
  • $\mathrm{df}$: Degrees of freedom, the dimension of the ball.
  • $q$: Significance level.

$\left\lVert \mathbf{L}^{+}\mathbf{x} \right\rVert_{2}^{2} = \mathbf{x}^{\intercal}\left(\mathbf{L}\mathbf{L}^{\intercal}\right)^{+}\mathbf{x}$, so on a full-rank square map the first line is the Mahalanobis distance k_ucs measures against $\mathbf{L}\mathbf{L}^{\intercal}$, and the two radii agree.

Algorithm

  1. On NormalKUncertaintyAlgorithm, take the ball coordinates of each sampled error with norm_ball_coordinates, one column per error.
  2. Take the squared column norms, giving one squared distance per sample, and return the square root of their 1 - q quantile.
  3. On ChiSqKUncertaintyAlgorithm, return the square root of the 1 - q chi-squared quantile at df degrees of freedom, or at size(L, 1) when km.ambient is true.
  4. On GeneralKUncertaintyAlgorithm, return sqrt((1 - q) / q), Cantelli's bound, which reads no geometry.
  5. On a Number, return it unchanged.

Arguments

  • km, type: Radius algorithm, or the radius itself as a Number.
  • q: Significance level.
  • X: Sample of estimation errors, one row per simulation.
  • L: Geometry map.
  • df: Degrees of freedom, the dimension of the ball. Its caller reads ucs_dimension for a map factorised from a shape, $N(N+1)/2$ on a full covariance shape, and LinearAlgebra.rank(L) for a deviation map.

Returns

  • kappa::Number: Radius of the ball.

Related

References

  • [170] D. Goldfarb and G. Iyengar. Robust Portfolio Selection Problems. Mathematics of Operations Research 28, 1–38 (2003). Section 5.
source
k_norm_ball(::NormalKUncertaintyAlgorithm, ::Number, ::Nothing, ::MatNum, ::Integer)

Refuses the sampled radius on the Orthogonal Subspace, which simulates no estimation errors for that radius to read.

NormalKUncertaintyAlgorithm takes a quantile of a sample of Mahalanobis distances, and OrthogonalUncertaintySet draws no sample, because it derives its geometry from the fitted loadings alone. Without this method the absent sample raises a MethodError, which names no remedy.

Arguments

  • The radius algorithm, the significance level, the absent sample, the scaling and the degrees of freedom, all ignored.

Validation

Returns

  • Never returns.

Related

source
PortfolioOptimisers.port_opt_view — Method
port_opt_view(
    risk_ucs::NormBallUncertaintySet{<:Any, <:AbstractMatrix{<:Union{Number, AbstractJuMPScalar}}, <:Any, <:MuUncertaintySetClass},
    i,
    args...
) -> Union{NormBallUncertaintySet{var"#s185", var"#s1851", var"#s1852", C, Nothing} where {var"#s185"<:Number, var"#s166"<:Union{Number, AbstractJuMPScalar}, var"#s1851"<:AbstractMatrix{var"#s166"}, var"#s1852"<:Number, C<:AbstractUncertaintySetClass}, NormBallUncertaintySet{var"#s185", var"#s1851", var"#s1852", C, <:AbstractArray{var"#s166", N}} where {var"#s185"<:Number, var"#s166"<:Union{Number, AbstractJuMPScalar}, var"#s1851"<:AbstractMatrix{var"#s166"}, var"#s1852"<:Number, C<:AbstractUncertaintySetClass, var"#s166"<:Union{Number, AbstractJuMPScalar}, N}}

Return a view of a mean NormBallUncertaintySet restricted to assets at index i.

The view is the projection of the set onto the cluster's coordinates, and not a refit: a row slice of the map is the map of the projected set, because the coordinates $\boldsymbol{u}$ of the ball are untouched by dropping rows of $\mathbf{L}$. It is what the ellipsoid's view returns too, since $\mathbf{\Sigma}_{ii} = \mathbf{L}_{i}\mathbf{L}_{i}^{\intercal}$. A caller who wants the set the same estimator would fit on the subset alone fits the subset.

Algorithm

  1. Take view(risk_ucs.L, i, :), the rows of the map the selected assets occupy.
  2. Take nothing_scalar_array_view(risk_ucs.val, i), the fitted characteristic vector restricted to the same assets, which passes a nothing through unchanged.
  3. Rebuild the set from the two views with rebuild_struct. kappa, p and class do not change.

Arguments

  • risk_ucs: Mean norm-ball uncertainty set.
  • i: Indices of the assets that the view keeps.
  • args...: Additional positional arguments (ignored).

Returns

  • risk_ucs::NormBallUncertaintySet: The set restricted to i.

Related

source
PortfolioOptimisers.port_opt_view — Method
port_opt_view(
    risk_ucs::NormBallUncertaintySet{<:Any, <:AbstractMatrix{<:Union{Number, AbstractJuMPScalar}}, <:Any, <:SigmaUncertaintySetClass},
    i,
    args...
) -> Union{NormBallUncertaintySet{var"#s185", var"#s1851", var"#s1852", C, Nothing} where {var"#s185"<:Number, var"#s166"<:Union{Number, AbstractJuMPScalar}, var"#s1851"<:AbstractMatrix{var"#s166"}, var"#s1852"<:Number, C<:AbstractUncertaintySetClass}, NormBallUncertaintySet{var"#s185", var"#s1851", var"#s1852", C, <:AbstractArray{var"#s166", N}} where {var"#s185"<:Number, var"#s166"<:Union{Number, AbstractJuMPScalar}, var"#s1851"<:AbstractMatrix{var"#s166"}, var"#s1852"<:Number, C<:AbstractUncertaintySetClass, var"#s166"<:Union{Number, AbstractJuMPScalar}, N}}

Return a view of a covariance NormBallUncertaintySet restricted to assets at index i, mapping the map's row index through the fourth-moment index generator.

The view is the projection of the set onto the cluster's coordinates, and not a refit. The set bounds a vectorised covariance, so its map lives on the $N^{2}$ axis while its centre lives on the $N$ axis, and the method applies two different indices, one to each field.

Algorithm

  1. Take nothing_scalar_array_view(risk_ucs.val, i), the fitted $N \times N$ covariance restricted to the selected assets. It takes the plain asset index, and a nothing passes through unchanged. The step runs first, because step 2 overwrites i.
  2. Recover N as isqrt(size(risk_ucs.L, 1)) from the map, and expand i with fourth_moment_index_generator(N, i), giving the positions the selected assets occupy in the vectorised covariance.
  3. Take view(risk_ucs.L, i, :) under the expanded index, giving the rows of the map the selected pairs occupy.
  4. Rebuild the set from the two views with rebuild_struct. kappa, p and class do not change.

Arguments

  • risk_ucs: Covariance norm-ball uncertainty set.
  • i: Indices of the assets that the view keeps.
  • args...: Additional positional arguments (ignored).

Returns

  • risk_ucs::NormBallUncertaintySet: The set restricted to i.

Related

source

References

[170]
D. Goldfarb and G. Iyengar. Robust Portfolio Selection Problems. Mathematics of Operations Research 28, 1–38 (2003).
[173]
A. Ben-Tal and A. Nemirovski. Robust Convex Optimization. Mathematics of Operations Research 23, 769–805 (1998).