GitHub

Online portfolio selection: the family, the geometry, the set and the state

This page has the types and functions that every online portfolio selection rule shares. A rule goes in the alg field of OnlinePortfolioSelection, and it updates the weights after each observation. The page has the abstract type of every rule, and the projection geometries, the measures of distance in which a rule moves its raw step back into the set of allowed weights. BoundedAllocationSet is a set of allowed weights for the set field. A first-order rule can hold a learning-rate schedule in place of a fixed step size, and the abstract type of the schedules is also on this page. online_update! is the one function a new rule must write. The other functions start and update the state of a rule and of a schedule.

PortfolioOptimisers.AbstractOnlinePortfolioSelectionAlgorithm — Type
abstract type AbstractOnlinePortfolioSelectionAlgorithm <: AbstractAlgorithm

Abstract supertype for the Online Selection Rules that an OnlinePortfolioSelection head holds in its alg field.

The rule is the only part of the online portfolio selection family that changes from one paper to the next. It is a struct of the paper's parameters, a private carrier for what the update accumulates, and one update method. The head owns the parts that every rule shares: the Allocation Set, the Causal Pass, the Block Step, the Recursion Read-out and the checks that refuse a bad input. A rule projects its raw step onto the head's Allocation Set in its own Projection Geometry, which it holds in its proj field. The type bound of that field names the geometries that the rule's theorem covers.

Interfaces

To implement a new rule, subtype AbstractOnlinePortfolioSelectionAlgorithm with the paper's parameters and a proj field, and implement the following methods:

  • online_update!(alg::AbstractOnlinePortfolioSelectionAlgorithm, st, w::AbstractVector, x::AbstractVector, rows, set::AbstractAllocationSet) -> Tuple: The Online Update. It reads the rule's carrier st, the allocation w held during the period, the finite price relative x of the period and the rows carrier that the head holds through the period. It returns (st', w'), the carrier and the allocation for the next period. It may write st in place, and it always returns a new vector for w'. A first-order rule also implements the seven-argument form, whose last argument is the Gradient Point that an ExpertMixture gives it. The generic method of that form drops the point.
  • rule_state_seed(alg::AbstractOnlinePortfolioSelectionAlgorithm, w::AbstractVector): The carrier before the first update, or nothing for a rule that carries nothing. w is the Start Allocation, and the carrier takes its length and its element type. The head calls the three-argument form, rule_state_seed(alg, w, set), with its Allocation Set, and the default method of that form drops set. A rule that holds allocations of its own over the assets, as the experts of an ExpertMixture are, implements the three-argument form and projects them onto set.
  • rows_needed(alg::AbstractOnlinePortfolioSelectionAlgorithm) -> Union{Nothing, Integer}: The number of rows that the rule reads at a step. It is 0 for a rule that reads none, and nothing for a rule that reads every row folded so far.
  • projection_geometry(alg::AbstractOnlinePortfolioSelectionAlgorithm) -> AbstractProjectionGeometry: The geometry in which the head projects the Start Allocation. It is the rule's proj field by default.

A rule whose carrier has a per-asset axis also implements port_opt_view(st, i, args...) on the type of the carrier, so that a view of the head slices the carrier. It also implements Base.copy(st), so that the copy of the state that partial_fit makes shares no array with the original.

Arguments

  • alg: The concrete rule.
  • st: The rule's private carrier, or nothing.
  • w: The allocation held during the period. It covers the full pinned universe and sums to one.
  • x: The price relative of the period, price_relative of the row. It is 1 .+ r, and one at a gap, so it is finite at every asset.
  • rows: The rows carrier that the head holds through the period, or nothing when the rule reads no rows. It is a ReturnsResult whose X holds the rows of returns as they arrived, with NaN where there was no return, under the pinned names and the Asset Panel of the buffer. A statistic over it, such as the mean of a forecaster, a prior or a re-solve, reads it as the batch verb reads a carrier, and reduces to its own Coverage Universe. A kernel over the price relatives reads a gap as one through price_relative.
  • set: The head's Allocation Set. The rule projects onto it through project.

Returns

  • (st', w')::Tuple: The carrier and the allocation for the next period.

Examples

A rule that projects one fixed raw step at every period. Under a cap of 0.5, the Euclidean projection moves the excess of the first asset to the other two assets in equal parts.

julia> struct FixedTarget{T1, T2} <: PortfolioOptimisers.AbstractOnlinePortfolioSelectionAlgorithm           q::T1           proj::T2       endjulia> function PortfolioOptimisers.online_update!(alg::FixedTarget, st, w::AbstractVector,                                                   x::AbstractVector, rows,                                                   set::PortfolioOptimisers.AbstractAllocationSet)           wh = PortfolioOptimisers.price_adjusted_allocation(w, x)           return st, PortfolioOptimisers.project(alg.proj, set, alg.q, wh)       endjulia> rd = ReturnsResult(; nx = ["A", "B", "C"], X = [0.1 -0.1 0.0; 0.0 0.2 -0.05]);julia> opt = OnlinePortfolioSelection(; alg = FixedTarget([0.8, 0.1, 0.1], EuclideanProjection()),                                      set = BoundedAllocationSet(;                                                                 wb = WeightBounds(; lb = 0,                                                                                   ub = 0.5)));julia> optimise(opt, rd).w3-element Vector{Float64}: 0.5 0.25 0.25

