Generalized distance to a simplex and a new geometrical method for portfolio optimization

Risk aversion plays a significant and central role in investors' decisions in the process of developing a portfolio. In this framework of portfolio optimization we determine the portfolio that possesses the minimal risk by using a new geometrical method. For this purpose, we elaborate an algorithm that enables us to compute any generalized Euclidean distance to a standard simplex. With this new approach, we are able to treat the case of portfolio optimization without short-selling in its entirety, and we also recover in geometrical terms the well-known results on portfolio optimization with allowed short-selling. Then, we apply our results in order to determine which convex combination of the CAC 40 stocks possesses the lowest risk: not only we get a very low risk compared to the index, but we also get a return rate that is almost three times better than the one of the index.

1 Introduction and aims of the article

Framework
The paper [M52] published by Harry Markowitz in 1952 completely changed the methods of portfolio management and gave birth to the so-called "Modern Portfolio Theory", thanks to which its author earned the Nobel Prize in Economics in 1990. Since his works and the paper [S63] of Sharpe, this theme centralizes a lot of interest and many developments have been written in this domain. Let us recall some recent and important works to which our article is linked.
In [DJDY08], Jón Daníelsson, Bjørn N. Jorgensen, Casper G. de Vries and Xiaoguang Yang study the portfolio allocation under the probabilistic VaR constraint and obtain remarkable topological results: the set of feasible portfolios is not always connected nor convex, and the number of local optima increases in an exponential way with the number of states. They propose a solution to reduce computational complexity due to this exponential increase.
In [FS12], Claudio Fontana and Martin Schweizer give a simple approach to mean-variance portfolio problems: they change the problems' parametrisation from trading strategies to final positions. In this way they are able to solve many quadratic optimisation problems by using orthogonality techniques in Hilbert spaces and providing explicit formulas.
In their important article [BCGD18], Hanene Ben Salah, Mohamed Chaouch, Ali Gannoun and Christian De Peretti (see also the thesis [B15]) define a new portfolio optimization model in which the risks are measured thanks to conditional variance or semivariance. They use returns prediction obtained by nonparametric univariate methods to make a dynamical portfolio selection and get better performance.
In [PR19], Sarah Perrin and Thierry Roncalli show how four algorithms of optimization (the coordinate descent, the alternating direction method of multipliers, the proximal gradient method and the Dykstra's algorithm) can be used to solve problems of portfolio allocation.
In [BIPS20], Taras Bodnar, Dmytro Ivasiuk, Nestor Parolya and Wolfgang Schmid make an interesting work about the portfolio choice problem for power and logarithmic utilities: they compute the portfolio weights for these utility functions assuming that the portfolio returns follow an approximate log-normal distribution, as suggested in [B00]. It is also noticeable that their optimal portfolios belong to the set of mean-variance feasible portfolios.

Aims and organization of the paper
The three aims of this article are the following: -give a new geometrical algorithm (Algorithm 1) to compute any generalized distance to a simplex, -determine, by making use of this algorithm, a portfolio with minimal variance, -apply this technique to the CAC 40 stocks, and get a portfolio with return rate that is almost three times better than the one of the index.
After having briefly explained the notations in Section 1, we expose in Section 2 the portfolio optimization problem and prove by compactness and con-vexity arguments that it possesses a unique solution. Then, in Section 3, we solve the problem in the case where short-selling is allowed. For this, we recall the classical method, and we give our very simple geometrical method. Section 4 is the heart of the article: in this section, we solve the portfolio optimization problem in the case where short-selling is not allowed. For this purpose, we give a new geometrical algorithm to compute the distance from a point to a standard simplex, which can be used for every Euclidean distance. We can eventually apply this algorithm to the example of the CAC 40 stocks and determine the portfolio with the lowest risk. This portfolio also has the property of being almost three times more efficient than the underlying index. This is done in Section 5.

Notations
We consider n stocks S 1 , S 2 , . . . , S n and denote by X 1 , X 2 , . . . , X n the random variables that represent their return rate (for example, daily, monthly or yearly).
Matrix C is the covariance matrix of X 1 , X 2 , . . . , X n , and X is a random vector.
Definition 1. We call portfolio (with allowed short-selling) every linear com- The return rate of the portfolio is the linear combination R If we don't allow short-selling, then every x i must be nonnegative, and in that case the linear combination is a convex combination. Moreover, The following proposition is immediate.
Proposition 2. The matrix C has the two following properties. In all the following, we assume that C is symmetric definite positive: this is always true in practise.
Let us denote by H the affine hyperplane of R n with equation n j=1 x j = 1, and by K the standard (n − 1)−simplex (also called standard simplex of dimension n − 1), i.e.
The simplex K is a Haussdorff compact subset of R n that is contained in the hyperplane H. For example, if n = 2, H is the line of equation x + y = 1 in the usual plane, and the 1−standard simplex K is the segment [(0, 1), (1, 0)] of this line.

Existence and uniqueness of the solution
Minimizing the variance of the portfolio is equivalent to finding the minimum on K of the quadratic form Let us consider the scalar product (x, y) → x, y := t xCy and the Euclidean norm The aim is to determine the point of K that realizes the minimal distance to K from the origin point in the sense of · . As K is a Haussdorff compact subset, and as f is continuous, we know that this minimum does exist. We will prove that it is also unique. For this, the convexity plays a central role (see for example [R17]).
Proposition 3. The map f is strictly convex.
Proof. For every x, y ∈ R n and for every λ ∈ [0, 1], we have which is nonnegative, as C is positive. Moreover, if x = y, this quantity is positive as C is definite positive.
Proposition 4. Let K be a convex domain and f : K → R a convex map. Then, (ii) if f is strictly convex, then f possesses at most one minimum.
Proof. (i) Let x 0 be a local minimum of f in K. Let us assume by contradiction that it is not global: there exists y ∈ K such that f (y) < f (x 0 ). For every t ∈]0, 1[, let us set y t = ty + (1 − t)x 0 . Then y t belongs to K, and for t small enough, (ii) Let us assume by contradiction that f possesses a least two distinct minima , which is a contradiction to the fact that x 1 is a minimum.
As a consequence of Proposition 4, the quadratic form f possesses exactly one minimum on f , and his minimum is global.

Minimisation of f on H
In this section, we give two methods to compute the portfolio that possesses the lowest risk: the classical one, and our geometrical approach.
Let us denote by E = (e 1 , . . . , e n ) the canonical basis of R n . A basis of the vector hyperplane that directs H is B = (e 1 − e 2 , e 1 − e 3 , . . . , e 1 − e n ). Moreover, x j e j ∈ R n , x belongs to H if and only if n j=1 x j = 1.
Let is denote by u the vector u = n j=1 e j , which is orthogonal to the hyperplane H, and let us set

Minimisation of f on H by the classical method
Here we briefly recall the classical method to compute the portfolio that possesses the lowest risk. Several sources, such as [N09], [M10] and [PP14], provide a clear presentation of these well-known tools.
Proposition 5. The unique solution x 0 that minimises the map f on H is the Proof. According to Lagrange's multipliers theorem, there exists λ ∈ R such that ∇f (x 0 ) = λ∇h(x 0 ). Here we have ∇f (x) = 2Cx and ∇h(x) = u, thus 2Cx 0 = λu, i.e. x 0 = λ 2 C −1 u. As t x 0 u = 1, we get Example 1. For n = 2, the formula is very simple: by setting and

Minimisation of f on H by the geometrical approach
Here we recover the classical results on the portfolio with minimal variance with allowed short-selling by making use of an Euclidean interpretation. This portfolio is P x0 , where x 0 is the orthogonal projection onto H of the origin point.
Let us define the (n, n)−matrix Proposition 6. The unique solution x 0 that minimises f on H is the vector whose coordinates in E are given by the last column of the inverse of matrix A.
Proof. For every x in H, x is the orthogonal projection onto H of the origin point if and only if x is orthogonal to H, that is to say, for every 4 Distance to K from a point of R n In this section, we will solve the problem of portfolio optimization without shortselling, by giving an explicit and calculable solution that doesn't seem to appear in the literature. Let us set Proposition 7. The orthogonal projection of a onto H is the vector whose nonzero coordinates in E are given by Proof. For every x = n j=1 x j e j ∈ R n , x is the orthogonal projection of a onto H if and only if the three following conditions hold (i) for every j ∈ J, x j = 0, n j=1 x j = 1,

4.2
The algorithm for computing the generalized distance to K from a point of R n We now propose a recursive algorithm to compute the point x 0 realizing the distance to K from a point a ∈ R n . In his article [C16], L. Condat gave a new and fast algorithm to project a vector onto a simplex. However, his algorithm was made only for the usual Euclidean distance. Our algorithm can be used for every Euclidean distance. The reader can also have a look at the paper [CY11] about the projection onto a simplex. If K is a 1−simplex (i.e. K has exactly 2 vertices) Return the vertex that is the closest to x Else Determine the hyperface K of K that is the closest to x Compute y the orthogonal projection of x onto H (the affine subspace defined by K ) Apply recursively the algorithm to (y,K ) Proposition 8. Algorithm 1 ends.
Proof. This is straightforward since at each step of the algorithm the dimension of the simplex decreases of one unit.
Lemma 1. If x belongs to H \ K, then the distance from x to K is realized in a point of the frontier of K.
Proof. Let us proceed by contradiction by assuming that the distance from x to K is realized in a point z in • K. Let us denote by y the intersection of the line (x, z) with an hyperface of K crossed by this line. Then, by Minkowski, we get x − z = x − y + y − z > x − y , which is absurd since z realizes the minimal distance from x to K.
As a consequence, if x belongs to H \ K, then the distance from x to K is the distance from x to the hyperface of K that is the closest to x.
Proof. Let us prove by induction on the dimension of K that the algorithm provides us x 0 ∈ K such that d(a, K) = − − → ax 0 . • If K has dimension 1, the result is clear.
• Now assume that the algorithm is correct for every (n − 1)−simplex. Let us consider K a n−simplex (with n ≥ 2), and prove that the algorithm is correct for K. Let x be the orthogonal projection of a onto H.
-If x belongs to K, then x is the solution, and the algorithm is correct.
-If x does not belong to K, as n ≥ 2, we consider the simplex K defined above, the affine subspace H and y the orthogonal projection of x onto H . By induction hypothesis applied to y and the (n − 1)−simplex K , the algorithm provides us x 0 ∈ K such that d(y, K ) = − − → yx 0 . In particular, x 0 belongs to K. Let us now prove that d(a, K) = − − → ax 0 . According to the Pythagorean theorem, as − → ax is orthogonal to H, we have thanks to Lemma 1. Moreover, as − → xy is orthogonal to H , we have ax 0 and the algorithm is correct for K.
Remark 1. Let x be in H \ K. Then the hyperface of K that is the closest to x is not necessarily the hyperface of K obtained by suppressing the (or one) vertex of K that is the furthest of x.
Proof. Let us consider the following example: let K be the 2−simplex in the hyperplane {x + y + z = 1} of R 3 . Let us set   , and the distances from x to these edges are δ 1 0.039, δ 2 0.048, δ 3 0.0002. So we have d 2 < d 3 < d 1 but δ 3 < δ 1 < δ 2 . Here, the vertex of K that is the furthest of x is e 1 , but the distance from x to K is realized in a point of the edge defined by {e 1 , e 2 }.

Minimisation of f on K
Now that we have the algorithm to compute the generalized distance to a standard simplex, it is easy to find the solution that minimises f on K: the portfolio that possesses the lowest risk is P x0 , where x 0 is the point of K that realizes the distance from the origin point to K, i.e. d(0, K) = x 0 .

Application to portfolio optimization
Here we determine the portfolio with lowest risk: we determine the convex combination of CAC 40 stocks 1 for which the variance is minimal 2 . We use the mean and the standard deviation of monthly 3 variation.

Portfolio optimization from 2007-04-23 to 2020-07-21
Here we consider the period from 2007-04-23 to 2020-07-21, that is to say we start from the highest point of CAC 40 index. Table 1 gives the mean and the standard deviation of stocks' return rates that appear in the results. By using Algorithm 1, we determine the portfolio with allowed short-selling that possesses the lowest risk: this linear combination is given by Table 2. The mean of its monthly variation is 0.44% and its standard-deviation 4.35%. We observe here that the linear combination obtained is a convex combination, which means that this portfolio is also the portfolio without short-selling that possesses the lowest risk. In geometrical terms, this means that the orthogonal projection of the origin point onto the hyperplane H already belongs to the simplex K.    Table 3 and Figure 2 give the yearly return rate of this portfolio. We notice that the portfolio is more profitable and more regular than the index: indeed, its mean is 7.41% and its standard deviation 11.93%, whereas for the index, the mean is 1.12% and the standard deviation 19.61%. Moreover, the return rate of the portfolio is almost never negative.  Table 4 and Figure 3 give the final value of the portfolio compared with the CAC 40 index and show the monthly variations of their value.  Here we consider the period from 2009-01-19 to 2020-07-21, that is to say we start from the lowest point of CAC 40 index. As in previous section, Table 5 gives the mean and the standard deviation of stocks' return rates that appear in the results.
The portfolio with allowed short-selling that possesses the lowest risk is given by the following linear combination in Table 6. The mean of its monthly variation is 0.76% and its standard-deviation 4.17%.
Now, according to Algorithm 1, the portfolio without short-selling that possesses the lowest risk is given by the following convex combination in Table 7. The mean of its monthly variation is 0.87% and its standard-deviation 4.22%.
Let us note that some stocks that were in the linear combination of the portfolio with allowed short-selling now disappear: the geometric explanation of this fact immediately comes from Lemma 1. The yearly return rate is given by Table 8. Here again, as shown by Table 8 and Figure 4, the portfolio is more profitable and more regular than the index: its mean is 13.27% and its standard deviation 11.99%, whereas for the index, the mean is 5.94% and the standard deviation 16.78%. Moreover, the return rate of the portfolio is negative for only two years, and the absolute value of these negative return rates very small.

Appendix -Python programs
Here we give a possible way to program Algorithm 1 in Python as well as the subroutine used to compute an orthogonal projection.
The function orth_proj(c,a,J) computes an orthogonal projection, where c is the covariance matrix, a is the point of which we want to compute the orthogonal projection, -J is the list of indices of p vectors of E that define the affine subspace onto which we want to project a. def orth_proj(c,a,J): p=len(J); n=len(c); i0=J[0]; L=list(set(range(n))-set(J)) #L is the complementary of J #Matrix The function mini_dist_fct(c,a) finds the point that realizes the minimal distance from a to the standard (n − 1)−simplex and also returns the square of this distance: it is a possible version of Algorithm 1. def mini_dist_fct(c,a): ]-a)] #Case 3: the orthogonal projection does not belong to the #simplex and the simplex has dimension greater than 1 else: #Looking for the hyperface that is the closest to x delta=mini_dist(c,x,J) dico[str(set(J))+str(x)]=delta x=delta [0] return [x,phi(x-a,x-a)] #Computing the point realizing the minimal distance return mini_dist(c,a,list(range(n)))