OWA risk measures (b): private API

PortfolioOptimisers.odd_even_merge_pass! — Function
odd_even_merge_pass!(
    c::AbstractVector{Tuple{Int64, Int64}},
    T::Integer,
    p::Integer,
    k::Integer
) -> AbstractVector{Tuple{Int64, Int64}}

Append to c the comparators of one pass of Batcher's odd-even merge network.

The pass compares the positions that are k apart and that are in the same block of 2p positions. A comparator that reads a position past T is omitted.

Algorithm

  1. For each start j from k % p up to T - k - 1, in steps of 2k, and for each offset i from 0 while i + j + k < T and i < k:
  2. Append the comparator (i + j + 1, i + j + k + 1) when the two zero-based positions i + j and i + j + k are in the same block of 2p positions.
  3. Return c.

Arguments

  • c: Comparator list, changed in place.
  • T: Number of values to sort.
  • p: Half the size of the blocks that the pass merges.
  • k: Distance between the two positions of each comparator.

Returns

  • c::Vector{Tuple{Int, Int}}: The comparator list.

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.bitonic_sort! — Function
bitonic_sort!(
    c::AbstractVector{Tuple{Int64, Int64}},
    lo::Integer,
    m::Integer,
    up::Bool
) -> AbstractVector{Tuple{Int64, Int64}}

Append to c the comparators that sort the m positions from lo with a bitonic merge network.

The first half is sorted in the opposite direction and the second half in the direction up, so the two halves make a bitonic sequence. bitonic_merge! then merges it.

Algorithm

  1. If m <= 1, return c unchanged.
  2. Set the half length h = div(m, 2).
  3. Append the comparators that sort the first h positions in the direction !up, by recursion.
  4. Append the comparators that sort the last m - h positions in the direction up, by recursion.
  5. Append the comparators that merge the m positions in the direction up, with bitonic_merge!.

Arguments

  • c: Comparator list, changed in place.
  • lo: First position of the sequence.
  • m: Length of the sequence.
  • up: If true, the sequence is sorted in ascending order. If false, in descending order.

Returns

  • c::Vector{Tuple{Int, Int}}: The comparator list.

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.bitonic_merge! — Function
bitonic_merge!(
    c::AbstractVector{Tuple{Int64, Int64}},
    lo::Integer,
    m::Integer,
    up::Bool
) -> AbstractVector{Tuple{Int64, Int64}}

Append to c the comparators that merge the bitonic sequence of m positions from lo.

The comparator span is the largest power of two below m, so the merge works for every length.

Algorithm

  1. If m <= 1, return c unchanged.
  2. Set the span p = prevpow(2, m - 1), the largest power of two below m.
  3. For each position i from lo to lo + m - p - 1, append the comparator of i and i + p. It puts the smaller value at i when up is true, and at i + p otherwise.
  4. Merge the first p positions and the last m - p positions in the direction up, by recursion.

Arguments

  • c: Comparator list, changed in place.
  • lo: First position of the sequence.
  • m: Length of the sequence.
  • up: If true, the merge puts the smaller value first. If false, it puts the larger value first.

Returns

  • c::Vector{Tuple{Int, Int}}: The comparator list.

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.assert_owa_formulation_weights — Method
assert_owa_formulation_weights(
    _::SortingNetworkOrderedWeightsArray,
    w::AbstractVector{<:Union{Number, AbstractJuMPScalar}}
)

Refuse an OWA weight vector w that is not nondecreasing.

The relaxed sorting network lets a comparator raise its larger value and lower its smaller value by the same amount. A weight vector that decreases between two positions can then lower the risk by such a spread. The model then has no minimum, or its minimum falls below the OWA risk.

Arguments

  • alg: The sorting-network formulation.
  • w: OWA weight vector, after the range measure reverses its second vector.

Validation

  • issorted(w). Raises a DomainError.

Returns

  • nothing.

Related

source
PortfolioOptimisers.resolve_deferred_quantities — Method
resolve_deferred_quantities(x, pr::AbstractPriorResult, slv = nothing)

Resolve the children that deferred_slots declared and the slots that calibration_slots declared, and return x itself when none of them changed.

This is the derived half of the resolution rule. A container declares its children once and both entry points follow: factory reaches them through @fprop, and the JuMP builders reach them through this method. Neither needs a forwarding method per container.

A type that resolves a quantity of its own overrides this with its own method, which is more specific. So the derivation carries container recursion alone, and never guesses how a matrix, a tensor or the centre a moment was taken about comes out of a fit.

Both channels end in one rebuild: a measure that carries both kinds of slot must not be rebuilt twice. resolve_calibration_slots states the calibration half and returns its resolved slots rather than a rebuilt object, and the two answers merge here. The deferred half merges last, so it wins a key both channels declare. A container names one child in both, and the child the recursion resolved is the one to keep.

slv is the effective solver, and the recursion threads it to every child. A container states no solver of its own, so it changes none: each child settles the one it was handed against the one it carries.

Algorithm

  1. Read the slots x declares with deferred_slots, giving slots.
  2. Read the resolved calibration slots with resolve_calibration_slots, giving calibrated.
  3. Return x unchanged when both are empty. A type with neither kind of slot needs no method of its own.
  4. Resolve every entry of slots with resolve_deferred_quantities, threading pr and slv to each, giving resolved. A child measure resolves through its own method, a vector of children through the vector method, and any other occupant comes back unchanged through this method, because it declares no slot: a stated value, nothing or a Deferred Quantity that the enclosing type resolves itself.
  5. Refuse a slot the recursion left unresolved with assert_declared_slot_resolver.
  6. Hand merge(calibrated, resolved) to rebuild_with_slots, which returns x itself when no entry moved and a rebuilt copy when one did.

Returns

  • x itself when no slot moved, and a rebuilt copy of x when one did.

Related

source
resolve_deferred_quantities(
    x::ComposedFunction{typeof(reverse), <:AbstractOrderedWeightsArrayFunction},
    pr::AbstractPriorResult
) -> ComposedFunction{typeof(reverse)}
resolve_deferred_quantities(
    x::ComposedFunction{typeof(reverse), <:AbstractOrderedWeightsArrayFunction},
    pr::AbstractPriorResult,
    slv
) -> ComposedFunction{typeof(reverse)}

Resolve the weight builder inside the reversal that OrderedWeightsArrayRange wraps its w2 in.

The Range constructor stores w2 as reverse ∘ w1 when the caller gives no w2, and a caller who gives a reversed builder gives reverse ∘ f. So the w2 slot holds a composition, and the builder that holds a rule is the inner function of that composition. Without this method the recursion stops at the composition, and a rule in the gain-tail builder does not resolve, while the same rule in w1 does.

The composition is rebuilt around the resolved half, so the reversal survives. The bound names reverse and an AbstractOrderedWeightsArrayFunction, so no other composition reaches it.

Related

source

References

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