Related

source
PortfolioOptimisers.AbstractProjectionGeometry — Type
abstract type AbstractProjectionGeometry <: AbstractAlgorithm

Abstract supertype for the Projection Geometries in which an Online Selection Rule projects its raw step back onto the Allocation Set.

The geometry belongs to the theorem of the rule. The regret bound of exponentiated gradient is a relative-entropy argument, and its multiplicative update followed by normalisation is the exact Kullback–Leibler projection onto the simplex. The reversion rules are Euclidean, and their sparsity comes from the entries that the Euclidean projection sets to zero. The type bound of the proj field of every rule names the geometries that its theorem covers.

Mathematical definition

A geometry is a potential $\Psi$. It projects the raw step onto the Allocation Set in the Bregman divergence of that potential.

\[\begin{align} \boldsymbol{w}^{+} &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; D_\Psi(\boldsymbol{w}, \boldsymbol{q})\,, \\ D_\Psi(\boldsymbol{w}, \boldsymbol{q}) &= \Psi(\boldsymbol{w}) - \Psi(\boldsymbol{q}) - \nabla \Psi(\boldsymbol{q})^\intercal (\boldsymbol{w} - \boldsymbol{q})\,. \end{align}\]

Where:

  • $\boldsymbol{w}^{+}$: Projected allocation, the answer of the projection onto the Allocation Set.
  • $\mathcal{W}$: Allocation Set.
  • $D_\Psi$: Bregman divergence of $\Psi$.
  • $\Psi$: Potential of the Projection Geometry.
  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.

Interfaces

To implement a new geometry, subtype AbstractProjectionGeometry and implement the following method for every Allocation Set that it projects onto:

  • project(proj::AbstractProjectionGeometry, set::AbstractAllocationSet, q::AbstractVector, w::AbstractVector) -> AbstractVector: The projection of the raw step q onto set in this geometry, as a new vector.

Arguments

  • proj: The geometry.
  • set: The Allocation Set, with its bounds resolved to vectors.
  • q: The raw step of the rule, before the projection.
  • w: The Price-Adjusted Allocation from which the step trades. A turnover ceiling on a ProgrammeAllocationSet reads it as its reference, and a Held Step returns it. The bounded set reads it only on a Held Step.

Returns

  • w'::AbstractVector: The projected allocation.

A geometry with no closed form on any set carries its own solver, as GramProjection does, and projection_solver reads that solver before the solver of the set.

Examples

A geometry that projects in the norm of a fixed positive diagonal. The asset with the larger weight in the norm moves less.

julia> struct FixedDiagonal{T} <: PortfolioOptimisers.AbstractProjectionGeometry           h::T       endjulia> function PortfolioOptimisers.project(proj::FixedDiagonal, set::BoundedAllocationSet,                                            q::AbstractVector, w::AbstractVector)           return PortfolioOptimisers.bounded_quadratic_projection(q, set.wb, proj.h)       endjulia> set = PortfolioOptimisers.resolve_allocation_set(BoundedAllocationSet(), 2, false, Float64);julia> PortfolioOptimisers.project(FixedDiagonal([1.0, 3.0]), set, [0.8, 0.8], [0.5, 0.5])2-element Vector{Float64}: 0.35 0.65

Related

source
PortfolioOptimisers.EuclideanProjection — Type
struct EuclideanProjection <: AbstractProjectionGeometry

Projects the raw step onto the Allocation Set in squared Euclidean distance.

On the simplex this projection is the sort of Duchi, Shalev-Shwartz, Singer and Chandra (2008). It sets every entry below its threshold to zero, and that is the source of the sparsity of the reversion rules. It is the default geometry of most rules, among them the reversion and tracking rules, the constant rebalanced portfolio, buy-and-hold and the Newton step.

Mathematical definition

\[\begin{align} \Psi(\boldsymbol{w}) &= \tfrac{1}{2} \lVert \boldsymbol{w} \rVert_2^2\,, \\ \mathrm{Proj}_{\mathcal{W}}(\boldsymbol{q}) &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; \tfrac{1}{2} \lVert \boldsymbol{w} - \boldsymbol{q} \rVert_2^2\,, \\ w_i(\theta) &= \min\left(\max\left(q_i - \theta,\, l_i\right),\, u_i\right)\,. \end{align}\]

