At each time point agent can:
- open one position if he has enough funds. This reduces funds by current price. The price is added to the list of open positions
- close one position (the one opened farthest in time) if he has open positions. This adds current price to funds, removes position from the list and increases profit by current price minus open price.
- hold (do nothing).
Given an array of prices, the aim is to find optimal open/close moments to get maximum profit.
I have implemented this, but the code runs very long (1 minute for 16 observations). What are the possibilities for the improvement?
Also, I want to get the optimal path itself. I can not store all the paths. What's the algorithm for backtracking?
Here is the code using Python:
import matplotlib.pyplot as plt
from collections import deque
import numpy as np
import time
def optimal_strategy(prices, root):
s = deque([root])
m = 0.0
while s:
n = s.pop()
t = n['time'] + 1
if t == len(prices):
m = np.max([m, n['profit']])
continue
p = prices[t]
s.append({'name': 'h' + str(t), 'time': t, 'parent': n['name'],
'funds': n['funds'], 'positions': n['positions'], 'profit': n['profit']})
if p < n['funds']:
s.append({'name': 'ol' + str(t), 'time': t, 'parent': n['name'],
'funds': n['funds'] - p, 'positions': n['positions'] + [p], 'profit': n['profit']})
if len(n['positions']) > 0:
s.append({'name': 'cl' + str(t), 'time': t, 'parent': n['name'],
'funds': n['funds'] + p, 'positions': n['positions'][1:], 'profit': n['profit'] + p - n['positions'][0]})
return m
nobs = 16
np.random.seed(1)
prices = np.cumsum(np.random.normal(size=nobs))
plt.plot(prices)
t0 = time.time()
m = optimal_strategy(prices, {'name': 'r', 'time': -1, 'parent': None,
'funds': 4.0, 'positions': [], 'profit': 0.0})
print('Time {} Max {}'.format(time.time() - t0, m))
Here is an example showing how to get the exact trades that lead to the maximum funds. Maximizing funds guarantees that we maximized profits. Detailed calculations about which trades earned what profit can be calculated after we know the sequence.