Portfolio Optimization with the Minimax algorithm [help needed]

Hi All,

Scanning the academic literature, I stumbled on an old algorithm for portfolio optimization called the Minimax (sometimes Maximin in fact) :
A MiniMax Portfolio selection rule with linear programming solution - Martin Young(1998)

Some recent white papers (for ex: here and here and elewhere), rank highly this somewhat deceptively simple algorithm compared to more complex alternatives, the most well known being the Markowitz and MAD portfolio selection scheme.

Being formulated easily, I attempted to write this optimization problem using cvxpy in a long only algo. But as I am not very advanced in linear programming, I have doubts about my implementation, so I turn to the proverbial wisdom of crowds and ask this community for help.

You will notice that I use the second equivalent formulation at the bottom of page 3 of the Young paper. I could not make the first one work.

62
Backtest from to with initial capital
Total Returns
--
Alpha
--
Beta
--
Sharpe
--
Sortino
--
Max Drawdown
--
Benchmark Returns
--
Volatility
--
 Returns 1 Month 3 Month 6 Month 12 Month
 Alpha 1 Month 3 Month 6 Month 12 Month
 Beta 1 Month 3 Month 6 Month 12 Month
 Sharpe 1 Month 3 Month 6 Month 12 Month
 Sortino 1 Month 3 Month 6 Month 12 Month
 Volatility 1 Month 3 Month 6 Month 12 Month
 Max Drawdown 1 Month 3 Month 6 Month 12 Month
import cvxpy as cvx
import pandas as pd
import numpy as np
import quantopian.algorithm as algo
import quantopian.experimental.optimize as qopt

def get_minimax_weights(returns, max_position=0.15):
num_stocks = len(returns.columns)
mean=returns.mean(axis=0).values
A = returns.as_matrix()
x = cvx.Variable(num_stocks)
objective = cvx.Maximize(mean.T*x)

constraints = [
A*x >= 0,
sum(x) <= 1,
x <= max_position,
x >= 0
]
prob = cvx.Problem(objective, constraints)
prob.solve(verbose=True)
print prob.value
w=pd.Series(data=np.asarray(x.value).flatten(),index= returns.columns)
w=w/w.abs().sum()
return w

def initialize(context):
context.securities=  [
sid(3766),
sid(4151),
sid(8347),
sid(16841),
sid(1091),
sid(4707),
sid(4283),
sid(2263),
sid(1267)
]
schedule_function(my_rebalance, date_rules.every_day(), time_rules.market_open(hours=1))

def my_rebalance(context,data):
returns = data.history(context.securities, 'price', 200, '1d').pct_change().dropna()
w=get_minimax_weights(returns, max_position=0.15)
order_ptf(w)

def order_ptf(weights):
algo.order_optimal_portfolio(
objective=qopt.TargetPortfolioWeights(weights),
constraints=[
qopt.MaxGrossLeverage(1.0),
]
)


There was a runtime error.
7 responses

Hi Lionel,

From what I can see your implementation looks correct. Not sure I agree with the logic of the paper of maximizing mean returns, however. Means are extremely difficult / noisy to estimate so I would expect this optimization to shift weights erratically (similar to mean-variance), not really a feature of a robust optimization method. You could definitely check if that's true, of course.

Best,
Thomas

Disclaimer

The material on this website is provided for informational purposes only and does not constitute an offer to sell, a solicitation to buy, or a recommendation or endorsement for any security or strategy, nor does it constitute an offer to provide investment advisory services by Quantopian. In addition, the material offers no opinion with respect to the suitability of any security or specific investment. No information contained herein should be regarded as a suggestion to engage in or refrain from any investment-related course of action as none of Quantopian nor any of its affiliates is undertaking to provide investment advice, act as an adviser to any plan or entity subject to the Employee Retirement Income Security Act of 1974, as amended, individual retirement account or individual retirement annuity, or give advice in a fiduciary capacity with respect to the materials presented herein. If you are an individual retirement or other investor, contact your financial advisor or other fiduciary unrelated to Quantopian about whether any given investment idea, strategy, product or service described herein may be appropriate for your circumstances. All investments involve risk, including loss of principal. Quantopian makes no guarantees as to the accuracy or completeness of the views expressed in the website. The views are subject to change, and may have become unreliable for various reasons, including changes in market conditions or economic circumstances.

what is the better optimization, Thomas? minimize the variance for a given return?

Yeah, minimum volatility is one of the best and most stable optimization techniques. It's also very simple.

Hi Thomas,

Thanks for checking this.

As I understand it, it is not about maximizing returns or estimating them but controlling the maximum loss that the portfolio would incur, to quote the abstract of the paper :