Where:

  • $\Psi$: Potential of the Projection Geometry.
  • $\mathrm{Proj}_{\mathcal{W}}$: Euclidean projection onto the Allocation Set $\mathcal{W}$.
  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
  • $\mathcal{W}$: Allocation Set.
  • $l_i$, $u_i$: Lower and upper bounds of asset $i$ on a BoundedAllocationSet.
  • $\theta$: Budget multiplier, the root of $\sum_i w_i(\theta) = 1$.

On a BoundedAllocationSet the projection is $\boldsymbol{w}(\theta)$ at the root. The budget $\sum_i w_i(\theta)$ does not increase in $\theta$, and it is linear between the kinks at $q_i - u_i$ and $q_i - l_i$. The geometry admits a negative lower bound.

Examples

julia> EuclideanProjection()EuclideanProjection()

Related

References

  • [177] J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra. Efficient projections onto the l1-ball for learning in high dimensions. In: Proceedings of the 25th International Conference on Machine Learning, 272–279 (2008).
source
PortfolioOptimisers.EntropicProjection — Type
struct EntropicProjection <: AbstractProjectionGeometry

Projects the raw step onto the Allocation Set in relative entropy.

On the simplex this projection is normalisation, q / sum(q). So the multiplicative update of exponentiated gradient, followed by normalisation, is this projection. Under the simplex bounds the projection keeps every positive entry positive and every zero entry at zero, so a zero in the Start Allocation stays zero for the whole run. The projection refuses a raw step with a negative entry, because the logarithm of a negative number is not defined.

Mathematical definition

\[\begin{align} \Psi(\boldsymbol{w}) &= \sum_i w_i \log w_i\,, \\ \mathrm{Proj}^{\mathrm{KL}}_{\mathcal{W}}(\boldsymbol{q}) &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; \sum_i w_i \log \frac{w_i}{q_i}\,, \\ w_i(\theta) &= \min\left(\max\left(q_i e^{-\theta},\, l_i\right),\, u_i\right)\,. \end{align}\]

Where:

  • $\Psi$: Potential of the Projection Geometry.
  • $\mathrm{Proj}^{\mathrm{KL}}_{\mathcal{W}}$: Projection onto $\mathcal{W}$ in relative entropy.
  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
  • $\mathcal{W}$: Allocation Set.
  • $l_i$, $u_i$: Lower and upper bounds of asset $i$ on a BoundedAllocationSet.
  • $\theta$: Budget multiplier, the root of $\sum_i w_i(\theta) = 1$.

The Bregman divergence of $\Psi$ is $\sum_i w_i \log (w_i / q_i) - \sum_i w_i + \sum_i q_i$, and on the budget its last two terms are constant. On a BoundedAllocationSet the projection is $\boldsymbol{w}(\theta)$ at the root. Under the simplex bounds the root is $e^{-\theta} = 1 / \sum_i q_i$. Under other bounds a floor $l_i > 0$ lifts a zero entry to $l_i$, and a cap $u_i = 0$ sets a positive entry to zero. The budget $\sum_i w_i(\theta)$ does not increase in $\theta$, and it is linear in $e^{-\theta}$ between the kinks at $l_i / q_i$ and $u_i / q_i$. The geometry refuses a negative lower bound.

Examples

julia> EntropicProjection()EntropicProjection()

Related

References

  • [178] D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998).
source
PortfolioOptimisers.GramProjection — Type
struct GramProjection{T1<:(Union{var"#s1802", var"#s1801"} where {var"#s1802"<:Solver, var"#s1801"<:(AbstractVector{<:Solver})}), T2<:(Union{Nothing, var"#s7442"} where var"#s7442"<:(AbstractMatrix))} <: AbstractProjectionGeometry

Projects the raw step onto the Allocation Set in the norm of the rule's Gram matrix.

The online Newton step of Agarwal, Hazan, Kale and Schapire (2006) proves its logarithmic regret in this geometry. The projection has no closed form on any set, the bare simplex included, so the geometry carries its own solver and every projection in it is a programme. The rule owns the matrix. NewtonStep binds the Gram matrix of its carrier to the A field of the geometry at every step, through gram_geometry. A geometry with no matrix refuses to project. The head projects the Start Allocation before the rule sees a gradient. The Gram matrix is the identity there, and the geometry is the Euclidean one, so projection_geometry returns EuclideanProjection for the Newton step.

Mathematical definition

\[\begin{align} \Psi(\boldsymbol{w}) &= \tfrac{1}{2} \boldsymbol{w}^\intercal \mathbf{A} \boldsymbol{w}\,, \\ \mathrm{Proj}^{\mathbf{A}}_{\mathcal{W}}(\boldsymbol{q}) &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; (\boldsymbol{w} - \boldsymbol{q})^\intercal \mathbf{A} (\boldsymbol{w} - \boldsymbol{q})\,. \end{align}\]

Where:

  • $\Psi$: Potential of the Projection Geometry.
  • $\mathbf{A}$: Gram matrix that the rule binds at the step, symmetric and positive definite.
  • $\mathrm{Proj}^{\mathbf{A}}_{\mathcal{W}}$: Projection onto $\mathcal{W}$ in the norm of $\mathbf{A}$.
  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
  • $\mathcal{W}$: Allocation Set.

