Abstract

This paper presents a pivoting-based method for solving convex quadratic programming and then shows how to use it together with a parameter technique to solve mean-variance portfolio selection problems.

1. Introduction

There are a variety of algorithms for solving convex quadratic programming (QP). The most well-known one is active set method [1,2]. However this method is difficult to learn for many people due to its operational manner. In this paper we present a pivoting-based method for solving convex QP which is efficient for calculating and concise for understanding.

The Karush-Kuhn-Tucker conditions (KKT conditions) of QP is a system of (in) equalities where all the expressions are linear equalities or inequalities except for complementarity conditions. Like Wolfe’s method [3] we solve the linear part by a kind of pivoting operation while maintaining the complementarity conditions in the computational process. However the system computed by our method has a much smaller size because many variables are deleted from the KKT conditions.

In 1952 Harry Markowitz published the milestone paper “Portfolio Selection” in which the portfolio selection problem is formulated as a convex quadratic program with nonnegative variables [4,5]. It is nearly 60 years. However most people still think the model is difficult to solve and few people conduct their investment activities by calculating efficient portfolios for references. We see that every investments textbooks have a figure to show portfolios which are formed by two assets with different correlation coefficients. But we can hardly see a book which has an example to show portfolios formed by three or more assets in the case of no short sale. We will present a pivoting-based algorithm together with a parameter technique to solve Markowitz’s portfolio selection model in a very simple form. The most important advantage of our parameter technique is that it can continuously obtain minimal risk portfolios at different levels of return in linear time after a portfolio is established by the pivoting algorithm.

The rest sections of this paper are organized as follows. In Section 2, we introduce a pivoting-based algorithm for solving the system of linear inequalities and the parameter technique for generating new basic solutions which are associated with different right-hand side terms. In Section 3, we introduce basic concepts and operations for solving the convex QP. In Section 4, we discuss how to solve Markowitz’s mean-variance portfolio selection model. For brevity, relative theorems and proofs as well as tedious reasoning processes are omitted. For details, the reader refers to [6-8].

2. The System of Linear Inequalities

Consider a system of linear inequalities in the form:

(2.1)

where, and b_i is a scalar,.

In our algorithm, the following concepts are employed.

A set of maximum linearly independent vectors of a₁, a₂, , a_m is called a basis of (2.1). Vectors in the basis are called basic otherwise called nonbasic. The equalities and inequalities associated with basic vectors are called basic otherwise called nonbasic. The system of basic (in) equalities is called a basic system and whose solution set is called a basic cone. The solution to the system of equations that are corresponding to basic (in) equalities, i.e., the vertex of the basic cone, is called basic solution.

Geometrically, our algorithm begins with a basic cone whose vertex is denoted by. If lies on the hyper-planes determined by every equalities and lies in the half-spaces determined by every inequalities of (2.1), it is a solution to the entire system. Otherwise there exists an inequality (or equality) such as so that which is called a violating inequality against. If the intersection of the half-space and the basic cone is empty, there is no solution for (2.1). Otherwise is projected onto the boundary of the half-space where replaces a basic inequality to constitute a new basic cone. Then the same process is repeated.

Algebraically, a nonbasic (in) equality replacing a basic inequality is accomplished by the following pivoting operation.

Given a basis of (2.1), let I₀, I₁, I₂ and I₃ be the index sets for basic equalities, basic inequalities, nonbasic inequalities and nonbasic equalities respectively. Let be the basic solution, i.e., ,. Suppose that

(2.2)

If w_rs ¹ 0 for an r Î I₃ÈI₂ and an s Î I₁, from the rth expression of (2.2) we have

(2.3)

Substitute it into the other expressions of (2.2) to yield

(2.4)

Now, we have a new basic cone whose index set is and the associated basic solution is denoted by. Multiply both sides of (2.4) by on the right to have

Multiply both sides of (2.2) by to have

Therefore

Rewrite the above expression as

and let, , to have

.

In the same way, from (2.3) we have

or

where.

The above operational process is called a pivoting (operation) and w_rs is called pivot (element). The row of w_rs is called pivot row and the column of w_rs is called pivot column. We say a_r enters and a_s leaves the basis and the exchange of these two vectors is denoted by a_r ↔ a_s. The process is simply shown by Tables 1 and 2.