This principle uses minimum return rather than variance as a measure of
risk. In particular, the portfolio is chosen which minimizes the maximum loss over all
past observation periods, for a given level of return. This objective function avoids the
logical problems of a quadratic (non-monotone) utility function implied by mean-variance
portfolio selection rules. The resulting minimax portfolios are diversified; for normal
returns data, the portfolios are nearly equivalent to those chosen by a mean-variance rule.

In fact, simillar algorithms use maximum drawdown, CVAR or Gini coefficient in the same kind of framework to measure potential loss as a way to avoid quadratic programming.

if anyone has tried those other schemes, i would love to hear about it.

Hi @Lionel,

Thanks very much for posting this paper! I think there are some useful ideas here. I have worked with CVaR optimization (per the Uryasev paper you link to) as well as the L1 risk measure (i.e., MAD) per Konno. I was initially attracted to them because they are linear programming problems. However that was because, at the time, we did not have cvxpy white-listed on Quantopian. Today with cvxpy I don't think you need to be averse to quadratic terms. Anyhow, I think these methods have use as risk constraints not as objectives. You need to have some exogenous alpha vector to work in here. For example, I have an implementation of the L1 risk constraint here.

Here is an implementation of optimization with a limit on CVaR (thanks to Scott Sanderson for the insight that avg_worst_returns = cvx.sum_smallest(portfolio_rets, nsamples) / nsamples captures the CVaR):

def calc_opt_cvar_weights(
alpha_vector,
hist_returns,
max_risk=-0.01,
cvar_ptile=0.95,
max_position=0.05,
lookback_days=520):

num_stocks = len(alpha_vector)
num_days = len(hist_returns)
A = hist_returns.fillna(0.0).as_matrix()[-(lookback_days-1):, :]
x = cvx.Variable(num_stocks)

nsamples = round(num_days * (1-cvar_ptile))
portfolio_rets = A*x
avg_worst_returns = cvx.sum_smallest(portfolio_rets, nsamples) / nsamples
objective = cvx.Maximize(alpha_vector*x)

constraints = [
avg_worst_returns > max_risk,
sum(x) == 0,
sum(cvx.abs(x)) <= 1,
x <= max_position,
x >= -max_position
]
prob = cvx.Problem(objective, constraints)
prob.solve(verbose=False)
print prob.value
sol = np.asarray(x.value).flatten()
return sol


I hope to find some time to work through the Minimax risk constraint.

Disclaimer

The material on this website is provided for informational purposes only and does not constitute an offer to sell, a solicitation to buy, or a recommendation or endorsement for any security or strategy, nor does it constitute an offer to provide investment advisory services by Quantopian. In addition, the material offers no opinion with respect to the suitability of any security or specific investment. No information contained herein should be regarded as a suggestion to engage in or refrain from any investment-related course of action as none of Quantopian nor any of its affiliates is undertaking to provide investment advice, act as an adviser to any plan or entity subject to the Employee Retirement Income Security Act of 1974, as amended, individual retirement account or individual retirement annuity, or give advice in a fiduciary capacity with respect to the materials presented herein. If you are an individual retirement or other investor, contact your financial advisor or other fiduciary unrelated to Quantopian about whether any given investment idea, strategy, product or service described herein may be appropriate for your circumstances. All investments involve risk, including loss of principal. Quantopian makes no guarantees as to the accuracy or completeness of the views expressed in the website. The views are subject to change, and may have become unreliable for various reasons, including changes in market conditions or economic circumstances.

Hi Jonathan,

Thanks for the code sample that's exactly the kind of code I was looking to experiment with.

On the same topic of portfolio optimization, There's this paper from Stanford that also seems to be worthy of investigation (with the full code provided) :
Risk-Constrained Kelly Gambling

We consider the classic Kelly gambling problem with general distribution of outcomes, and an additional risk constraint that limits the probability of a drawdown of wealth to a given undesirable level. We develop a bound on the drawdown probability; using this bound instead of the original risk constraint yields a convex optimization problem that guarantees the drawdown risk constraint holds. Numerical experiments show that our bound on drawdown probability is reasonably close to the actual drawdown risk, as computed by Monte Carlo simulation. Our method is parametrized by a single parameter that has a natural interpretation as a risk-aversion parameter, allowing us to systematically trade off asymptotic growth rate and drawdown risk. Simulations show that this method yields bets that out perform fractional-Kelly bets for the same drawdown risk level or growth rate. Finally, we show that a natural quadratic approximation of our convex problem is closely connected to the classical mean-variance Markowitz portfolio selection problem.