At $\mathbf{A} = I$ the projection is the Euclidean one.

Fields

  • slv: Solver or vector of solvers.
  • A: The Gram matrix in whose norm the geometry projects. The rule binds it at each step, and it is nothing before the rule binds one.

Constructors

GramProjection(;    slv::Slv_VecSlv,    A::Option{<:AbstractMatrix} = nothing) -> GramProjection

Keywords correspond to the struct's fields. The rule binds A at each step, and a caller leaves it at nothing.

Validation

  • If A is given: size(A, 1) == size(A, 2). A DimensionMismatch is thrown otherwise.

Examples

julia> GramProjection(; slv = Solver(; solver = nothing))GramProjection  slv ┼ Solver      │          name ┼ String: ""      │        solver ┼ nothing      │      settings ┼ nothing      │     check_sol ┼ @NamedTuple{}: NamedTuple()      │   add_bridges ┴ Bool: true    A ┴ nothing

Related

References

  • [179] A. Agarwal, E. Hazan, S. Kale and R. E. Schapire. Algorithms for portfolio management based on the Newton method. In: Proceedings of the 23rd International Conference on Machine Learning, 9–16 (2006).
source
PortfolioOptimisers.AbstractLearningRateSchedule — Type
abstract type AbstractLearningRateSchedule <: AbstractAlgorithm

Abstract supertype for the Learning-Rate Schedules that a first-order Online Selection Rule can hold in eta in place of a number.

The rule reads its schedule at every update, as a function of the period count and of the rule's carrier. So a schedule can follow the count alone, read a running statistic of the run that the carrier keeps for it, or name a stage boundary at which the rule restarts. A schedule owns no state. What it accumulates lives on the rule's carrier. The schedule seeds that statistic and writes it once for each row. By default it writes after the step, so the rate of a period reads only the past. A schedule that chooses the rate from the row of the period itself writes before the rule reads the rate.

Interfaces

To implement a new schedule, subtype AbstractLearningRateSchedule and implement the following methods:

  • learning_rate(sched::AbstractLearningRateSchedule, t::Integer, st) -> Real: The rate of the update at period t, the t-th row that the rule has seen. st is the rule's carrier, and its s field is the schedule's own statistic.
  • restart(sched::AbstractLearningRateSchedule, t::Integer) -> Bool: Whether the update at period t closes a stage. At a stage boundary the rule returns the Start Allocation for period t + 1 and puts its carrier back at its seed. The default is false.
  • schedule_state_seed(sched::AbstractLearningRateSchedule, w::AbstractVector): The statistic that the carrier holds for the schedule before the first row. The default is nothing.
  • schedule_update!(sched::AbstractLearningRateSchedule, s, w::AbstractVector, x::AbstractVector): Writes the row into the statistic s, from the allocation w played during the period and its price relative x. The default returns s unchanged.
  • reads_period_row(sched::AbstractLearningRateSchedule) -> Bool: Whether the schedule chooses the rate of period t from the row of period t. When it does, the rule writes the statistic before it reads the rate, and not after the step. The default is false. A rule whose update also needs the rate of the next period, as the online form of ExpectationMaximisation does, refuses a schedule that returns true, because the row of the next period is not there to read.
  • mixing_share(sched::AbstractLearningRateSchedule, t::Integer, alpha::Real) -> Real: The share of the uniform mix in the update at period t. The default is the rule's own alpha, and a schedule that sets the share from a stage length returns its own.

A statistic with entries over the assets, such as the expert allocations of a schedule that replays the run, also implements schedule_state_view. That method slices the statistic to the selected assets with the rule's carrier. The default copies a statistic over the run as it is.

A number in eta is the constant schedule. The six verbs return the number, false, nothing, the statistic unchanged, false and alpha.

Examples

A schedule that halves the rate at every period, from 0.4. Two steps of exponentiated gradient at the rates 0.4 and 0.2 give the allocation below.

julia> struct HalvingRate{T} <: PortfolioOptimisers.AbstractLearningRateSchedule           eta::T       endjulia> function PortfolioOptimisers.learning_rate(sched::HalvingRate, t::Integer, st)           return sched.eta / 2^(t - 1)       endjulia> PortfolioOptimisers.learning_rate(HalvingRate(0.4), 3, nothing)0.1julia> rd = ReturnsResult(; nx = ["A", "B", "C"], X = [0.1 -0.1 0.0; 0.0 0.2 -0.05]);julia> round.(optimise(OnlinePortfolioSelection(; alg = MirrorDescent(; eta = HalvingRate(0.4))),                       rd).w; digits = 4)3-element Vector{Float64}: 0.3436 0.3295 0.327

Related

source
PortfolioOptimisers.BoundedAllocationSet — Type
struct BoundedAllocationSet{__T_wb, __T_sets} <: AbstractAllocationSet

