Keywords

1 Introduction

In this work we discuss the numerical solution of the portfolio selection problem. Our starting point is the classical Markowitz mean-variance framework, in which one aims at the construction of an investment portfolio that exposes investor to minimum risk providing him a fixed expected return. A common strategy to estimate Markowitz model parameters is to use historical data as predictive of the future behaviour of asset returns. This typically leads to ill-conditioned numerical problems. We then consider l 1 regularization techniques; the single-period regularized model was introduced in [3], where a l 1-penalty term is added to the objective function of the optimization problem at the core of the model. This has also nice financial interpretations, both in terms of transaction costs and control of short-positions. We then extend the regularized model to the multi-period case. Our model satisfies time consistency, a fundamental requirement in this framework. Different definitions of time consistency can be found in literature, either related to dynamic risk measures or investment policies [5]; this concept deals with the consistency over time of decisions taken with the support of evolving available information. We discuss the numerical solution in both cases. We develop iterative algorithms based on Bregman iteration method, that converts the constrained problem into a short sequence of unconstrained ones. The presence of the l 1-term makes the solution of the involved optimization sub-problem not trivial, thus we apply ad hoc methods to deal with non-smoothness [1].

In Sect. 2 we describe the regularized portfolio selection model; in Sect. 3 we describe Bregman iteration method.

2 Regularized Portfolio Selection Model

Let n be the number of traded assets. We assume self-financing investment strategies, both in the single and in the multi-period case. We start by describing the static mean-variance problem. We suppose that one unit of capital is available and define

$$\displaystyle \begin{aligned} \mathbf{w} = (w_{1},w_{2},\ldots,w_{n})^T \end{aligned}$$

the portfolio weight vector, where w i is the amount invested in the i-th security. We furthermore denote with

$$\displaystyle \begin{aligned} \mathbf{r} = (r_{1},r_{2},\ldots,r_{n})^T \end{aligned}$$

the vector of expected asset returns. Regularized portfolio selection is formulated as the following quadratic constrained optimization problem:

$$\displaystyle \begin{aligned} \begin{array}{l} \min_{\mathbf{w}} {\mathbf{w}}^T \varSigma\mathbf{w} + \tau \|\mathbf{w}\|{}_1\\ \mathrm{s.t.} \\ {\mathbf{w}}^T {\mathbf{1}}_n = 1,\\ {\mathbf{w}}^T \mathbf{r} = \rho \\ \end{array} \end{aligned}$$

where 1 n is the column vector of ones of dimension n, ρ is the fixed expected portfolio return, and Σ is the covariance matrix of returns. The first constraint is a budget constraint which establishes that all the available capital is invested. The second one fixes the expected return.

Let us now turn to the dynamic case and consider m dates, which define m − 1 periods of investment. Decisions are assumed at time t i, i = 1, …, m − 1; decision taken at time t i is kept in the period [t i, t i+1). Portfolio weights and asset returns are now stored in matrices \(W\in \Re ^{n\times m}, \; R \in \Re ^{n\times (m-1)}\), in which the i-th columns w i, r i contain, respectively, the weight vector at time t i and the expected return vector in the period [t i, t i+1). Regularized portfolio selection is formulated as the following constrained optimization problem:

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \min_W \sum_{i=1}^{m} \Bigl[ {\mathbf{w}}_i^T\varSigma_i{\mathbf{w}}_i + \tau \|{\mathbf{w}}_i\|{}_1 \Bigr] \\ &\displaystyle &\displaystyle \mathrm{s.t.} \\ &\displaystyle &\displaystyle {\mathbf{w}}_1^T {\mathbf{1}}_n = 1 {} \end{array} \end{aligned} $$
(1)
$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle {\mathbf{w}}_i^T {\mathbf{1}}_n = (1+r_{i-1})^T {\mathbf{w}}_{i-1}, \quad i = 2,\ldots,m {} \end{array} \end{aligned} $$
(2)
$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle {\mathbf{w}}_n^T {\mathbf{1}}_n = x_{\mathrm{term}} {} \end{array} \end{aligned} $$
(3)