Where

For Table 1, is called the deviation of a_i or the associated (in-) equality with respect to. If ; then is a solution to system (2.1). If for some r Î I₂, is called

violating inequality against and is called the distance from to.

The computational steps for the system of linear inequalities are as follows.

Algorithm 2.1. Pivoting algorithm for system (2.1).

Step 1. Construct initial table.

If (2.1) has an inequality in the form of, is an initial basic inequality; otherwise introduce into (2.1) and let be the initial basic inequality, i = 1, 2, , n. Where M is a number large enough, is called artificial inequality and whose coefficient vector is called artificial vector. The initial basic solution is where

or -M, i = 1, 2, , n. The initial basic vector is e_i which is the ith row of the identity matrix of order n,  i = 1, 2, , n. Other (in) equalities of (2.1) and their coefficient vectors are nonbasic whose deviation with respect to is. Thus we have an initial table as shown by Table 1.

Step 2. Preprocessing.

Let I₃ be the index set of equalities, i.e., I₃ = {1, , l}.

1) If I₃ = Æ, go to step 3. Otherwise, for an rÎI₃ if the deviation σ_r of a_r is negative, positive or zero, go to 2), 3) and 4) respectively.

2) If there is no positive element in the row of a_r that is corresponding to the basic inequality, (2.1) has no solution; otherwise carry out a pivoting on one of the positive elements, let and return to 1).

3) If there is no negative element in the row of a_r that is corresponding to the basic inequality, (2.1) has no solution, otherwise carry out a pivoting on one of the negative elements, let and return to 1).

4) If all of the elements in the row of a_r that are corresponding to basic inequalities are zeros, let and return to 1); otherwise carry out a pivoting on one of the non-zero elements, let and return to 1).

Step 3. Main iterations.

1) If all of the deviations of non-basic vectors are nonnegative, the current basic solution is a solution to (2.1). Otherwise 2) select a non-basic vector with negative deviation to enter the basis. If there is no positive element in the row of entering vector that is corresponding to the basic inequality, (2.1) has no solution, otherwise carry out a pivoting on one of the positive elements and return to 1).

Note that step 1 of Algorithm 2.1 is just a simplified statement for constructing the initial table. In fact, if (2.1) has no inequality but has for a finite u_i, can serve as an initial basic inequality and no need to introduce the artificial.

From steps 2 and 3 of Algorithm 2.1 we see that basic equalities never leave the basic system. Because if (2.1) has a solution, it must satisfy all the equalities. Therefore, once a non-basic equality enters the basic system, the corresponding column can be eliminated.

Sometimes, a system of inequalities has inequalities in the form of, especially, which are formally written as and in our method. Let be the basic solution, then deviations of a_i and -a_i are and respectively and with a sum of. Since a_i and -a_i are linearly dependent, they cannot be basic simultaneously. If one of them is basic, the deviation of the other one is, hence can be ignored. If both of a_i and -a_i are non-basic, they can share one row in the table since the coefficients in the expressions of a_i and -a_i in terms of basic vectors have reversed signs.

It should be noted that even though the basic solution is not explicitly presented in the table, it can be easily obtained from the table. Let be the basic solution which is obtained as follows. If x_i ³ l_i or -M is basic, or -M; otherwise equals to the deviation of this inequality plus l_i or -M. Or if is basic,; otherwise equals to u_i minus the deviation of.

There are many rules for selecting a vector to enter or leave the basis. We will give several ones which are used in the main iterations stage.

For a given basis of (2.1) let I₀, I₁ and I₂ be index sets for basic equalities, basic inequalities and non-basic inequalities respectively. Let be the current basic solution and

.

Rule 1. (The smallest deviation rule). Among all the non-basic vectors with negative deviations, select a vector a_r having the smallest deviation to enter the basis. That is if, then a_r enters the basis.

Rule 2. (The largest distance rule). Among all the non-basic vectors with negative deviations, select a vector a_r whose associated inequality is farthest away from the current basic solution to enter the basis. That is if, then a_r enters the basis.