Limits the allocation to the budget and to per-asset weight bounds, with closed-form projections and no solver.

The default, BoundedAllocationSet(), is the simplex. Under the simplex bounds the Euclidean projection is the sort of Duchi and co-authors, and the entropic projection is normalisation. Under any other bound each projection clips the raw step at one scalar, the root of the budget, which breakpoint_root finds exactly from the kinks of the budget. The barrier geometries find their root by bisection. The Euclidean geometry admits a negative lower bound. The entropic and barrier geometries refuse it, because their potentials are not defined below zero.

Mathematical definition

\[\begin{align} \mathcal{W} &= \left\lbrace \boldsymbol{w} \in \mathbb{R}^N : \boldsymbol{1}^\intercal \boldsymbol{w} = 1,\; l_i \leq w_i \leq u_i \right\rbrace\,. \end{align}\]

Where:

  • $\mathcal{W}$: Allocation Set.
  • $N$: Number of assets.
  • $l_i$, $u_i$: Lower and upper bounds of asset $i$ on a BoundedAllocationSet.

The set is not empty when $\sum_i l_i \leq 1 \leq \sum_i u_i$. At $l_i = 0$ and $u_i = 1$ it is the probability simplex.

Fields

  • wb: Weight bounds.
  • sets: Sets used to map estimator values to assets.

Constructors

BoundedAllocationSet(;    wb::Option{<:WbE_Wb} = WeightBounds(),    sets::Option{<:UniverseSets} = nothing) -> BoundedAllocationSet

Keywords correspond to the struct's fields.

Validation

View parameters

When port_opt_view is called on this type, the following @vprop-tagged fields are automatically subset to the selected indices:

Examples

julia> BoundedAllocationSet()BoundedAllocationSet    wb ┼ WeightBounds       │   lb ┼ Float64: 0.0       │   ub ┴ Float64: 1.0  sets ┴ nothing

Related

source
PortfolioOptimisers.resolve_allocation_set — Function
resolve_allocation_set(
    set::BoundedAllocationSet,
    N::Integer,
    strict::Bool,
    datatype::DataType
) -> Union{BoundedAllocationSet{WeightBounds{__T_lb, __T_ub}, Nothing} where {__T_lb, __T_ub}, BoundedAllocationSet{WeightBounds{__T_lb, __T_ub}, UniverseSets{__T_xkey, __T_uxkey, __T_tfkey, __T_utfkey, __T_cfkey, __T_ucfkey, __T_nikey, __T_dict}} where {__T_lb, __T_ub, __T_xkey, __T_uxkey, __T_tfkey, __T_utfkey, __T_cfkey, __T_ucfkey, __T_nikey, __T_dict}}

Resolves the weight bounds of a BoundedAllocationSet to vectors over N assets.

weight_bounds_constraints does the work, with the set's sets for a bound that names assets. A WeightBoundsEstimator resolves a side that it states as a scalar to that scalar, and the projections read a bound at each asset. So a second call expands the resolved pair to N entries. The set that comes back keeps its sets.

Related

source
resolve_allocation_set(
    set::ProgrammeAllocationSet,
    N::Integer,
    strict::Bool,
    datatype::DataType
) -> ProgrammeAllocationSet{var"#s185", _A, _B, _C, _D, _E, Bool, _F, _G, _H, _I, _J, _K, _L, _M, _N, _O, _P, _Q, _R, _S, _T, _U, _V, _W, _X, <:Number, <:Number} where {var"#s185"<:AbstractPriorEstimator, _A, _B, _C, _D, _E, _F, _G, _H, _I, _J, _K, _L, _M, _N, _O, _P, _Q, _R, _S, _T, _U, _V, _W, _X}

Resolves the slots of a ProgrammeAllocationSet that hold a name or an estimator, once per fold.

This is the first stage of the set's resolution. It resolves each slot to a value over the N assets through sets, as processed_jump_optimiser_attributes resolves the same slot of a JuMPOptimiser. The slots that read the head's rows go unchanged to the second stage, resolve_allocation_set_rows, which runs at every step.

Algorithm

  1. Resolve the weight bounds wb over the N assets with weight_bounds_constraints.
  2. Resolve the thresholds lt and st with threshold_constraints.
  3. Resolve the grouped cardinality constraints gcarde and sgcarde with linear_constraints, with integer values.
  4. Resolve the sub-group matrices smtx and sgmtx with asset_sets_matrix. When the two slots hold one object, resolve it once and give the result to both slots.
  5. Resolve the sub-group thresholds slt and sglt, then sst and sgst, with threshold_constraints, in the same way.
  6. Resolve the turnover ceilings tn with turnover_constraints.
  7. When lcse holds no exposure estimator (exposure_keyed), resolve it with linear_constraints. Otherwise keep it for the second stage, because an exposure row needs the loadings of the prior.
  8. Return a new set that holds the resolved slots and every other slot of set.

