Portfolio Theory (Part 2)

In part 1, we have considered those with equality constraints. In this part, we also consider the situation that all weights are greater than zero and expected return is a min-bounded instead of exact value.

Problem statement

Given N random variables with known expected value u[i],i=1..N and covariance matrix v[i,j] for i,j=1..N and a target return R. Find weight w[i] such that
1. sum[i=1..N]( w[i] ) = W (usually set W = 1)
2. sum[i=1..N]( w[i]*u[i] ) >= R
3. w[i] >= 0 for i=1..N
4. minimize sum[i=1..N,j=1..N]( w[i]*v[i,j]*w[j] ) i.e. variance of portfolio

Algorithm

First, we converse all inequalities into form of x >= 0. Specifically, we introduce a slack variable s and change this constraint
sum[i=1..N]( w[i]*u[i] ) >= R
into
sum[i=1..N]( w[i]*u[i] ) + s = R && s >= 0

The algorithm run as following.
1. solve the optimization problem with only equality constraints by Lagrange Mulipliers, name the solution as opt.
2. if opt is feasible, then we are done. If not, there must be some inequalities violated (i.e. some varibles are negative). For each negative variabls, we set it to zero and repeat step 1.

Code

import numpy as np 
from numpy.linalg import lstsq

EPS = 1e-10
def portfolio2(u,v,R,W=1):
    if R > np.amax(u) or R < np.amin(u):
      raise ArithmeticError('no solution') 
    n = len(u)
    ans = -np.ones(n) 
    ix = []           # index of variables that are zero 
    while np.any(ans < -EPS):
        # standard solution 
        m = np.zeros((n+2,n+2))
        m[0:n,0:n] = 2*v
        m[n,0:n] = m[0:n,n] = 1
        m[n+1,0:n] = m[0:n,n+1] = u
        y = np.zeros(n+2)
        y[n] = W
        y[n+1] = R

        # set variables to zero 
        m[:, ix] = 0
        # remove corresponding Lagrange multiplers
        m = np.delete(m, ix, 0)
        y = np.delete(y, ix)

        # solve by least square 
        ans = lstsq(m, y)[0][0:n];

        # update variables that are zero
        ix = np.union1d(ix, np.arange(n)[ans < -EPS]).astype(int)
    return ans 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s