Rule 3. (Rule of the farthest distance along an edge). Among all the non-basic vectors with negative deviations, select a vector a_r whose associated inequality is farthest away from the current basic solution along an edge of the basic cone to enter the basis. That is if = for an sÎI₁, then a_r enters the basis.

Rule 4. (The smallest index rule). Among all the nonbasic vectors with negative deviations, select a vector a_r having the smallest index to enter the basis; and among all the basic vectors to leave the basis, select a vector a_s having the smallest index to leave the basis. That is if, then a_r enters the basis; and if , then a_s leaves the basis.

Like Bland’s anti-cycling rule [9], it can be proved that when the smallest index rule is used to solve system (2.1), cycling doesn’t occur.

Now let us consider the parameter technique by which a new basic solution can be obtained from the current table by changing the right-hand side terms of some basic (in) equalities.

For a basis of (2.1), let I_B and I_N denote the index sets of basic and nonbasic vectors respectively and be the basic solution. Suppose

.

Multiply both sides by, since a_j = b_j, j Î I_B, to have

.

Therefore the deviation of the nonbasic a_i is

.

If b_j is changed to b_j + d_j, j Î I_B, the deviation of a_i becomes

(2.5)

The above operation is denoted by, j Î I_B.

Usually we just change the right-hand side of one basic (in) equality such as changing b_s to b_s + D for an s Î I_B. Then the deviation of a_i becomes

(2.6)

It indicates that when the right-hand side of a basic (in) equality is increased by D, deviations of nonbasic vectors with respect to the new basic solution can be obtained by multiplying the column of this basic (in) equality by D, and then add it to the last column (the deviation column). We will use to denote such an operation which gives the result (2.6).

3. Convex Quadratic Programming

3.1. Fundamental Concepts and Algorithm

Consider quadratic programming in this form:

(3.1)

where, is positive semidefinite, , , b_i and l_i are real numbers.

Let λ_i be the Lagrange multiplier associated with or, m_i be the Lagrange multiplier associated with, and e_i be the ith row of the identity matrix of order n. The KKT conditions for (3.1) are as follows.

,

,

,

,

Since

eliminate all the m_i from above KKT conditions to have

(3.2)

We will solve the linear part of (3.2) by Algorithm 2.1 while maintaining all of the complementarity conditions.

(3.2) has n + m variables where λ₁, λ₂, , λ_l are free. In order to initiate the computation, we introduce artificial inequalities

into (3.2). The coefficient vectors of first n + m (in) equalities of (3.2) are

,

and the coefficient vectors of last n + m inequalities are denoted by e_i which is the ith row of the identity matrix of order n + m, i = 1, 2, , n + m.

In system (3.2),

and,

and

are called complementary inequalities, and their coefficient vectors are called complementary vectors in which

are called Lagrange vectors and

are called constraint vectors, and the associated inequalities are called Lagrange inequalities and constraint (in) equalities respectively.

According to the definition of basic solution of the system of linear inequalities, if one of the complementary inequalities is basic, the corresponding complementarity condition is satisfied. Hence we will keep one of them basic and the other one nonbasic in the computational process.

The initial basic system for solving (3.2) is

,

i.e., e₁, , e_n, e_n+1, , e_n+m are initial basic vectors, and

is initial basic solution; h_i and a_i are initial nonbasic vectors with deviations

,

and

,

.

The representation of nonbasic vectors in terms of basic ones and their deviations are given in Table 3.

Since a₁, , a_l are coefficient vectors of equalities, we first put them into the basis as many as possible. Without loss of generality, suppose that a₁, , a_l are

linearly independent and suppose l pivoting operations can be carried out along the diagonal of the sub-matrix

.

In order to maintain the complementarity conditions, another l pivoting operations are carried out along the diagonal of

which translate the l basic artificial vectors out of the basis. The above 2l pivoting operations are called preprocessing. Since the basic solution must satisfy every equality constraints, once an equality enters the basic system, it is never selected to leave the basic system. For this reason, the columns of basic equalities and the associated rows of artificial inequalities can be deleted from the table. It implies that the upper bound M of the artificial variable may be any number. For convenience of computation, we always take M = 0.

The computational process following the preprocessing is called main iterations where each table is called general (pivoting) table, as shown by Table 4.