Arguments

  • set: The programme set.
  • N: The number of assets.
  • strict: Whether to throw an error if sets does not contain the desired value in sets.dict[key].
  • datatype: The element type of the resolved values. The grouped cardinality constraints take Int.

Returns

  • set'::ProgrammeAllocationSet: The set with its named slots resolved.

Related

source
PortfolioOptimisers.project — Function
project(proj::EuclideanProjection, set::BoundedAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::EntropicProjection, set::BoundedAllocationSet, q::AbstractVector, w::AbstractVector)

Projects a rule's raw step onto a BoundedAllocationSet in the Euclidean or the entropic geometry.

These are the closed-form arms of the Constrained Update. Under the simplex bounds the Euclidean arm is the sort of project_simplex, and the entropic arm is normalisation. Under any other bound each arm finds the root of its budget exactly, from the kinks of the budget, through breakpoint_root. A root whose allocation misses the budget in floating point gives the Held Step, through budget_or_held_step.

Mathematical definition

\[\begin{align} w^{+}_i &= \min\left(\max\left(q_i - \theta,\, l_i\right),\, u_i\right) \quad \text{(Euclidean)}\,, \\ w^{+}_i &= \min\left(\max\left(q_i e^{-\theta},\, l_i\right),\, u_i\right) \quad \text{(entropic)}\,, \\ \sum_i w^{+}_i &= 1\,. \end{align}\]

Where:

  • $\boldsymbol{w}^{+}$: Projected allocation, the answer of the projection onto the Allocation Set.
  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
  • $l_i$, $u_i$: Lower and upper bounds of asset $i$ on a BoundedAllocationSet.
  • $\theta$: Budget multiplier, the root of $\sum_i w_i(\theta) = 1$.

Each form is the KKT solution of the projection in its geometry, and $\theta$ is the multiplier of the budget. In the entropic form a zero entry stays at $l_i$ for every $\theta$. So the entropic arm needs $q_i \geq 0$, $\sum_i q_i > 0$, $l_i \geq 0$, and $\sum_{q_i > 0} u_i + \sum_{q_i = 0} l_i \geq 1$.

Algorithm

Under EuclideanProjection:

  1. When the bounds are the simplex bounds, refuse a non-finite q with assert_finite_raw_step, and return project_simplex of q.
  2. Otherwise, find the allocation at the root with bounded_quadratic_projection at unit weights.
  3. Return that allocation, or the Held Step w, with budget_or_held_step.

Under EntropicProjection:

  1. Refuse a non-finite q, a q with a negative entry, and a q that sums to zero.
  2. When the bounds are the simplex bounds, return q ./ sum(q).
  3. Refuse a negative lower bound, and bounds that no allocation on the budget satisfies, with assert_feasible_bounds.
  4. Refuse a q that cannot reach the budget, because its zeros stay at their floors and its positive entries stop at their caps.
  5. Find the scale t at which sum(clamp.(t .* q, lb, ub)) is one, with breakpoint_root over the kinks lb ./ q and ub ./ q. The search runs in -t, in which the budget does not increase.
  6. Return clamp.(t .* q, lb, ub), or the Held Step w, with budget_or_held_step.

Arguments

  • proj: The geometry.
  • set: The set, with its bounds resolved.
  • q: The raw step.
  • w: The Price-Adjusted Allocation from which the step trades. A Held Step returns it.

Validation

  • all(isfinite, q). A DomainError is thrown otherwise.
  • sum(lb) <= 1 <= sum(ub) over the resolved bounds, off the simplex bounds. An ArgumentError is thrown otherwise.
  • Under EntropicProjection: all(>=(0), q), sum(q) > 0, all(>=(0), lb) and sum(ifelse.(q .> 0, ub, lb)) >= 1. A DomainError is thrown otherwise.

Returns

  • w'::Vector: The projected allocation as a new vector, or a copy of w on a Held Step.

Related

source
project(proj::TsallisProjection, set::BoundedAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::LogBarrierProjection, set::BoundedAllocationSet, q::AbstractVector, w::AbstractVector)

Projects the raw step q onto a BoundedAllocationSet in the Tsallis or the log-barrier geometry. These are the barrier arms of the Constrained Update, and w is the Price-Adjusted Allocation.

Neither potential has a closed-form projection onto the simplex, so the arms use the scalar root of barrier_projection on every bound, the simplex included. A root whose allocation misses the budget in floating point gives the Held Step (budget_or_held_step). This happens, for example, under the log barrier when a raw entry is 1e-20. Its base is 1e20, and the multiplier that brings the entry to a share of the budget cancels against that base.

Algorithm

  1. Refuse a negative or non-finite entry of q and a negative floor, with assert_barrier_raw_step.
  2. Map q to its mirror image b, q .^ (alpha - 1) under the Tsallis geometry and inv.(q) under the log barrier. A zero entry maps to Inf.
  3. Find the allocation wn with barrier_projection, on b, the inverse mirror map and the bounds of set.
  4. Return wn, or the Held Step w when wn misses the budget in floating point, with budget_or_held_step.

