Norm-Ball Uncertainty Sets
PortfolioOptimisers.NormBallUncertaintySet — Type
struct NormBallUncertaintySet{__T_kappa, __T_L, __T_p, __T_class, __T_val} <: AbstractUncertaintySetResultHolds 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.0leaves 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, andr = 0is admitted and leaves the nominal quantity.
p: Norm order $p \geq 1$ of the ball,Infadmitted. 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.nothinglets 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()) -> NormBallUncertaintySetKeywords 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 anArgumentError.isfinite(kappa)andkappa >= 0.!isnan(p)andp >= 1.Infis admitted.size(L, 1) > 0andall(isfinite, L). A map with no column is admitted.- If
classis aSigmaUncertaintySetClass:size(L, 1)is a perfect square, because the map lives on the vectorised covariance. - If
valis provided:length(val) == size(L, 1). The rule reads a length rather than a size, so it holds on both axes:valis 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 axisvalmust 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 ┴ nothingRelated
AbstractUncertaintySetResultAbstractUncertaintySetClassEllipsoidalUncertaintySetBoxUncertaintySetL1UncertaintySetCompactCovarianceUncertaintySetdual_norm_orderset_ucs_return_constraints!set_ucs_variance_risk!ucs_varianceport_opt_view
References
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_coordinatesapplies 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
- On
NormalKUncertaintyAlgorithm, take the ball coordinates of each sampled error withnorm_ball_coordinates, one column per error. - Take the squared column norms, giving one squared distance per sample, and return the square root of their
1 - qquantile. - On
ChiSqKUncertaintyAlgorithm, return the square root of the1 - qchi-squared quantile atdfdegrees of freedom, or atsize(L, 1)whenkm.ambientistrue. - On
GeneralKUncertaintyAlgorithm, returnsqrt((1 - q) / q), Cantelli's bound, which reads no geometry. - On a
Number, return it unchanged.
Arguments
km,type: Radius algorithm, or the radius itself as aNumber.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 readsucs_dimensionfor a map factorised from a shape, $N(N+1)/2$ on a full covariance shape, andLinearAlgebra.rank(L)for a deviation map.
Returns
kappa::Number: Radius of the ball.
Related
NormBallUncertaintySetNormBallUncertaintySetAlgorithmk_ucsucs_dimensionnorm_ball_setnorm_ball_deviation_set
References
- [170] D. Goldfarb and G. Iyengar. Robust Portfolio Selection Problems. Mathematics of Operations Research 28, 1–38 (2003). Section 5.
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
- The method always throws an
ArgumentError. The message names the two algorithms that read no sample,ChiSqKUncertaintyAlgorithmandGeneralKUncertaintyAlgorithm, and a number, which states the radius itself.
Returns
- Never returns.
Related
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
- Take
view(risk_ucs.L, i, :), the rows of the map the selected assets occupy. - Take
nothing_scalar_array_view(risk_ucs.val, i), the fitted characteristic vector restricted to the same assets, which passes anothingthrough unchanged. - Rebuild the set from the two views with
rebuild_struct.kappa,pandclassdo 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 toi.
Related
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
- 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 anothingpasses through unchanged. The step runs first, because step 2 overwritesi. - Recover
Nasisqrt(size(risk_ucs.L, 1))from the map, and expandiwithfourth_moment_index_generator(N, i), giving the positions the selected assets occupy in the vectorised covariance. - Take
view(risk_ucs.L, i, :)under the expanded index, giving the rows of the map the selected pairs occupy. - Rebuild the set from the two views with
rebuild_struct.kappa,pandclassdo 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 toi.
Related
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).