OWA risk measures (b)
PortfolioOptimisers.SortingNetworkOrderedWeightsArray — Type
struct SortingNetworkOrderedWeightsArray{__T_merge, __T_ordering} <: OrderedWeightsArrayFormulationOWA formulation that computes the exact OWA risk through a relaxed sorting network of $O(T \log^{2} T)$ linear rows.
The formulation runs the net portfolio returns through a sorting network, and relaxes each comparator to three linear rows. Goemans [212] shows that the relaxation of any sorting network is an extended formulation of the permutahedron. The formulation fixes the network inputs to the returns and leaves the outputs free. A relaxed comparator can only spread its two values apart, and a nondecreasing weight vector pays for each spread, so the minimum of the weighted network outputs is the OWA risk. So the risk is exact, as the risk of ExactOrderedWeightsArray is, but the model has $O(T \log^{2} T)$ rows in place of $T^{2}$. It is the exact formulation for a long sample.
The formulation needs a nondecreasing weight vector, which is also the condition for the risk measure to be convex. On any other vector the relaxation is not exact: the model has no minimum, or its minimum falls below the OWA risk. So the constructor of the risk measure refuses such a vector.
One interior-point iteration costs one factorisation of the KKT matrix, and the fill of that factorisation sets the time of the solve, not the row count. QDLDL, the default linear solver of Clarabel, factorises the matrix one column at a time. A supernodal factorisation of the same matrix cuts the time of the solve: MKL Pardiso by 83 to 85 % at $T = 500$ and by 90 % at $T = 1000$, and Tulip by 76 to 79 % and by 87 %. The iterations and the risk do not change.
Two setups give a supernodal factorisation. The times below are for the minimum risk of the Gini mean difference weights, owa_gmd, on eight assets, with the default network, one thread and tolerances of 1e-9.
- Clarabel with the setting
direct_solve_method = :mklfactorises with MKL Pardiso. It needsusing Pardiso, and it runs on x86-64 only. It solved $T = 500$ in 4.5 to 4.7 s against 26.5 to 30.5 s with QDLDL, and $T = 1000$ in 28.4 s against 298.5 s. - Tulip with
KKT_System = Tulip.KKT.K1()andKKT_Backend = Tulip.KKT.TlpCholmod.Backend()factorises the normal equations with the supernodal Cholesky factorisation of CHOLMOD. It needs no binary past CHOLMOD. It solved $T = 500$ in 6.3 s and $T = 1000$ in 39.9 s.
Mathematical definition
\[\begin{align} \mathrm{OWA}(\boldsymbol{w}) &= \begin{cases} \underset{\boldsymbol{z}}{\min} & s\, \boldsymbol{\omega}^{\intercal} \boldsymbol{z}_{\mathrm{out}}\\ \text{s.t.} & z_{l(k)} + z_{h(k)} = z_{a(k)} + z_{b(k)} \quad \forall k = 1,\, \ldots,\, K\\ & z_{h(k)} \geq z_{a(k)},\; z_{h(k)} \geq z_{b(k)} \quad \forall k = 1,\, \ldots,\, K\\ & \boldsymbol{z}_{\mathrm{in}} = \hat{\boldsymbol{r}} / s\,. \end{cases} \end{align}\]
Where:
- $\boldsymbol{\omega}$: Nondecreasing OWA weight vector $T \times 1$.
- $\hat{\boldsymbol{r}}$: The net portfolio returns, $T \times 1$, with entries $\hat{r}_t$.
- $s$: Largest absolute asset return, which scales the network values towards one.
- $K$: Number of comparators of the network.
- $a(k),\, b(k)$: The two values that comparator $k$ reads.
- $l(k),\, h(k)$: The smaller and the larger value that comparator $k$ writes.
- $\boldsymbol{z}_{\mathrm{in}},\, \boldsymbol{z}_{\mathrm{out}}$: The values that the network reads, and the last value that it writes to each position, in ascending order of position.
Fields
merge: Sorting network that the formulation relaxes. Every sorting network gives the exact risk. The network sets the number of rows and the cost of one solver iteration.
ordering: Order of the network variables in the model. It does not change the risk.
Constructors
SortingNetworkOrderedWeightsArray(; merge::AbstractSortingNetworkMerge = BitonicMerge(), ordering::AbstractSortingNetworkOrdering = ComparatorOrdering()) -> SortingNetworkOrderedWeightsArrayKeywords correspond to the struct's fields.
Examples
julia> SortingNetworkOrderedWeightsArray()SortingNetworkOrderedWeightsArray merge ┼ BitonicMerge() ordering ┴ ComparatorOrdering()Related
OrderedWeightsArrayFormulationExactOrderedWeightsArrayApproxOrderedWeightsArrayAbstractSortingNetworkMergeAbstractSortingNetworkOrderingOrderedWeightsArrayOrderedWeightsArrayRange
References
PortfolioOptimisers.AbstractSortingNetworkMerge — Type
abstract type AbstractSortingNetworkMerge <: AbstractAlgorithmAbstract supertype for the sorting networks that SortingNetworkOrderedWeightsArray relaxes.
A sorting network is a fixed list of comparators. Each comparator reads two positions and writes the smaller value to the first position and the larger value to the second. Goemans [212] shows that the relaxation of any sorting network is an extended formulation of the permutahedron, so every subtype gives the exact OWA risk. The network sets the number of rows of the model and the cost of one solver iteration.
Interfaces
To implement a new sorting network, subtype AbstractSortingNetworkMerge and implement the following method:
sorting_network
sorting_network(alg::MySortingNetworkMerge, T::Integer) -> Vector{Tuple{Int, Int}}: Comparator list that sortsTvalues in ascending order.
Arguments
alg: The concrete subtype instance.T: Number of values to sort.
Returns
c::Vector{Tuple{Int, Int}}: Comparators in the order of execution. A pair(i, j)puts the smaller value at positioniand the larger value at positionj. After the last comparator, the values are in ascending order for every input.
Examples
julia> struct MySortingNetworkMerge <: PortfolioOptimisers.AbstractSortingNetworkMerge endjulia> function PortfolioOptimisers.sorting_network(::MySortingNetworkMerge, T::Integer) return [(i, j) for j in 2:T for i in 1:(j - 1)] endjulia> PortfolioOptimisers.sorting_network(MySortingNetworkMerge(), 3)3-element Vector{Tuple{Int64, Int64}}: (1, 2) (1, 3) (2, 3)Related
References
PortfolioOptimisers.OddEvenMerge — Type
struct OddEvenMerge <: AbstractSortingNetworkMergeSorts with Batcher's odd-even merge network, which has the fewest comparators of the two merge networks.
Batcher [213] states the network for a power of two. The network here omits each comparator that reads a position past T, so it sorts every T. It has $O(T \log^{2} T)$ comparators: 3756 at T = 250 and 9511 at T = 500.
Examples
julia> OddEvenMerge()OddEvenMerge()Related
References
- [213] K. E. Batcher. Sorting networks and their applications. In: Proceedings of the AFIPS Spring Joint Computer Conference, 307–314 (1968).
PortfolioOptimisers.BitonicMerge — Type
struct BitonicMerge <: AbstractSortingNetworkMergeSorts with Batcher's bitonic merge network, which QDLDL, the default linear solver of Clarabel, factorises with less work under its AMD order. Under a supernodal factorisation the two networks cost about the same.
Batcher [213] states the network for a power of two. The network here splits a sequence of any length T into a descending half and an ascending half, and merges the two halves with the largest power of two below the length as the comparator span. It has $O(T \log^{2} T)$ comparators: 4405 at T = 250 and 11026 at T = 500, which is more than OddEvenMerge.
Examples
julia> BitonicMerge()BitonicMerge()Related
References
- [213] K. E. Batcher. Sorting networks and their applications. In: Proceedings of the AFIPS Spring Joint Computer Conference, 307–314 (1968).
PortfolioOptimisers.sorting_network — Function
sorting_network(
_::OddEvenMerge,
T::Integer
) -> Vector{Tuple{Int64, Int64}}
Return the comparators of Batcher's odd-even merge network for T values.
Algorithm
- Start with the empty comparator list
cand the block half-sizep = 1. - While
p < T, run the passes of the merge of the blocks of2ppositions. For each distancekfrompdown to1, halved at each pass, append the comparators of the pass withodd_even_merge_pass!. - Double
p, and repeat step 2. - Return
c.
Arguments
alg: The odd-even merge network.T: Number of values to sort.
Returns
c::Vector{Tuple{Int, Int}}: Comparators in the order of execution. A pair(i, j)puts the smaller value at positioniand the larger value at positionj.
Examples
julia> PortfolioOptimisers.sorting_network(OddEvenMerge(), 4)5-element Vector{Tuple{Int64, Int64}}: (1, 2) (3, 4) (1, 3) (2, 4) (2, 3)Related
References
- [213] K. E. Batcher. Sorting networks and their applications. In: Proceedings of the AFIPS Spring Joint Computer Conference, 307–314 (1968).
sorting_network(
_::BitonicMerge,
T::Integer
) -> Vector{Tuple{Int64, Int64}}
Return the comparators of Batcher's bitonic merge network for T values.
Arguments
alg: The bitonic merge network.T: Number of values to sort.
Returns
c::Vector{Tuple{Int, Int}}: Comparators in the order of execution. A pair(i, j)puts the smaller value at positioniand the larger value at positionj.
Examples
julia> PortfolioOptimisers.sorting_network(BitonicMerge(), 3)3-element Vector{Tuple{Int64, Int64}}: (2, 3) (1, 3) (1, 2)Related
References
- [213] K. E. Batcher. Sorting networks and their applications. In: Proceedings of the AFIPS Spring Joint Computer Conference, 307–314 (1968).
PortfolioOptimisers.AbstractSortingNetworkOrdering — Type
abstract type AbstractSortingNetworkOrdering <: AbstractAlgorithmAbstract supertype for the orders of the network variables of SortingNetworkOrderedWeightsArray.
The order changes the columns of the model, not the risk. A solver that permutes the system before it factorises it gives the same cost for every order.
Interfaces
To implement a new order of the network variables, subtype AbstractSortingNetworkOrdering and implement the following method:
sorting_network_columns
sorting_network_columns(alg::MySortingNetworkOrdering, c::AbstractVector{Tuple{Int, Int}}) -> Vector{Int}: Column of each network value.
Arguments
alg: The concrete subtype instance.c: Comparators of the network, fromsorting_network.
Returns
cols::Vector{Int}: A permutation of1:(2 * length(c)). Comparatorkwrites the values2k - 1, the smaller one, and2k, the larger one. Valuemis the network variablecols[m].
Examples
julia> struct MySortingNetworkOrdering <: PortfolioOptimisers.AbstractSortingNetworkOrdering endjulia> function PortfolioOptimisers.sorting_network_columns(::MySortingNetworkOrdering, c::AbstractVector{Tuple{Int, Int}}) return collect((2 * length(c)):-1:1) endjulia> PortfolioOptimisers.sorting_network_columns(MySortingNetworkOrdering(), [(1, 2)])2-element Vector{Int64}: 2 1Related
PortfolioOptimisers.ComparatorOrdering — Type
struct ComparatorOrdering <: AbstractSortingNetworkOrderingPuts the network variables in the order of the comparators that write them.
The two values of each comparator are adjacent, and the comparators follow the order of execution.
Examples
julia> ComparatorOrdering()ComparatorOrdering()Related
PortfolioOptimisers.WireOrdering — Type
struct WireOrdering <: AbstractSortingNetworkOrderingPuts the network variables in the order of the positions they hold, one position after the other.
The values that one position holds are adjacent, in the order that the network writes them.
Examples
julia> WireOrdering()WireOrdering()Related
PortfolioOptimisers.sorting_network_columns — Function
sorting_network_columns(
_::ComparatorOrdering,
c::AbstractVector{Tuple{Int64, Int64}}
) -> Any
Return the columns of the network values in the order of the comparators that write them.
Arguments
alg: The comparator order.c: Comparators of the network.
Returns
cols::Vector{Int}:1:(2 * length(c)), as a vector.
Examples
julia> PortfolioOptimisers.sorting_network_columns(ComparatorOrdering(), [(1, 2), (2, 3)])4-element Vector{Int64}: 1 2 3 4Related
sorting_network_columns(
_::WireOrdering,
c::AbstractVector{Tuple{Int64, Int64}}
) -> Any
Return the columns of the network values in the order of the positions they hold.
A stable sort of the values by their position keeps the values of one position in the order that the network writes them.
Algorithm
- Build
wire, the position of each network value. Comparatorkwrites value2k - 1to its first position and value2kto its second position. - Sort the values by
wirewith a stable sort, which gives the permutationsortperm(wire). - Return its inverse, the column of each value.
Arguments
alg: The position order.c: Comparators of the network.
Returns
cols::Vector{Int}: A permutation of1:(2 * length(c)).
Examples
julia> PortfolioOptimisers.sorting_network_columns(WireOrdering(), [(1, 2), (2, 3)])4-element Vector{Int64}: 1 2 3 4julia> PortfolioOptimisers.sorting_network_columns(WireOrdering(), [(2, 3), (1, 2)])4-element Vector{Int64}: 2 4 1 3Related
PortfolioOptimisers.OrderedWeightsArrayRange — Type
struct OrderedWeightsArrayRange{__T_settings, __T_w1, __T_w2, __T_alg} <: RangeRiskMeasureMeasures risk as the sum of a loss tail and a gain tail of the sorted portfolio returns, each an OWA risk.
The risk is the sorted returns weighted by the difference of two OWA weight vectors, w1 for the loss tail and w2 for the gain tail.
w2 is held reversed. The reversal makes the difference of the two weight vectors a range. w1 weighs the lower tail of the sorted returns and the reversed w2 weighs the upper tail, so w1 - w2 adds the two tails and does not cancel them. It is the weight-space form of the convention ValueatRiskRange states on the returns themselves.
When w2 is nothing, the constructor mirrors w1: it stores reverse(w1) for a vector and reverse ∘ w1 for a callable. A w2 that the caller gives is stored as given. The stored w2 is never nothing, so a rebuild from the fields of an instance reverses nothing a second time.
Under ApproxOrderedWeightsArray this type approximates each tail on its own, and the relaxation is tighter than one OrderedWeightsArray over a fused vector such as owa_cvarrg. So a range of OWA tails is spelled with this type, and the aliases OWA_RG, OWA_CVaR_RG and OWA_TG_RG build it.
A w2 that you give is stored as given, so you must give it already reversed: reverse(v) for a vector v, and reverse ∘ f for a callable f. The constructor does not check the orientation. An unreversed w2 weighs the same lower tail as w1, so w1 - w2 cancels the two tails instead of adding them, and the measure is not a range. ApproxOrderedWeightsArray builds each tail from properties of its weight vector that a reordering leaves unchanged, so its model still optimises the range. The functor and expected_risk read w1 - w2, so the risk that they report then differs from the model.
Mathematical definition
\[\begin{align} \mathrm{OWARange}_{\boldsymbol{w}_{1},\boldsymbol{w}_{2}}(\boldsymbol{x}) &= \sum_{t=1}^{T} \left(w_{1,t} - w_{2,t}\right) x_{(t)}\,. \end{align}\]
Where:
- $\mathrm{OWARange}_{\boldsymbol{w}_{1},\boldsymbol{w}_{2}}(\boldsymbol{x})$: Ordered weights array range.
- $\boldsymbol{x}$: Portfolio returns vector $T \times 1$.
- $T$: Number of observations.
- $\boldsymbol{w}_{1}$: Lower-tail OWA weight vector $T \times 1$.
- $\boldsymbol{w}_{2}$: Upper-tail OWA weight vector $T \times 1$, held reversed.
- $x_{(t)}$: $t$-th smallest entry of $\boldsymbol{x}$, so $x_{(1)} \leq \dots \leq x_{(T)}$.
Fields
settings: Risk measure settings.
w1: Optional first OWA weight vector.
w2: Second OWA weight vector, held reversed. The constructor stores the reversal ofw1when it receivesnothing, and stores a givenw2as given.
alg: Risk measure optimisation formulation algorithm.
Constructors
OrderedWeightsArrayRange(; settings::RiskMeasureSettings = RiskMeasureSettings(), w1::OWA_Func_VecNum = owa_tg, w2::Option{<:OWA_Func_VecNum} = nothing, alg::OrderedWeightsArrayFormulation = ApproxOrderedWeightsArray()) -> OrderedWeightsArrayRangeKeywords correspond to the struct's fields. w2 = nothing stores the reversal of w1.
Validation
- If
w1is aVecNum:!isempty(w1). Raises anIsEmptyError. - If
w2is aVecNum:!isempty(w2). Raises anIsEmptyError. - If both
w1andw2areVecNum:length(w1) == length(w2). Raises aDimensionMismatch. - If both
w1andw2areVecNumandalgis aSortingNetworkOrderedWeightsArray:issorted(w1 - w2), withw2as stored. Raises aDomainError. A callable is checked when the model is built.
Functor
(r::OrderedWeightsArrayRange)(x::VecNum)Computes the OWA range of a portfolio returns vector x, as the sorted returns weighted by w1 - w2. A w1 or w2 that is a callable is evaluated at length(x) first, so the weight vectors always match the sample.
Arguments
x::VecNum: Portfolio returns vector.
Examples
julia> OrderedWeightsArrayRange()OrderedWeightsArrayRange settings ┼ RiskMeasureSettings │ scale ┼ Float64: 1.0 │ ub ┼ nothing │ rke ┴ Bool: true w1 ┼ typeof(owa_tg): PortfolioOptimisers.owa_tg w2 ┼ ComposedFunction{typeof(reverse), typeof(owa_tg)}: reverse ∘ PortfolioOptimisers.owa_tg alg ┼ ApproxOrderedWeightsArray │ p ┴ Vector{Float64}: [2.0, 3.0, 4.0, 10.0, 50.0]The worst realisation, mirrored into the gain tail, gives the range of the returns.
julia> x = [0.02, -0.01, 0.03, -0.04];julia> OrderedWeightsArrayRange(; w1 = owa_wr)(x) ≈ maximum(x) - minimum(x)truejulia> OrderedWeightsArrayRange(; w1 = owa_wr(4), w2 = reverse(owa_wr(4)))(x) ≈ maximum(x) - minimum(x)trueRelated
OWA_RGOWA_CVaR_RGOWA_TG_RGOrderedWeightsArrayOrderedWeightsArrayFormulationExactOrderedWeightsArraySortingNetworkOrderedWeightsArrayApproxOrderedWeightsArrayRiskMeasureSettings
References
- [209] W. Ogryczak and T. Śliwiński. On solving linear programs with the ordered weighted averaging objective. European Journal of Operational Research 148, 80–91 (2003).
- [199] D. Cajas. OWA portfolio optimization: A disciplined convex programming framework. Available at SSRN 3988927 (2021).
- [12] D. Cajas. Advanced Portfolio Optimization: A Cutting-edge Quantitative Approach (Springer Nature Switzerland, 2025). Section 7.2.3.
PortfolioOptimisers.factory — Method
factory(
x::Union{OrderedWeightsArray, OrderedWeightsArrayRange},
pr::AbstractPriorResult,
args...;
kwargs...
) -> Union{OrderedWeightsArray, OrderedWeightsArrayRange}
Resolve the weight builders of an OrderedWeightsArray or an OrderedWeightsArrayRange against prior result pr, and return the measure with builders that hold numbers.
The measure carries no propagation tag, so it generates no prior factory method of its own and this is the channel the value-level entry points take. The JuMP route reaches the same recursion through set_risk_constraints!, which calls resolve_deferred_quantities directly. The range reads its two builders on the same terms as the single measure reads its one.
A builder holding numbers, a weight vector and a plain function are all carried through unchanged, so the common case allocates nothing.
Related
References
- [12]
- D. Cajas. Advanced Portfolio Optimization: A Cutting-edge Quantitative Approach (Springer Nature Switzerland, 2025).
- [199]
- D. Cajas. OWA portfolio optimization: A disciplined convex programming framework. Available at SSRN 3988927 (2021).
- [209]
- W. Ogryczak and T. Śliwiński. On solving linear programs with the ordered weighted averaging objective. European Journal of Operational Research 148, 80–91 (2003).
- [212]
- M. X. Goemans. Smallest compact formulation for the permutahedron. Mathematical Programming 153, 5–11 (2015).
- [213]
- K. E. Batcher. Sorting networks and their applications. In: Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference (1968); pp. 307–314.