Where h_N and h_B are a partition of the Lagrange vectors, e_n+N and e_n+B are a partition of the Lagrange vectors, e_N and e_B as well as a_N and a_B are partitions of the constraint vectors and respectively, and s_h, s_λ, s_e, s_a in the last column are vectors formed by deviations of the corresponding nonbasic vectors.

We say the principal sub-matrix associated with nonbasic Lagrange vectors and basic constraint vectors to be Lagrange matrix and denote it by L, and say the principal sub-matrix associated with nonbasic constraint vectors and basic Lagrange vectors to be constraint matrix and denote it by G. For the initial table, L = H and G = O; for Table 4,

and.

It can be proved that both Lagrange matrix and constraint matrix are positive semi-definite when the Hessian matrix H of (3.1) is positive semi-definite. A positive semi-definite matrix has the property that if the ith diagonal entry is zero, then all the entries in the ith row and in the ith column are zeros.

Main iterations involve two kinds of operations. One is called principal pivoting which is carried out on a positive diagonal element of the table. The other one is called double pivoting which is carried out on a pair of symmetric off-diagonal elements successively while the diagonal element is zero. The 2l pivoting operations in the preprocessing stage are l double pivoting operations.

The basic solution associated with Table 4 is

.

Besides, we have and. Where l_B and l_N are vectors formed by the right-hand side terms of basic and nonbasic, λ_B and λ_N are vectors formed by basic and nonbasic multipliers of λ₁, λ₂, , λ_m, m_B and m_N are vectors formed by basic and nonbasic multipliers of μ₁, μ₂, , μ_n respectively.

Computational steps for the convex QP are as follows.

Algorithm 3.1. Computational steps for (3.2).

Step 1. Initial step.

Let

be the initial basic system and construct initial table given by Table 3.

Step 2. Preprocessing.

For i = 1, 2, , l, when the deviation of a_i is less than, greater than, or equal to 0, go to 1), 2) and 3) respectively.

1) If there is no positive elements in the row of a_i that are corresponding to basic inequalities, there is no feasible solution, stop; otherwise carry out a pivoting on one of the positive elements and then carry out a pivoting on the symmetric element.

2) If there is no negative elements in the row of a_i that are corresponding to basic inequalities, there is no feasible solution, stop; otherwise carry out a pivoting on one of the negative elements and then carry out a pivoting on the symmetric element.

3) If all the elements in the row of a_i that are corresponding to basic inequalities are zero, delete the row of a_i and then delete the column of e_n+i; otherwise carry out a pivoting on one of the nonzero elements and then carry out a pivoting on the symmetric element.

Step 3. Main iterations.

1) If all the deviations of nonbasic vectors (except for nonbasic Lagrange vectors e_n+1, , e_n+l that are corresponding to equality constraints) are non-negative, the current basic solution is the solution to (3.2), stop; otherwise select a nonbasic vector with negative deviation to enter the basis.

2) If there is no positive element in the row of the entering vector that is corresponding to the basic inequality, (3.2) has no solution, stop. Otherwise 3) if the diagonal element in the row of the entering vector is positive, carry out a pivoting on that diagonal element, return to 1); otherwise carry out a pivoting on the largest off-diagonal element in the row of the entering vector, and then carry out a pivoting on the symmetric element, and return to 1).

We will prove that the smallest index rule can prevent cycling even though it may involve more pivoting operations than the smallest deviation rule does. Here each pair of complementary vectors has the same index. For example, h_i and e_i have index i for i = 1, 2, , n, and a_i and e_n+i have index n + i for i = 1, 2, , m.

If cycling occurs, some vectors would enter and leave the basis repeatedly. Let s be the largest index of such vectors and consider two tables in the computational process. In one table the sth Lagrange vector enters and the sth constraint vector leaves the basis, and in the other table just reverse. Let P and Q be the principal sub-matrices associated with complementary nonbasic vectors of these two tables, and s_P and s_Q be deviations associated with P and Q respectively. Then, and

where Q can be partitioned into a 2 ´ 2 matrix as shown in Table 4 or positive definite. It contradicts the assumption that the components of s_P and s_Q with index s are negative and other components are nonnegative.

