Portfolio Optimization with the Simplex Method

Portfolio optimization is often presented as a problem of deciding which investments to buy.

But mathematically, it can be viewed as an optimization problem:
Given a set of constraints, how can we allocate capital to maximize expected return?

This week, let's solve a simple portfolio allocation problem using the Simplex Method.

The Problem

Suppose an investor has $100,000 to allocate among three investment strategies:
- Conservative Fund: 4% expected annual return
- Balanced Fund: 7% expected annual return
- Growth Fund: 11% expected annual return

Let:

$\begin{aligned}x_1&=\text{Conservative investment}\\ x_2&=\text{Balanced investment}\\ x_3&=\text{Growth investment}\end{aligned}$

The investor wants to maximize expected annual return:

$\boxed{\max R=0.04x_1+0.07x_2+0.11x_3}$

Subject to:

$\begin{aligned}x_1+x_2+x_3&=100,000,\\ x_1&\geq 30,000,\\ x_2&\geq 20,000,\\ x_3&\leq 40,000,\\ x_1,x_2,x_3&\geq 0 \end{aligned}$

In other words:
- At least $30,000 must be invested in the Conservative Fund.
- At least $20,000 must be invested in the Balanced Fund.
- At most $40,000 can be invested in the Growth Fund.
- All investments must be nonnegative.

Now let's solve this using the Simplex Method.

Converting the Constraints

This is where the mechanics of the Simplex Method become important.

For the equality constraint, we need an artificial variable to establish an initial basic variable:

$x_1+x_2+x_3+a_1=100,000$

For the greater-than-or-equal-to constraints, we subtract a slack variable and add an artificial variable:

$\begin{aligned}x_1-s_1+a_2&=30,000,\\ x_2-s_2+a_3&=20,000 \end{aligned}$

For the less-than-or-equal-to constraint, we simply add a slack variable:

$x_3+s_3=40,000$

Because artificial variables are present, we use the Two-Phase Simplex Method.

Phase I will find a feasible solution while removing the artificial variables from the basis.

Phase I

Our Phase I objective is to minimize the sum of the artificial variables:

$\begin{aligned}\min W&=a_1+a_2+a_3 \\ &=(100,000-x_1-x_2-x_3)+(30,000-x_1+s_1)+(20,000-x_2+s_2)\\ &=150,000-2x_1-2x_2-x_3+s_1+s_2 \end{aligned}$

Since our tableau convention uses maximization, we can instead write:

$\max-W=-150,000+2x_1+2x_2+x_3-s_1-s_2$

For tableau convenience:

$\max-W-2x_1-2x_2-x_3+s_1+s_2=-150,000$

Our initial tableau is therefore:

$\begin{array}{c|cccccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&a_1&a_2&a_3&-W&b \\ \hline a_1&1&1&1&0&0&0&1&0&0&0&100,000 \\ a_2&1&0&0&-1&0&0&0&1&0&0&30,000 \\ a_3&0&1&0&0&-1&0&0&0&1&0&20,000 \\ s_3&0&0&1&0&0&1&0&0&0&0&40,000 \\ \hline-W&-2&-2&-1&1&1&0&0&0&0&1&-150,000 \end{array}$

Choosing the First Pivot

We select the most negative entry in the objective row.

There are two tied choices:

$\begin{aligned}&-\ \text{Column}\ x_1:-2 \\ &-\ \text{Column}\ x_2:-2 \end{aligned}$

When there is a tie, either column is valid. I'll choose:

$x_1$

Now we use the ratio test to determine the pivot row.

Only positive entries in the pivot column are eligible:

$\frac{100,000}{1}=100,000$

And:

$\frac{30,000}{1}=30,000$

The smallest nonnegative ratio is 30,000, so the pivot is in row 2:

$\begin{array}{c|cccccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&a_1&a_2&a_3&-W&b \\ \hline a_1&1&1&1&0&0&0&1&0&0&0&100,000 \\ a_2&\boxed{1}&0&0&-1&0&0&0&1&0&0&30,000 \\ a_3&0&1&0&0&-1&0&0&0&1&0&20,000 \\ s_3&0&0&1&0&0&1&0&0&0&0&40,000 \\ \hline-W&-2&-2&-1&1&1&0&0&0&0&1&-150,000 \end{array}$

The pivot is already 1, so we only need to eliminate the other entries in the pivot column.

After row reduction:

$\begin{array}{c|cccccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&a_1&a_2&a_3&-W&b \\ \hline a_1&0&1&1&1&0&0&1&-1&0&0&70,000 \\ x_1&1&0&0&-1&0&0&0&1&0&0&30,000 \\ a_3&0&1&0&0&-1&0&0&0&1&0&20,000 \\ s_3&0&0&1&0&0&1&0&0&0&0&40,000 \\ \hline-W&0&-2&-1&-1&1&0&0&2&0&1&-90,000 \end{array}$

Second Pivot

The most negative entry is:

$-\ \text{Column}\ x_2:-2$

The ratio test gives:

$\frac{70,000}{1}=70,000$

And:

$\frac{20,000}{1}=20,000$

So the pivot is in row 3:

$\begin{array}{c|cccccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&a_1&a_2&a_3&-W&b \\ \hline a_1&0&1&1&1&0&0&1&-1&0&0&70,000 \\ x_1&1&0&0&-1&0&0&0&1&0&0&30,000 \\ a_3&0&\boxed{1}&0&0&-1&0&0&0&1&0&20,000 \\ s_3&0&0&1&0&0&1&0&0&0&0&40,000 \\ \hline-W&0&-2&-1&-1&1&0&0&2&0&1&-90,000 \end{array}$

After row reduction:

$\begin{array}{c|cccccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&a_1&a_2&a_3&-W&b \\ \hline a_1&0&0&1&1&1&0&1&-1&-1&0&50,000 \\ x_1&1&0&0&-1&0&0&0&1&0&0&30,000 \\ x_2&0&1&0&0&-1&0&0&0&1&0&20,000 \\ s_3&0&0&1&0&0&1&0&0&0&0&40,000 \\ \hline-W&0&0&-1&-1&-1&0&0&2&2&1&-50,000 \end{array}$

We now have three possible entering columns:

$\begin{aligned}&-\ \text{Column}\ x_3:-1 \\ &-\ \text{Column}\ s_1:-1 \\ &-\ \text{Column}\ s_2:-1 \end{aligned}$

I'll choose slack 1 because it allows us to remove artificial 1 from the basis efficiently.

After the pivot and row reduction:

$\begin{array}{c|cccccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&a_1&a_2&a_3&-W&b \\ \hline s_1&0&0&1&1&1&0&1&-1&-1&0&50,000 \\ x_1&1&0&1&0&1&0&1&0&-1&0&80,000 \\ x_2&0&1&0&0&-1&0&0&0&1&0&20,000 \\ s_3&0&0&1&0&0&1&0&0&0&0&40,000 \\ \hline-W&0&0&0&0&0&0&1&1&1&1&0 \end{array}$

Now notice something important.

There are no negative entries in the Phase I objective row, and the optimal value is:

$W=0$

This means the original problem is feasible.

Even better, all the artificial variables are no longer in the basis, so we can move to Phase II.

If the minimum value of the Phase I objective had been greater than zero, the original problem would have been infeasible.

Phase II

Now we return to the original objective:

$\boxed{\max R=0.04x_1+0.07x_2+0.11x_3}$

We can remove the artificial-variable columns and replace the Phase I objective with our original objective:

$\begin{array}{c|ccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&R&b \\ \hline s_1&0&0&1&1&1&0&0&50,000 \\ x_1&1&0&1&0&1&0&0&80,000 \\ x_2&0&1&0&0&-1&0&0&20,000 \\ s_3&0&0&1&0&0&1&0&40,000 \\ \hline R&-2/50&-7/100&-11/100&0&0&0&1&0 \end{array}$

The most negative entry is:

$-\ \text{Column}\ x_3:\frac{-11}{100}$

So we enter with that column.

The ratio test identifies row 4 as the pivot row.

After pivoting:

$\begin{array}{c|ccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&R&b \\ \hline s_1&0&0&0&1&1&-1&0&10,000 \\ x_1&1&0&0&0&1&-1&0&40,000 \\ x_2&0&1&0&0&-1&0&0&20,000 \\ x_3&0&0&1&0&0&1&0&40,000 \\ \hline R&-2/50&-7/100&0&0&0&11/100&1&4,400 \end{array}$

The next most negative entry is:

$-\ \text{Column}\ x_2:\frac{-7}{100}$

So it remains in the basis.

After pivoting:

We now have the most negative coefficient:

$-\ \text{Column}\ s_2:\frac{-7}{100}$

So it enters the basis.

After pivoting:

$\begin{array}{c|ccccccc|c}&x_1&x_2&x_3&s_1&s_2&s_3&R&b \\ \hline s_2&0&0&0&1&1&-1&0&10,000 \\ x_1&1&0&0&-1&0&0&0&30,000 \\ x_2&0&1&0&1&0&-1&0&30,000 \\ x_3&0&0&1&0&0&1&0&40,000 \\ \hline R&-2/50&0&0&7/100&0&2/50&1&6,500 \end{array}$

Finally, the only negative entry remaining is:

$-\ \text{Column}\ x_1:\frac{-2}{50}$

So it remains in the basis.

After the final pivot:

There are now no negative entries in the objective row, so the Simplex Method terminates.

The optimal expected annual return is:

$\boxed{R=7,700}$

This is because we let:

$s_1=s_3=0$

Which leads to:

$\begin{aligned}x_1&=30,000 \\ x_2&=30,000 \\ x_3&=40,000 \end{aligned}$

The Optimal Portfolio

The investor should therefore allocate:
- $30,000 to the Conservative Fund
- $30,000 to the Balanced Fund
- $40,000 to the Growth Fund

This produces an expected annual return of:

$\begin{aligned}R&=0.04(30,000)+0.07(30,000)+0.11(40,000)\\ &=7,700 \end{aligned}$

or $7,700 per year.

The interesting part is that the optimal solution pushes the Growth Fund all the way to its 40% maximum, while keeping the Conservative and Balanced investments exactly at their required minimums.

That's the power of linear optimization:
Rather than simply choosing the investment with the highest expected return, we can mathematically determine the best allocation while satisfying all of our constraints.

In a real portfolio, we would typically add additional constraints for risk, volatility, diversification, liquidity, correlation, and other factors.

And that's where portfolio optimization gets much more interesting.

Next week, I'll cover how row reductions work and the fundamentals of Reduced Row Echelon Form (RREF).

I used row reductions throughout this example to transform our Simplex tableau, but what exactly are we doing when we perform those operations, and why do they work?

That's what we'll explore next week.

Portfolio Optimization with the Simplex Method

Keep Reading