Like the other approaches, It seems to perform somewhat ok performance wise (see backtest).
I set a bound to the maximum weight so my adaptation of it is more of a fractional kelly.

I have some hard time setting the bounds. If I set the drawdown ( minimalWealthFraction=0.7) too low, the solver fails, in this case a 30% drawdown seems unachievable with just equity indexes.

Let me know what you think.

62
Backtest from to with initial capital
Total Returns
--
Alpha
--
Beta
--
Sharpe
--
Sortino
--
Max Drawdown
--
Benchmark Returns
--
Volatility
--
 Returns 1 Month 3 Month 6 Month 12 Month
 Alpha 1 Month 3 Month 6 Month 12 Month
 Beta 1 Month 3 Month 6 Month 12 Month
 Sharpe 1 Month 3 Month 6 Month 12 Month
 Sortino 1 Month 3 Month 6 Month 12 Month
 Volatility 1 Month 3 Month 6 Month 12 Month
 Max Drawdown 1 Month 3 Month 6 Month 12 Month
import cvxpy as cvx
import pandas as pd
import numpy as np
import quantopian.algorithm as algo
import quantopian.optimize as qopt

def get_minimax_weights(returns, target_loss=0.03):
num_stocks = len(returns.columns)
mean = returns.mean(axis=0).values
A = returns.as_matrix()
x = cvx.Variable(num_stocks)
objective = cvx.Maximize(mean.T * x)

constraints = [
x >= 0,
A * x >= -target_loss,
cvx.sum_entries(x) == 1.0
]
prob = cvx.Problem(objective, constraints)
prob.solve(verbose=True)
print prob.value
print x.value
w = pd.Series(data=np.asarray(x.value).flatten(), index=returns.columns)
w = w / w.abs().sum()
return w

def get_RCK_weights(returns, minimalWealthFraction=0.7, confidence=0.3,max_expo=0.25):
n = len(returns.columns)
pi = np.array([1. / len(returns)] * len(returns))
r = (returns+1.).as_matrix().T
b_rck = cvx.Variable(n)
lambda_rck = cvx.Parameter(sign='positive')
lambda_rck.value = np.log(confidence) / np.log(minimalWealthFraction)
growth_rate = pi.T * cvx.log(r.T * b_rck)
risk_constraint = cvx.log_sum_exp(np.log(pi) - lambda_rck * cvx.log(r.T * b_rck)) <= 0
constraints = [cvx.sum_entries(b_rck) == 1, b_rck >= 0, b_rck<=max_expo, risk_constraint]
rck = cvx.Problem(cvx.Maximize(growth_rate), constraints)
rck.solve(verbose=False)
#print rck.value
#print b_rck.value
w = pd.Series(data=np.asarray(b_rck.value).flatten(), index=returns.columns)
w = w / w.abs().sum()
return w

def initialize(context):
context.securities=  [
sid(25904), # VFH (Vanguard Financials ETF)
sid(25906), # VHT (Vanguard Health Care ETF)
sid(25905), # VGT (Vanguard Information Technology ETF)
sid(26667), # VDE (Vanguard Energy ETF)
sid(25902), # VCR (Vanguard Consumer Discretionary ETF)
sid(22445), # IBB (iShares Nasdaq Biotechnology Index Fund)
sid(39479), # IBB (iShares Nasdaq Biotechnology Index Fund)
sid(22887), # EDV VANGUARD treasury
sid(25899), # VB = Vanguard small cap
sid(25898)  # VAW (Vanguard Materials ETF)
]
schedule_function(my_rebalance, date_rules.every_day(), time_rules.market_open(hours=1))

def my_rebalance(context,data):
returns = data.history(context.securities, 'price', 400, '1d').pct_change().dropna()
w=get_RCK_weights(returns)
order_ptf(w)

def order_ptf(weights):
algo.order_optimal_portfolio(
objective=qopt.TargetWeights(weights),
constraints=[
qopt.MaxGrossExposure(1.0),
]
)


There was a runtime error.

Another great resource for the community, and another paper from stanford:

Expert Pooling using Exponential Weighting EPEx

Markowitz and Cover offer competing philosophies
toward solving the portfolio selection problem. Instead
of trying to determine which approach is most desirable
overall, we recognize that different approaches to port-
folio selection perform better or worse depending on
the market conditions, which can change dramatically
over time. Based on this observation, we introduce
an algorithm called “Expert Pooling using Exponential
Weighting” (EPEx), which combines the portfolios of
individual experts based on their recent performance.

with full code available at https://github.com/nmchaves/stock-portfolio-selection

This woud allow to combine multiple portfolio selection schemes.