3.2. Convex QP with Upper Bounded Variables

Now let us consider the quadratic programming where variables are bounded from above:

(3.3)

Let

and let I₁ and I₂ be a partition of {1, , n}, i.e., I₁ È I₂ = {1, , n} and I₁ Ç I₂ = Æ, but empty I₁ or I₂ is allowed. It can be verified that if is a solution to the system

(3.4)

and every components of satisfy and, then is the optimal solution for (3.3).

The solution of (3.4) is as follows.

Firstly, let I₁ = {1, 2, , n} and I₂ = Æ, i.e., ignoring all the upper bounds u_i, to solve (3.4) where the first two steps of Algorithm 3.1 are applied. In the following computational process we will make the basic solution satisfy not only but also. That is we should make deviations of both e_i and -e_i non-negative. In other words, if the deviation of e_i or -e_i is negative, then it is a candidate to enter the basis.

If -e_i is entering the basis but it does not appear in the table, we change the table as follows. Replace the deviation σ_i of e_i with u_i - l_i - σ_i, reverse signs of other entries in the row of e_i, and then substitute -e_i for e_i; reverse signs of entries in the column of h_i and then substitute -h_i for h_i. The above operation is called a vector substitution for e_i. It amounts to replacing the nonbasic with and replacing the basic with. Similarly, if e_i is entering the basis but it does not appear in the table, we update the table by conducting a vector substitution for -e_i.

Another problem in solving (3.4) is that when a Lagrange vector h_i, -h_i or e_n+i is entering the basis, all the entries in this row are non-positive. In this situation, the change of the table is stated in the following 1) and 2).

1) Suppose that the Lagrange vector h_i is entering the basis but all the entries in this row are non-positive. In this case we conduct a vector substitution for h_i, i.e., reverse signs of all the entries in the row of h_i and then substitute -h_i for h_i; reverse signs of entries in the column of e_i and then substitute -e_i for e_i. It amounts to replacing the nonbasic with and replacing the basic with. The associated equalities of the last two inequalities are and, therefore the change of the right-hand side of is u_i - l_i. Considering signs of all the entries in the column of -e_i had been reversed, by (2.6) we multiply the column of -e_i by l_i - u_i, and then add it to the deviation column. Similarly, if -h_i is entering the basis but all the entries in this row are non-positive, we conduct a vector substitution for -h_i

2) Suppose that the Lagrange vector e_n+i (i = l + 1, , m) is entering the basis but all the entries in this row are non-positive. We see that e_n+i is a n + m dimensional unit vector with 1 at the (n + i) th position, h_i and -h_i are n + m dimensional vector whose last m components are not all zeros, and the last m components of constraint vectors are zeros. It implies that the expression of e_n+i in terms of basic vectors must contain h_j or -h_j. Suppose that w_ij is a negative off-diagonal entry in the row of e_n+i and in the column of (= h_j or -h_j). We conduct a vector substitution for e_n+i in this way: reverse signs of entries in the column of and then substitute for; replace the deviation s_j of (= e_j or -e_j) with u_j - l_j - s_j, reverse signs of other entries in the row of, and then substitute for. This substitution transforms w_ij into a positive number so that a regular pivoting e_n+i ↔ can be carried out.

Now let us give the algorithm for solving (3.3). In this algorithm, the non-basic vectors include not only those listed in the table but also those that are not listed in the table where = e_i or -e_i and = h_i or -h_i.

Algorithm 3.2. Computational steps for (3.4).

Step 1. Initial step, see step 1 of Algorithm.3.1.

Step 2. Preprocessing, see step 2 of Algorithm 3.1.

Step 3. Main iterations.

1) If all the deviations of non-basic vectors except for e_n+1, , e_n+l are non-negative, the current basic solution is optimal for (3.3), stop. Otherwise

2) select a non-basic vector with negative deviation to enter the basis. If the entering vector is a_i, , or e_n+i, go to a), b), c), d) respectively.

a) If all the entries in the row of a_i that are corresponding to basic inequalities are non-positive, (3.3) has no feasible solution, stop. If the diagonal entry in the row of a_i is positive, carry out a pivoting on that entry, return to 1); otherwise carry out a pivoting on the largest entry in the row of a_i and then carry out a pivoting on the symmetric entry, return to 1).

