OWA risk measures (b)

PortfolioOptimisers.SortingNetworkOrderedWeightsArray — Type
struct SortingNetworkOrderedWeightsArray{__T_merge, __T_ordering} <: OrderedWeightsArrayFormulation

OWA 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 = :mkl factorises with MKL Pardiso. It needs using 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() and KKT_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()) -> SortingNetworkOrderedWeightsArray

Keywords correspond to the struct's fields.

Examples

julia> SortingNetworkOrderedWeightsArray()SortingNetworkOrderedWeightsArray     merge ┼ BitonicMerge()  ordering ┴ ComparatorOrdering()

Related

References

  • [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 AFIPS Spring Joint Computer Conference, 307–314 (1968).
source
PortfolioOptimisers.AbstractSortingNetworkMerge — Type
abstract type AbstractSortingNetworkMerge <: AbstractAlgorithm

Abstract 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 sorts T values 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 position i and the larger value at position j. 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

  • [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 AFIPS Spring Joint Computer Conference, 307–314 (1968).
source
PortfolioOptimisers.OddEvenMerge — Type
struct OddEvenMerge <: AbstractSortingNetworkMerge

Sorts 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).
source
PortfolioOptimisers.BitonicMerge — Type
struct BitonicMerge <: AbstractSortingNetworkMerge

Sorts 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).
source
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

  1. Start with the empty comparator list c and the block half-size p = 1.
  2. While p < T, run the passes of the merge of the blocks of 2p positions. For each distance k from p down to 1, halved at each pass, append the comparators of the pass with odd_even_merge_pass!.
  3. Double p, and repeat step 2.
  4. 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 position i and the larger value at position j.

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).
source
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 position i and the larger value at position j.

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).
source
PortfolioOptimisers.AbstractSortingNetworkOrdering — Type
abstract type AbstractSortingNetworkOrdering <: AbstractAlgorithm

Abstract 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, from sorting_network.

Returns

  • cols::Vector{Int}: A permutation of 1:(2 * length(c)). Comparator k writes the values 2k - 1, the smaller one, and 2k, the larger one. Value m is the network variable cols[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 1

Related

source
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 4

Related

source
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

  1. Build wire, the position of each network value. Comparator k writes value 2k - 1 to its first position and value 2k to its second position.
  2. Sort the values by wire with a stable sort, which gives the permutation sortperm(wire).
  3. Return its inverse, the column of each value.

Arguments

  • alg: The position order.
  • c: Comparators of the network.

Returns

  • cols::Vector{Int}: A permutation of 1:(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 3

Related

source
PortfolioOptimisers.OrderedWeightsArrayRange — Type
struct OrderedWeightsArrayRange{__T_settings, __T_w1, __T_w2, __T_alg} <: RangeRiskMeasure

Measures 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.

Warning

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 of w1 when it receives nothing, and stores a given w2 as 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()) -> OrderedWeightsArrayRange

Keywords correspond to the struct's fields. w2 = nothing stores the reversal of w1.

Validation

  • If w1 is a VecNum: !isempty(w1). Raises an IsEmptyError.
  • If w2 is a VecNum: !isempty(w2). Raises an IsEmptyError.
  • If both w1 and w2 are VecNum: length(w1) == length(w2). Raises a DimensionMismatch.
  • If both w1 and w2 are VecNum and alg is a SortingNetworkOrderedWeightsArray: issorted(w1 - w2), with w2 as stored. Raises a DomainError. 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)true

Related

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.
source
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

source

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.