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.
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
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
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.
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:n]; # update variables that are zero ix = np.union1d(ix, np.arange(n)[ans < -EPS]).astype(int) return ans