b) If is not listed in the table, conduct a vector substitution for. In the row of the entering vector e_i¢, if all the entries that are corresponding to basic inequalities are non-positive, (3.3) has no feasible solution, stop; otherwise if the diagonal entry is positive, carry out a pivoting on that entry, return to 1); otherwise carry out a pivoting on the largest entry and then carry out a pivoting on the symmetric entry, return to 1).

c) If the diagonal entry in the row of is positive, carry out a pivoting on that entry, return to 1); otherwise if there is a positive entry in the row of, carry out a pivoting on the largest entry and then carry out a pivoting on the symmetric entry, return to 1); otherwise conduct a vector substitution for, return to 1).

d) If the diagonal entry in the row of e_n+i is positive, carry out a pivoting on that entry, return to 1); otherwise if there is a positive entry in the row of e_n+i, carry out a pivoting on the largest entry and then carry out a pivoting on the symmetric entry, return to 1); otherwise conduct a vector substitution for e_n+i, return to 1).

4. Mean-Variance Portfolio Optimization

4.1. Markowitz’s Portfolio Selection Model

Suppose that there are n assets for selection. The rates of return of these n assets are R₁, , R_n (random variables) whose means are r₁, , r_n respectively and the covariance matrix is where. Let x₁, x₂, , x_n be fractions of n assets. The problem is to determine the portfolio (x₁, x₂, , x_n) so that it has a minimal variance risk at a certain level of expected return rate. It is formulated as follows.

(4.1)

where and r_p is the expected return rate of the investor. Obviously, r_p should satisfy

to ensure the feasibility.

The KKT conditions of model (4.1) are

(4.2)

Add up the n complementarity conditions to have, thus

.

This is another way to compute the variance risk of the portfolio.

(4.1) is a special case of (3.1) mainly in that (4.1) has no general inequality constraints and has feasible solutions. It makes the computation of (4.1) much easy.

Algorithm 4.1. Pivoting algorithm for (4.2).

Step 1. Initial step.

Let

be the initial basic system to construct initial table as shown by Table 5.

Where e₁, , e_n, e_n+1, e_n+2 are coefficient vectors of the initial basic system which are the n + 2 rows of the

identity matrix of order n + 2, , and.

Step 2. Preprocessing.

Suppose that, and. Carry out four pivoting operations as follows:

e ↔ e₁, h₁↔ e_n+1, r ↔ e₂, h₂ ↔ e_n+2.

Step 3. Main iterations.

1) If all the deviations of nonbasic vectors except for e_n+1 and e_n+2 are nonnegative, the current basic solution is the solution of (4.2), stop. Otherwise

2) select a nonbasic vector (except for e_n+1 and e_n+2) with the most negative deviation to enter the basis. If the diagonal entry in the row of entering vector is positive, carry out a pivoting on that entry, return to 1); otherwise carry out two pivoting operations first on the largest entry in the entering vector row and then carry out a pivoting on the symmetric entry, return to 1).

Denote rank (H) by the rank of H. It can be proved that among n basic vectors e₁, , e_n at most rank (H) + 2 ones may be pivoted out of the basis. It implies that at most rank (H) + 2 components of may be nonzeros.

Let r_i1, , r_iT be the realization of R_i in T periods, then. Let

then the covariance matrix. Since D is an T ´ n matrix, rank (H) is no more than T. Therefore each portfolio obtained by Algorithm 4.1 contains no more than T + 2 assets no matter how larger n is.

An experiment was conducted by using algorithm 4.1 combining with the parameter formula (2.6) for 70 weekend closed prices of 1072 stocks. Here n = 1072 and T = 70 - 1 = 69. It experiences about 80 pivoting operations to obtain one efficient portfolio and 314 pivoting operations to obtain 20 minimal variance portfolios with different values of r_p which are evenly ranging from the minimal mean to the maximal mean of the 1072 stocks. Each pivoting requires about 1074 ´ 1075 multiplications and additions. Therefore the total amounts of computation are 80 ´ 1074 ´ 1075 and 314 ´ 1074 ´ 1075 multiplications and additions respectively. We know that it requires about 1072³/3 multiplications and additions to solve a system of 1072 linear equations in 1072 variables by Gaussian elimination.

