# Distribution of weights in a portfolio with constraints using backtracking¶

In [1]:
import pandas as pd
import numpy as np
import plotly.plotly as py
import plotly.graph_objs as go


## Configure our portfolio¶

For this example, we will use four assets: A, B, C and D. These assets will have the same constraints: No minimum investment and a maximum investment of 35% of the total.

In [2]:
asset_names = ["Asset A", "Asset B", "Asset C", "Asset D"]
asset_constraints = pd.DataFrame(
index=asset_names, columns=['min_weight', 'max_weight'],
data=[[0.0, 0.35], [0.0, 0.35], [0.0, 0.35], [0.0, 0.35]])
asset_constraints

Out[2]:
min_weight max_weight
Asset A 0.0 0.35
Asset B 0.0 0.35
Asset C 0.0 0.35
Asset D 0.0 0.35

We will add an additional constraint that applies to the whole portfolio. This constraint is the maximum turnover, which limits the change in our investing portfolio.

In [3]:
max_turnover = 0.2


We will use an arbitrary estimation for the assets. To keep the example simple, the estimation is assigned in decreasing order. This estimation can be any estimation of return calculated for each of the components of our portfolio

In [4]:
estimation = pd.Series(index=asset_names, data=[0.006, 0.005, 0.002, 0.001])
estimation

Out[4]:
Asset A    0.006
Asset B    0.005
Asset C    0.002
Asset D    0.001
dtype: float64

Finally, we need to start from the current weights of the portfolio. As we are creating one from scratch, we will asign the same weights to all the assets.

In [5]:
# Start in equally weighted
initial_weights = pd.Series(index=asset_names, data=1 / len(asset_names))
initial_weights

Out[5]:
Asset A    0.25
Asset B    0.25
Asset C    0.25
Asset D    0.25
dtype: float64

## Implementation of backtracking algorithm¶

In [6]:
class Distribution:
"""This class accepts different constraints associated to every asset (like maximum or minimum
weight) and the whole porfolio (like the maximum turnover). The algorithm start in a series of
given initial weights and assign the weights according to a estimation of return of the assets."""
def __init__(self, asset_constraints, max_turnover, initial_weights, estimation):
# Sort symbol, weights and asset constraints by estimation
ranked_asset_names = estimation.sort_values(ascending=False).index
# Sort constraints by estimation
self.asset_names = ranked_asset_names
self.asset_constraints = asset_constraints.reindex(self.asset_names)
self.max_turnover = max_turnover
self.initial_weights = initial_weights.reindex(self.asset_names)
self.available_weights = self.get_available_weights()
self.weight_evolution = None
self.selected_weights = None

def run(self):
"""Run the algorithm starting in the first level"""
self.weight_evolution = pd.DataFrame(columns=self.asset_names)
self.selected_weights = pd.Series(
index=self.asset_names, data=[min(row) for row in self.available_weights])
return self.backtracking(0)

def get_available_weights(self):
"""Pre-step before calling to backtracking algorithm. It reduces the amount of candidates by
removing all the weights that do not fulfill a constraint associated to an asset."""
available_weights = \
pd.DataFrame(index=np.arange(100, -1, -1) / 100, columns=self.asset_constraints.index,
data=np.tile(np.arange(100, -1, -1) / 100,
reps=(len(self.asset_constraints.index), 1)).T)

# Minimum Weight
available_weights[available_weights < self.asset_constraints.min_weight] = np.nan

# Maximum weight
available_weights[available_weights > self.asset_constraints.max_weight] = np.nan

# Total turnover
available_weights[available_weights < (self.initial_weights - self.max_turnover)] = np.nan
available_weights[available_weights > (self.initial_weights + self.max_turnover)] = np.nan

return np.array([row[~np.isnan(row)] for row in available_weights.T.values])

def backtracking(self, level):
"""Backtracking algorithm. It search recursively by every possible solution, starting by
the asset with more estimation and going deeper into the tree to look for possible alternatives
in assets with less stimation. It's important to have the assets sorted by estimation and
the available weights sorted by weight, both descending,to start assigned all the possible
weight to the asset with more estimation.
"""
# Are we in the last level (leaves)?
is_leaf = (level + 1) > len(self.available_weights) - 1

# Get available weights for the asset that correspond to the current level
available_weights = self.available_weights[level]

for i in range(0, len(available_weights)):
# Consider current option and all its sub-levels
previous_selected_weights = self.selected_weights.copy()
self.selected_weights[level] = available_weights[i]
self.weight_evolution = self.weight_evolution.append(
self.selected_weights, ignore_index=True)
if self.is_valid():
return self.selected_weights
elif not is_leaf:
# Look for more candidates if we are not in the last level.
# Increasing one level implies to assign some weight (in case it has no minimum)
# to the next asset with more estimation.
result = self.backtracking(level + 1)
if result is not None:
# It found a solution
return result
self.selected_weights = previous_selected_weights
return None

def is_valid(self):
"""Check that a candidate distribution of weights fulfil all the constraints"""

# Sum of all weights = 1
condition_1 = self.selected_weights.sum() == 1

# Total turnover
condition_2 = (self.selected_weights - self.initial_weights).abs().sum() < self.max_turnover

return condition_1 & condition_2

def plot (self, asset_names, notebook=True):
"""Plot the weight of the asssets in each visited state in an area plot"""
if notebook:
init_notebook_mode(connected=True)
cf.go_offline()

weights = self.weight_evolution[asset_names]
if weights.shape[0] > 1000:
weights = self.weight_evolution[asset_names].loc[::100]
weights.iplot(kind='area', fill=True, filename='backtracking_distribution/first_approach',
yTitle='Weight',xTitle='States visited',title='Weight distribution')


## Reduce the number of available weights and run the program¶

In [7]:
distribution = Distribution(asset_constraints, max_turnover, initial_weights, estimation)
pd.DataFrame(index=asset_names,data=distribution.available_weights)

Out[7]:
0 1 2 3 4 5 6 7 8 9 ... 21 22 23 24 25 26 27 28 29 30
Asset A 0.35 0.34 0.33 0.32 0.31 0.3 0.29 0.28 0.27 0.26 ... 0.14 0.13 0.12 0.11 0.1 0.09 0.08 0.07 0.06 0.05
Asset B 0.35 0.34 0.33 0.32 0.31 0.3 0.29 0.28 0.27 0.26 ... 0.14 0.13 0.12 0.11 0.1 0.09 0.08 0.07 0.06 0.05
Asset C 0.35 0.34 0.33 0.32 0.31 0.3 0.29 0.28 0.27 0.26 ... 0.14 0.13 0.12 0.11 0.1 0.09 0.08 0.07 0.06 0.05
Asset D 0.35 0.34 0.33 0.32 0.31 0.3 0.29 0.28 0.27 0.26 ... 0.14 0.13 0.12 0.11 0.1 0.09 0.08 0.07 0.06 0.05

4 rows × 31 columns

In [8]:
# Run the algorithm to obtain the distribution
result = distribution.run()
result

Out[8]:
Asset A    0.35
Asset B    0.25
Asset C    0.25
Asset D    0.15
dtype: float64
In [9]:
distribution.plot(asset_names)