Arguments

  • proj: The barrier geometry.
  • set: The bounded set, its bounds resolved.
  • q: The raw step.
  • w: The Price-Adjusted Allocation the step trades from, the answer of a Held Step.

Validation

  • all(>= 0, q) and every entry finite. A DomainError is thrown otherwise.
  • all(>= 0, lb) over the resolved bounds. A DomainError is thrown otherwise.
  • Everything barrier_projection refuses.

Returns

  • w'::Vector: The projected allocation, or w copied on a Held Step.

Related

source
project(proj::DiagonalProjection, set::BoundedAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::DiagonalProjection, set::ProgrammeAllocationSet, q::AbstractVector, w::AbstractVector)

Projects the raw step q onto the Allocation Set set in the norm of diag(proj.h). These are the diagonal arms of the Constrained Update, and w is the Price-Adjusted Allocation.

On a bounded set the weights of the norm break the sort that projects onto the simplex in the Euclidean geometry. So the bounded arm finds the scalar root on every bound, the simplex included.

Algorithm

On a BoundedAllocationSet:

  1. Find the allocation wn at the weighted scalar root with bounded_quadratic_projection, on the bounds of set and the weights proj.h.
  2. Return wn, or the Held Step w when wn misses the budget in floating point, with budget_or_held_step.

On a ProgrammeAllocationSet:

  1. Solve the programme of projection_programme, whose objective set_projection_objective! writes, and return its allocation.

Related

source
project(proj::GramProjection, set::BoundedAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::EuclideanProjection, set::ProgrammeAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::EntropicProjection, set::ProgrammeAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::GramProjection, set::ProgrammeAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::TsallisProjection, set::ProgrammeAllocationSet, q::AbstractVector, w::AbstractVector)
project(proj::LogBarrierProjection, set::ProgrammeAllocationSet, q::AbstractVector, w::AbstractVector)

Projects a raw step onto the Allocation Set by the programme of projection_programme.

These are the programme arms of the Constrained Update. They cover every pair of a geometry and a set except the scalar roots on the bounded set. Under EntropicProjection, TsallisProjection and LogBarrierProjection, clip_at_zero sets every negative entry of the answer to zero. The solver can give an entry slightly below zero, within its tolerance, and the next step must not read it.

Validation

Related

source
PortfolioOptimisers.online_update! — Function
online_update!(alg::AbstractOnlinePortfolioSelectionAlgorithm, st, w::AbstractVector, x::AbstractVector, rows, set::AbstractAllocationSet)
online_update!(alg::AbstractOnlinePortfolioSelectionAlgorithm, st, w::AbstractVector, x::AbstractVector, rows, set::AbstractAllocationSet, point::Option{<:AbstractVector})

Runs the Online Update, one row of the online portfolio selection recursion, which each rule writes once.

The function reads the rule, its private carrier st, the allocation w held during the period, the finite price relative x of that period, the rows carrier that the head holds through the period, and the head's Allocation Set. It returns (st', w'), the carrier and the allocation for the next period. A rule may write its carrier in place, and nothing is a legal carrier. w' is always a new vector, because the projection makes one, so the update never writes a w that is a view after port_opt_view.

Every rule makes the same two steps. It takes an unconstrained step to a raw vector, and it then calls project onto the set in its geometry. A rule that reads w continues from the allocation it gets, which is the Start Allocation on the first row.

The seven-argument form names the Gradient Point. An ExpertMixture under BlendPoint gives every expert its played blend as point. A first-order rule then evaluates its gradient at that point and steps from its own iterate, so every expert reads the one gradient on which the dynamic-regret mixtures state their bounds. The generic method drops the point and runs the six-argument update. So a rule with no gradient ignores the point, and a nothing point, which the mixture gives under OwnPoint, runs the six-argument update for every rule. MirrorDescent, OptimisticStep and AdaptiveSubgradient read a given point.

Mathematical definition

\[\begin{align} (s_{t+1}, \boldsymbol{q}) &= U(s_t, \boldsymbol{w}_t, \boldsymbol{x}_t)\,, \\ \boldsymbol{w}_{t+1} &= \underset{\boldsymbol{w} \in \mathcal{W}}{\arg\min} \; D_\Psi(\boldsymbol{w}, \boldsymbol{q})\,. \end{align}\]

Where:

  • $U$: Unconstrained step of the rule.
  • $s_t$: Carrier of the rule before the update of period $t$.
  • $\boldsymbol{w}_t$: Iterate of the rule at period $t$, the allocation its update reads.
  • $\boldsymbol{x}_t$: Price relative vector of period $t$, each asset's price over its price one period earlier.
  • $\boldsymbol{q}$: Raw step, the vector the rule's unconstrained step gives before the projection onto the Allocation Set.
  • $\mathcal{W}$: Allocation Set.
  • $D_\Psi$: Bregman divergence of $\Psi$.

