Sparse portfolio algorithms
A ShortTermSparsePortfolio step finds the point it projects onto the allowed weights in one of three ways, each from the short-term sparse portfolio of Lai et al. [95]. L1Optimum takes the optimum of the problem of [95]. HuberOptimum takes the fixed point of the iteration of [95], in closed form. AlternatingDirectionMethod runs that iteration until the stopping rule of [95]. A new algorithm subtypes AbstractSparsePortfolioAlgorithm and adds a method of sparse_portfolio_iterate.
PortfolioOptimisers.L1Optimum — Type
struct L1Optimum <: AbstractSparsePortfolioAlgorithmPuts the whole budget on the asset with the largest Price Relative Forecast, and splits it in equal parts between tied assets.
This is the optimum of the programme of the short-term sparse portfolio, equation (12) of [95]. The optimum does not depend on $\lambda$, so the algorithm takes no parameter. Where the programme has no minimum, the algorithm returns the same split.
Mathematical definition
\[\begin{align} \boldsymbol{b}^\star &= \underset{\boldsymbol{b}}{\arg\min} \; \langle \boldsymbol{b}, \boldsymbol{\phi} \rangle + \lambda \lVert \boldsymbol{b} \rVert_1 \quad \text{s.t.} \quad \boldsymbol{1}^\intercal \boldsymbol{b} = 1\,, \\ \boldsymbol{b}^\star &= \frac{1}{\lvert \mathcal{K} \rvert} \sum_{k \in \mathcal{K}} \boldsymbol{e}_k\,, \quad \mathcal{K} = \underset{i}{\arg\min} \; \phi_i\,. \end{align}\]
Where:
- $\boldsymbol{b}^\star$: Optimum of the programme.
- $\boldsymbol{b}$: Unscaled target of the short-term sparse portfolio step, the vector whose scaled projection is the next allocation.
- $\boldsymbol{\phi}$: Objective vector of the short-term sparse portfolio step, $-(1.1 \log \hat{\boldsymbol{x}} + \boldsymbol{1})$ for the Price Relative Forecast $\hat{\boldsymbol{x}}$. Its smallest entry is the largest forecast.
- $\lambda$: Penalty weight of the $L_1$ norm, positive.
- $\mathcal{K}$: Set of the assets with the smallest entry of $\boldsymbol{\phi}$.
- $\boldsymbol{e}_k$: Unit vector of asset $k$.
Over $\boldsymbol{b} \geq \boldsymbol{0}$ the penalty is the constant $\lambda$, so the optimum there is a vertex $\boldsymbol{e}_k$ with $k \in \mathcal{K}$. A short of $s$ on asset $j$ that funds more of asset $k$ changes the objective by $s (\phi_k - \phi_j + 2 \lambda)$. That change is not negative while $\max \boldsymbol{\phi} - \min \boldsymbol{\phi} \leq 2 \lambda$, so no short improves on the vertex. Past that bound the programme has no minimum, and the objective falls without end along that short from the vertex. Tied assets share an optimal face, and the equal split is its centre.
Examples
julia> L1Optimum()L1Optimum()Related
References
- [95] Z.-R. Lai, P.-Y. Yang, L. Fang and X. Wu. Short-term sparse portfolio optimization based on alternating direction method of multipliers. Journal of Machine Learning Research 19, 1–28 (2018). Section 3.2, Equation 12.
PortfolioOptimisers.HuberOptimum — Type
struct HuberOptimum{__T_lambda, __T_gamma} <: AbstractSparsePortfolioAlgorithmFinds the fixed point of the alternating direction iteration of the short-term sparse portfolio in closed form.
The iteration of [95] converges to this point, so it is the default algorithm of ShortTermSparsePortfolio. Where the programme has no minimum, the algorithm returns the split of L1Optimum.
Mathematical definition
\[\begin{align} \underset{\boldsymbol{b}, \boldsymbol{g}}{\min} &\; \langle \boldsymbol{b}, \boldsymbol{\phi} \rangle + \lambda \lVert \boldsymbol{g} \rVert_1 + \frac{a}{2} \lVert \boldsymbol{b} - \boldsymbol{g} \rVert_2^2 \quad \text{s.t.} \quad \boldsymbol{1}^\intercal \boldsymbol{b} = 1\,, \\ h(b) &= \underset{g}{\min} \; \lambda \lvert g \rvert + \frac{a}{2} (b - g)^2 = \begin{cases} \tfrac{a}{2} b^2 & \lvert b \rvert \leq \gamma\,, \\ \lambda \lvert b \rvert - \tfrac{\lambda \gamma}{2} & \text{otherwise}\,, \end{cases} \\ b_i(\nu) &= \mathrm{clamp}\left( -\frac{\phi_i + \nu}{a}, -\gamma, \gamma \right)\,, \quad \nu \in \left[ -\lambda - \min \boldsymbol{\phi}, \lambda - \max \boldsymbol{\phi} \right]\,. \end{align}\]
Where:
- $\boldsymbol{b}$: Unscaled target of the short-term sparse portfolio step, the vector whose scaled projection is the next allocation.
- $\boldsymbol{g}$: Auxiliary vector that carries the $L_1$ penalty in place of the target.
- $\boldsymbol{\phi}$: Objective vector of the short-term sparse portfolio step, $-(1.1 \log \hat{\boldsymbol{x}} + \boldsymbol{1})$ for the Price Relative Forecast $\hat{\boldsymbol{x}}$. Its smallest entry is the largest forecast.
- $\lambda$: Penalty weight of the $L_1$ norm, positive.
- $\gamma$: Soft-threshold width, positive.
- $a$: Quadratic coupling $\lambda / \gamma$ of the target to the auxiliary vector.
- $h$: Huber penalty of one coordinate, the minimum of the programme over the auxiliary coordinate $g$.
- $\nu$: Multiplier of the budget constraint $\boldsymbol{1}^\intercal \boldsymbol{b} = 1$.
- $b_i(\nu)$: Coordinate of asset $i$ at the multiplier $\nu$, where $\lvert \phi_i + \nu \rvert < \lambda$.
- $N$: Number of assets.
The programme is equation (20) of [95] without its penalty on the budget residual, which is zero on the budget. The minimum over $\boldsymbol{g}$ is the soft threshold of $\boldsymbol{b}$ at $\gamma$, and it leaves the penalty $h$ on each coordinate. Equation (19) of [95] is $h / \lambda$.
The derivative $h'(b) = \mathrm{clamp}(a b, -\lambda, \lambda)$ is bounded, so a multiplier $\nu$ exists only in the interval above. An asset with $\lvert \phi_i + \nu \rvert < \lambda$ holds $b_i(\nu)$. An asset with $\lvert \phi_i + \nu \rvert = \lambda$ can hold any amount past $\pm \gamma$, with the sign of $-(\phi_i + \nu)$, because $h$ is linear there. The sum of the $b_i(\nu)$ falls piecewise linearly in $\nu$, with knots at $-\phi_i \pm \lambda$. The multiplier is the root of that sum at one, or the end of the interval where the sum cannot reach one. At the lower end the assets with the smallest $\phi_i$ take the remainder of the budget, and at the upper end the assets with the largest $\phi_i$ take it.
When $N \gamma \leq 1$ the sum is at most one everywhere. An asset $k$ with the smallest $\phi_k$ then takes $1 - \sum_{i \neq k} b_i$, and every other asset holds at most $\gamma$. When $\max \boldsymbol{\phi} - \min \boldsymbol{\phi} > 2 \lambda$ the interval is empty, and the programme has no minimum.
Algorithm
- Compute the ends of the interval of the multiplier,
lo = -lambda - minimum(phi)andhi = lambda - maximum(phi). - When
lo > hi, the programme has no minimum. Return the split ofL1Optimum. - Find the multiplier
nuin[lo, hi]withhuber_multiplier. - Compute the coordinates
batnuwithhuber_coordinates. - Add the remainder of the budget to
bwithhuber_remainder!, in equal parts between tied assets, and returnb.
Fields
lambda: The weight of the $L_1$ penalty of the short-term sparse portfolio.
gamma: The soft-threshold width. The ratiolambda / gammais twice the weight of the quadratic coupling in Equation 13 of [95].
Constructors
HuberOptimum(; lambda::Real = 0.5, gamma::Real = 0.01) -> HuberOptimumKeywords correspond to the struct's fields, and the defaults come from [95].
Validation
lambda > 0,gamma > 0. ADomainErroris thrown otherwise.
Examples
julia> HuberOptimum()HuberOptimum lambda ┼ Float64: 0.5 gamma ┴ Float64: 0.01Related
References
- [95] Z.-R. Lai, P.-Y. Yang, L. Fang and X. Wu. Short-term sparse portfolio optimization based on alternating direction method of multipliers. Journal of Machine Learning Research 19, 1–28 (2018). Section 3.3.1, Equations 13, 17 to 20 and 22, and Section 4.1.
PortfolioOptimisers.AlternatingDirectionMethod — Type
struct AlternatingDirectionMethod{__T_lambda, __T_gamma, __T_eta, __T_iters, __T_tol} <: AbstractSparsePortfolioAlgorithmRuns the alternating direction iteration of the short-term sparse portfolio until its stopping rule holds.
Take this algorithm to reproduce the loop and the stopping rule of [95]. Its fixed point is the point that HuberOptimum finds in closed form, but the stop comes long before the iterate reaches that point. The stop reads the budget residual, which changes sign as the dual variable adapts, and the iteration meets tol = 1e-4 at one of those sign changes. The scaled projection of the stopped iterate is usually the fixed point's projection, but it can hold other assets. A tolerance that the sign changes never meet runs all iters iterations.
The tests measure these numbers from the uniform seed. On 0.02 .* randn(StableRNG(11), 40, 4), over the 36 windows of five rows, the stop comes after 359 to 4619 iterations and 2 to 27 sign changes. At the stop the iterate is up to about 0.67 from the fixed point in one coordinate, and it comes within $10^{-6}$ of the fixed point after 29461 to 104386 iterations. On 0.02 .* randn(StableRNG(1), 60, 4), rows 2 to 6 give two assets almost equal forecasts. At zeta = 500 the stopped iterate projects to about [0.46, 0, 0, 0.54], and the fixed point projects to [0, 0, 0, 1].
Mathematical definition
\[\begin{align} L(\boldsymbol{b}, \boldsymbol{g}, \rho) &= \langle \boldsymbol{b}, \boldsymbol{\phi} \rangle + \frac{a}{2} \lVert \boldsymbol{b} - \boldsymbol{g} \rVert_2^2 + \lambda \lVert \boldsymbol{g} \rVert_1 + \frac{\eta}{2} (\boldsymbol{1}^\intercal \boldsymbol{b} - 1)^2 + \rho (\boldsymbol{1}^\intercal \boldsymbol{b} - 1)\,, \\ \boldsymbol{b}^{(o+1)} &= \underset{\boldsymbol{b}}{\arg\min} \; L(\boldsymbol{b}, \boldsymbol{g}^{(o)}, \rho^{(o)}) = \left( a \mathbf{I} + \eta \boldsymbol{1} \boldsymbol{1}^\intercal \right)^{-1} \left( a \boldsymbol{g}^{(o)} + (\eta - \rho^{(o)}) \boldsymbol{1} - \boldsymbol{\phi} \right)\,, \\ \boldsymbol{g}^{(o+1)} &= \underset{\boldsymbol{g}}{\arg\min} \; L(\boldsymbol{b}^{(o+1)}, \boldsymbol{g}, \rho^{(o)}) = \operatorname{sign}(\boldsymbol{b}^{(o+1)}) \odot \max(\lvert \boldsymbol{b}^{(o+1)} \rvert - \gamma, 0)\,, \\ \rho^{(o+1)} &= \rho^{(o)} + \eta (\boldsymbol{1}^\intercal \boldsymbol{b}^{(o+1)} - 1)\,, \\ \left( a \mathbf{I} + \eta \boldsymbol{1} \boldsymbol{1}^\intercal \right)^{-1} \boldsymbol{v} &= \frac{\boldsymbol{v}}{a} - \frac{\eta \, \boldsymbol{1}^\intercal \boldsymbol{v}}{a (a + \eta N)} \boldsymbol{1}\,. \end{align}\]
Where:
- $L$: Augmented Lagrangian of the iteration.
- $\boldsymbol{b}$: Unscaled target of the short-term sparse portfolio step, the vector whose scaled projection is the next allocation.
- $\boldsymbol{g}$: Auxiliary vector that carries the $L_1$ penalty in place of the target.
- $\rho$: Dual variable of the budget constraint.
- $o$: Iteration index, counted from one.
- $\boldsymbol{\phi}$: Objective vector of the short-term sparse portfolio step, $-(1.1 \log \hat{\boldsymbol{x}} + \boldsymbol{1})$ for the Price Relative Forecast $\hat{\boldsymbol{x}}$. Its smallest entry is the largest forecast.
- $\lambda$: Penalty weight of the $L_1$ norm, positive.
- $\gamma$: Soft-threshold width, positive.
- $a$: Quadratic coupling $\lambda / \gamma$ of the target to the auxiliary vector.
- $\eta$: Weight of the penalty on the budget residual, and the step of the dual variable.
- $\mathbf{I}$: $N \times N$ identity matrix.
- $\boldsymbol{v}$: Any $N \times 1$ vector.
- $N$: Number of assets.
$L$ is equation (13) of [95], and the three updates are equations (29), (32) and (27) of [95]. The last line is the Sherman-Morrison identity. A fixed point of the updates has a zero budget residual, and it solves the programme of HuberOptimum.
Algorithm
- Seed
bandgat the held allocationw, andrhoat zero, as step 3 of Algorithm 1 of [95] does. Computea = lambda / gamma. - Compute the right-hand side
rhsof the update of $\boldsymbol{b}$ fromgandrho. - Compute
bfromrhswith the inverse in closed form, in $O(N)$ operations. - Compute
g, the soft threshold ofbatgamma. - Compute the budget residual
res = sum(b) - 1, and addeta * restorho. - When
abs(res) < tol, or afteritersiterations, returnb. Otherwise go back to step 2.
Fields
lambda: The weight of the $L_1$ penalty of the short-term sparse portfolio.
gamma: The soft-threshold width. The ratiolambda / gammais twice the weight of the quadratic coupling in Equation 13 of [95].
eta: The weight of the penalty on the budget residual, which is also the step of the dual variable.
iters: Maximum number of iterations.
tol: The convergence tolerance on the budget residual.
Constructors
AlternatingDirectionMethod(; lambda::Real = 0.5, gamma::Real = 0.01, eta::Real = 0.005, iters::Integer = 10_000, tol::Real = 1e-4) -> AlternatingDirectionMethodKeywords correspond to the struct's fields, and the defaults come from [95].
Validation
lambda > 0,gamma > 0,eta > 0,tol > 0. ADomainErroris thrown otherwise.iters >= 1. ADomainErroris thrown otherwise.
Examples
julia> AlternatingDirectionMethod()AlternatingDirectionMethod lambda ┼ Float64: 0.5 gamma ┼ Float64: 0.01 eta ┼ Float64: 0.005 iters ┼ Int64: 10000 tol ┴ Float64: 0.0001Related
References
- [95] Z.-R. Lai, P.-Y. Yang, L. Fang and X. Wu. Short-term sparse portfolio optimization based on alternating direction method of multipliers. Journal of Machine Learning Research 19, 1–28 (2018). Section 3.3.2, Equations 13, 27, 29 and 32, Algorithm 1 and Section 4.1.
PortfolioOptimisers.sparse_portfolio_iterate — Function
sparse_portfolio_iterate(alg::L1Optimum, phi::AbstractVector, w::AbstractVector)
sparse_portfolio_iterate(alg::HuberOptimum, phi::AbstractVector, w::AbstractVector)
sparse_portfolio_iterate(alg::AlternatingDirectionMethod, phi::AbstractVector, w::AbstractVector)Finds the unscaled target of a ShortTermSparsePortfolio step for the objective vector phi.
L1Optimum returns the optimum of the programme of [95]: it splits the whole budget in equal parts between the smallest entries of phi, which are the assets with the largest forecast. HuberOptimum returns the fixed point of the iteration of [95] in closed form, and the split of L1Optimum where its programme has no minimum. AlternatingDirectionMethod runs that iteration from the held allocation w, and it is the only method that reads w. The type docstrings state the formulas.
Returns
b::AbstractVector: The unscaled target. The two closed forms sum to one. The iteration sums to one withintolwhen it stops attol, and it can be further from one when it runs allitersiterations.
Related
References
- [95] Z.-R. Lai, P.-Y. Yang, L. Fang and X. Wu. Short-term sparse portfolio optimization based on alternating direction method of multipliers. Journal of Machine Learning Research 19, 1–28 (2018). Equations 12, 27, 29 and 32 and Algorithm 1.
References
- [95]
- Z.-R. Lai, P.-Y. Yang, L. Fang and X. Wu. Short-term sparse portfolio optimization based on alternating direction method of multipliers. Journal of Machine Learning Research 19, 1–28 (2018).