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