Now let us give a small example to show how to solve the portfolio problem by using Algorithm 4.1 and the parameter technique introduced in section 2.

Example 1. An investor is interested in three assets. The means of these three assets are 0.05, 0.11 and 0.08and the covariance matrix is. Solve a portfolio with the minimal variance risk at expected return rate r_p = 0.07, 0.08, 0.09 or 0.1.

Solution. The model of this problem is

where, H is the covariance matrix and  r_p = 0.07, 0.08, 0.09 or 0.1.

The initial table for r_p = 0.07 is given by Table 6.

Since the minimal mean is in the first column, we carry out a double pivoting to have Table 7.

Since the maximal mean is in the second column of the initial table, we carry out a double pivoting (,to have Table 8" target="_self"> Table 8.

In Table 8, ignoring the deviations of e₄ and e₅ since they are associated with equalities, there is only one negative deviation -0.2217 taken by h₃. Therefore h₃ enters the basis. Since the diagonal entry 0.37 in the row of h₃ is positive, carry out a principal pivoting on 0.37 to yield Table 9 ignoring the last three columns.

From the column r_p = 0.07 we see that all the deviations of nonbasic vectors except for e₄ and e₅ are positive, therefore the minimal risk portfolio for r_p = 0.07 is = (0.3671, 0.0338, 0.5991), and l₁ = 0.4165 and l₂ = -3.2117. The variance risk of this portfolio is l₁ + l₂r_p = 0.4165 - 3.2117 ´ 0.07 = 0.1916.

Now consider the portfolio with r_p = 0.08. since D = 0.08 – 0.07 = 0.01, by (2.6), we multiply the column of r by 0.01 and then add it and the column of r_p = 0.07 to get the column of r_p = 0.08. We see that the last three numbers of the column of r_p = 0.08 are still positive. Therefore the minimal risk portfolio for r_p = 0.08 is = (0.2095, 0.2095, 0.5811), and l₁ = 0.2607 and l₂ = -1.4459. The variance risk of this portfolio is l₁ + l₂r_p = 0.2607 - 1.4459 ´ 0.08 = 0.1451.

For r_p = 0.09, since D = 0.09 – 0.08 = 0.01, we multiply the column of r by 0.01 and then add it and the column of r_p = 0.08 to get the column of r_p = 0.09. We see that the last three numbers of the column of r_p = 0.09 are positive also. Therefore the minimal risk portfolio for  r_p = 0.09 is = (0.0518, 0.3851, 0.5631), and l₁ = 0.1050 and l₂ = 0.3198. The variance risk is l₁ + l₂r_p = 0.1050 + 0.3198 ´ 0.09 = 0.1338.

In the same way, we can get the column of r_p = 0.1. We see that the deviation of e₁ is negative and the diagonal entry is positive. Carry out a pivoting e₁ ↔ h₁ to have Table 10.

From Table 10 we see that the last three deviations are positive. Therefore the minimal risk portfolio for r_p = 0.1 is = (0, 0.6667, 0.3333), and l₁ = -0.2811 and l₂ = 4.5556. The variance risk of this portfolio is l₁ + l₂r_p = -0.2811 + 4.5556 ´ 0.1 = 0.1744.

4.2. Portfolio of Upper Bounded Assets

For institutional investors some asset such as a stock is not allowed greater than a limited ratio of the total capital. In this situation the model with upper bounded variables is required. Let u_i be the upper bound for asset x_i that satisfies and for i = 1, , n. This problem is formulated as

(4.3)

where to ensure the feasibility. The minimal value of r_p is obtained as follows. Suppose that. Distribute 1 to x₁, x₂, , x_n sequentially such that, , , , where and. Then

.

Similarly, we can obtain the maximal value r_max of r_p.

The algorithm for (4.3) is as follows.

Algorithm 4.2. Computational steps for (4.3).

Step 1. Initial step, see step 1 of Algorithm 4.1.

Step 2. Preprocessing, see step 2 of Algorithm 4.1.

Step 3. Main iterations.

1) If all the deviations of non-basic vectors except for e_n+1 and e_n+2 are non-negative, the current basic solution is optimal for (4.3), stop. Otherwise