where x term is the expected wealth provided by the overall investment and Σ i is the covariance matrix estimated in the i-th period. As in the one-period case, constraint (1) is the budget constraint, constraint (2) means that the investment strategy is self-financing, thus, at the end of each period the wealth is given by the revaluation of the previous one. Finally, constraint (3) fixes the investment target. We adopt a separable formulation for the risk measure, so, following [4], we show that our approach is time consistent.

3 Bregman Iteration for Portfolio Selection

Regularized portfolio selection can be in general formulated as the constrained nonlinear optimization problem:

$$\displaystyle \begin{aligned} \begin{array}{l} \min_{\mathbf{w}} E(\mathbf{w}) \\ \mathrm{s.t.} \\ A\mathbf{w} = \mathbf{b}, \end{array} \end{aligned} $$
(4)

where, defined M = m + 1, N = m ⋅ n, the functional \(E(\mathbf {w}): \Re ^N \longrightarrow \Re \) is strictly convex and non-smooth due to the presence of the l 1-penalty term and \( A \in \Re ^{M \times N}\) is the matrix form of the constraints and \( \mathbf {b} \in \Re ^M\). Bregman iteration can be used to reduce (4) in a short sequence of unconstrained problems by using the Bregman distance associated with E [2].

The Bregman distance associated with a proper convex functional E(w) at point v is defined as:

$$\displaystyle \begin{aligned} D_E^{\mathbf{p}}(\mathbf{w},\mathbf{v})=E(\mathbf{w})-E(\mathbf{v})- < \mathbf{p}, \mathbf{w}-\mathbf{v} >, \end{aligned}$$

where p ∈ ∂E(v) is a subgradient in the subdifferential of E at point v and < ., . >  denotes the canonical inner product in R N. First of all, the constrained problem (4) is converted into the unconstrained one:

$$\displaystyle \begin{aligned} \begin{array}{l} \min_{\mathbf{w}} E(\mathbf{w}) + \frac{\lambda}{2} \|A\mathbf{w} - \mathbf{b} \|{}_2^2 \end{array}\end{aligned} $$
(5)

for a fixed λ > 0. Then, at each Bregman iteration E(w) is replaced by the Bregman distance so a sub-problem in the form of (5) is solved according to the following iterative scheme:

$$\displaystyle \begin{aligned} \left \{ \begin{array}{l} {\mathbf{w}}_{k+1} = \mathrm{argmin}_{\mathbf{w}} D_E^{\mathbf{p_k}}(\mathbf{w}, {\mathbf{w}}_{k}) + \frac{\lambda}{2} \| A\mathbf{w} - \mathbf{b} \|{}_2^2,\\ {\mathbf{p}}_{k+1} = {\mathbf{p}}_{k}-\lambda A^T(A {\mathbf{w}}_{k+1} -b) \in \partial E( {\mathbf{w}}_{k+1}).\\ \end{array} \right .\end{aligned} $$
(6)

Under suitable hypotheses the convergence of the sequence {w k} to the solution of the constrained problem (4) is guaranteed in a finite number of steps [6]. Since there is generally no explicit expression for the solution of the sub-minimization problem involved in (6), at each iteration the solution is computed inexactly using an iterative solver. At this purpose, we focus on first order methods, which are gradient-based that converge rather slowly; however, for large problem dimensions, usually a fast lower-precision solution is favoured. In particular, we use the Fast Proximal Gradient method with backtracking stepsize rule (FISTA) [1], an accelerated variant of Forward Backward algorithm, suitable for minimizing convex objective functions given by summation of smooth and non-smooth terms. We test our algorithms on real market data, and validate our approach observing the out-of-sample performances of optimal portfolios.