Arguments

  • alg: The rule.
  • st: The rule's carrier, or nothing.
  • w: The allocation held during the period.
  • x: The price relative of the period, 1 .+ r, one at a gap.
  • rows: The rows carrier that the head holds through the period, a ReturnsResult of the rows as they arrived, or nothing.
  • set: The Allocation Set, resolved.
  • point: The Gradient Point, the allocation a first-order rule evaluates its gradient at, or nothing for its own iterate.

Returns

  • (st', w')::Tuple: The carrier and the allocation for the next period.

Related

source
PortfolioOptimisers.rule_state_seed — Function
rule_state_seed(::AbstractOnlinePortfolioSelectionAlgorithm, ::AbstractVector)
rule_state_seed(alg::AbstractOnlinePortfolioSelectionAlgorithm, w::AbstractVector,
                set::Option{<:AbstractAllocationSet})

Returns the carrier that a rule holds before its first update. The default is nothing, for a rule that carries nothing.

The head calls the three-argument form with its Allocation Set, and the default method of that form drops set. So a rule whose carrier reads only the Start Allocation implements the two-argument form. A rule that holds allocations of its own over the assets, as an ExpertMixture and a FollowTheLeadingHistory hold their experts, implements the three-argument form. It projects each allocation onto set, as the head projects its w0. When set is nothing, the method projects nothing.

Related

source
PortfolioOptimisers.reads_period_row — Function
reads_period_row(eta::Real)
reads_period_row(sched::AbstractLearningRateSchedule)

Checks whether the schedule chooses the rate of period t from the row of period t.

It is true for a schedule that replays the period before it returns a rate, as WindowedBestRate does. It is false for a number and for every schedule that reads only the past. When it is true, a rule writes the statistic before it reads the rate. Otherwise the rule writes it after its step. statistic_before_rate and statistic_after_step are the two calls.

Related

source
PortfolioOptimisers.schedule_state_view — Function
schedule_state_view(s, i)

Slices a schedule's statistic to the selected assets when a view slices the rule's carrier.

By default it returns a copy of the statistic as it is, because a schedule that reads the count or the run keeps a statistic over the run and not over the assets. A statistic that holds allocations, as the statistic of WindowedBestRate does, slices and renormalises each allocation through renormalised_view.

Related

source
PortfolioOptimisers.merge_states — Method
merge_states(
    _::OnlinePortfolioSelectionState,
    _::OnlinePortfolioSelectionState
)

Refuses to merge two online selection states.

An Online Update is not a sufficient statistic for its block. A carrier can be one, such as a Gram sum or a prefix of rows, but the allocation beside it is not. So two states folded on disjoint blocks describe no single run. To fold the rows in one pass, run the Causal Pass, which costs O(N) a row.

Validation

  • The function always throws an ArgumentError.

Related

source
PortfolioOptimisers.port_opt_view — Method
port_opt_view(
    x::OnlinePortfolioSelectionState,
    i,
    args...
) -> OnlinePortfolioSelectionState{__T_n, __T_w, _A, __T_X, __T_nx, __T_pnl, __T_amsk, __T_ts, __T_hold} where {__T_n<:Integer, __T_w<:(AbstractVector), _A, __T_X<:Union{Nothing, SampleBufferState}, __T_nx<:Union{Nothing, AbstractVector{<:AbstractString}}, __T_pnl<:Union{Nothing, AssetPanel}, __T_amsk<:Union{Nothing, AbstractVector{<:Bool}}, __T_ts<:Union{Nothing, AbstractVector}, __T_hold<:Union{Nothing, HeldStep}}

Slices an OnlinePortfolioSelectionState to the selected assets, giving the state of the same observations over those assets.

The method slices w and renormalises it. It sends the carrier to its own view through rule_state_view, and the rows buffer to the view of SampleBufferState. It slices the names, the panel and the mask, and it keeps the count, the timestamps and the hold record. The view is a copy for the read-out, and the recursion keeps the full w.

Arguments

  • x: The state to slice.
  • i: Index or indices of the assets to keep.
  • args...: Additional positional arguments, forwarded to the carrier's view.

Returns

  • state::OnlinePortfolioSelectionState: The state over the selected assets.

Related

source

References

[177]
J. Duchi, S. Shalev-Shwartz, Y. Singer and T. Chandra. Efficient projections onto the l1-ball for learning in high dimensions. In: Proceedings of the 25th International Conference on Machine Learning (2008); pp. 272–279.
[178]
D. P. Helmbold, R. E. Schapire, Y. Singer and M. K. Warmuth. On-line portfolio selection using multiplicative updates. Mathematical Finance 8, 325–347 (1998).
[179]
A. Agarwal, E. Hazan, S. Kale and R. E. Schapire. Algorithms for portfolio management based on the Newton method. In: Proceedings of the 23rd International Conference on Machine Learning (2006); pp. 9–16.