2) select a non-basic vector with negative deviation to enter the basis. If this vector is not listed in the table, conduct a vector substitution. If the diagonal entry in that row is positive, carry out a pivoting on that entry, return to 1); otherwise carry out a pivoting on the most positive entry in that row and then carry out a pivoting on the symmetric entry, return to 1).

Example 2. In Example 1, each asset is not allowed to exceed 50%. Solve a minimal risk portfolio with r_p = 0.09.

Solution. The initial form is given by Table 11.

As done for Example 1, carrying out 4 pivoting operations e ↔ e₁, h₁ ↔ e₄, r ↔ e₂, h₂ ↔ e₅, and then carrying out a principal pivoting h₃ ↔ e₃, we have Table 12 where the columns of e and r and the rows of e₄ and e₅ are deleted.

We see that the third asset 0.5631 is greater than 0.5. Therefore we let -e₃ enter the basis. But -e₃ is not listed

in the current table. For this we conduct a vector substitution for e₃: replace the deviation 0.5631 of e₃ with 0.5 - 0.5631 = -0.0631, reverse signs of other entries in the row of e₃, and then substitute -e₃ for e₃; reverse signs of entries in the column of h₃ and then substitute -h₃ for h₃. It results in Table 13.

In Table 13 we carry out a pivoting on the diagonal entry 2.7027 to yield Table 14.

Now all the deviations are positive and no assets are greater than 0.5. Hence we get the required portfolio. Since -e₃ is basic, x₃ = u₃ = 0.5, and x₁ = 0.0833, x₂ = 0.4167. The variance risk x^THx = 0.1353.

An experiment was conducted by using the same data with n = 1072 and T = 69. For u_i = 0.1, i = 1, 2, , n, it experiences about 95 pivoting operations to obtain one efficient portfolio and 347 pivoting operations to obtain 20 minimal variance portfolios with different values of r_p. Each pivoting requires about 1074 ´ 1075 multiplications and additions. Therefore the total amounts of computation are 95 ´ 1074 ´ 1075 and 347 ´ 1074 ´ 1075 multiplications and additions respectively.

5. Conclusions

In this paper we proposed a series of pivoting-based algorithms for solving the following problems:

•    the system of linear inequalities;

•    convex quadratic programming;

•    mean-variance portfolio selection problems.

These algorithms are concise for understanding and efficient for computing as shown by the numerical examples and computer experiments for 1072 stocks. We also proved the convergence of the smallest index rule for convex QP therefore for mean-variance portfolio optimization for the first time.

6. References

[1]       R. Fletcher, “Practical Method of Optimization: Constrained Optimization,” John Wiley & Sons, New York, 1981.

[2]       J. Nocedal and S. J. Wright, “Numerical Optimization,” Science Press of China, Beijing, 2006.

[3]       P. Wolfe, “The Simplex Method for Quadratic Programming,” Econometrica, Vol. 27, No. 10, 1959, pp. 382-398. doi:10.2307/1909468

[4]       H. Markowitz, “Portfolio Selection,” The Journal of Finance, Vol. 7, No. 1, 1952, pp. 77-91. doi:10.2307/2975974

[5]       H. M. Markowitz and G. P. Todd, “Mean-Variance Analysis in Portfolio Choice and Capital Markets,” Frank J. Fabozzi Associates, Pennsylvania, 2000.

[6]       Z. Z. Zhang, “Convex Programming: Pivoting Algorithms for Portfolio Selection and Network Optimization,” Wuhan University Press, Wuhan, 2004.

[7]       Z. Z. Zhang, “Quadratic Programming: Algorithms for Nonlinear Programming and Portfolio Selection,” Wuhan University Press, Wuhan, 2006.

[8]       Z. Z. Zhang, “An Efficient Method for Solving the Local Minimum of Indefinite Quadratic Programming,” 2007. http://www.numerical.rl.uk/qp/qp.html

[9]       V. Chvatal, “Linear Programming,” W. H. Freeman Company, New York, 1983.