Constrained Max Drawdown: a Fast and Robust Portfolio Optimization Approach

Below we review the Nobel prize - winning Markowitz model (see Markowitz (1952) and Markowitz (1959)).

Where the decision variable $x_{i}$ is the proportion of the funds allocated to asset $i$, $\sigma_{i,j}$ is the (daily) covariance between asset $i$ and asset $j$, $r_{i}$ is the expected return of asset $i$ (computed via the Method of Moments i.e. the arithmetic mean over the sample period), and $\rho$ is a minimum (expected) return that is required per trading day.

The objective function seeks to minimize the standard deviation of the portfolio by considering the variance of each asset as well as its covariance with respect to the other assets in the sample.

Constraint (1) ensures that the optimal asset allocation achieves a minimum acceptable expected return.

Constraint (2) enforces that exactly 100% of the funds are allocated to some combination of assets.

Constraint (3) is a set of $n$ box constraints that ensures each asset is assigned a non-negative proportion of the funds, up to a maximum of 100%.

Therefore, this model has a quadratic objective function (since the decision variables are squared) and a set of linear constraints, so it is a QP.

Since the covariance matrix is, by definition, positive semidefinite, then: this is a convex quadratic program, the feasible set is a polyhedron, the solution lies either on the boundary or the interior of the feasible set, and it is relatively easy to solve (compared to a quadratic program with a non positive definite parameter matrix in the objective function).

In that direction, it is worth pointing out that Slater’s conditions are satisfied:

Let $x^{T}\Sigma x$ be the matrix form of the objective, where $\Sigma$ is the covariance matrix.

Note that the program is indeed convex: $x^{T}\Sigma x$ is convex since $\Sigma$ is positive semi-definite, and all constraints are affine, and therefore convex (and concave too)

Further note the program is strictly feasible: let $x_{i}=1$, for a given stock $i$ with an expected return strictly above $\rho$ (there must exist at least 1 such stock, otherwise the program is unfeasible); then the inequality constraint is satisfied strictly, and the equality constraint is also satisfied

Therefore, strong duality holds and, since we know a finite $p^{*}$ exists (since this is a convex quadratic program), then we are guaranteed a finite $d^{*}$ exists too and $p^{*}=d^{*}$ (where $p^{*}$ and $d^{*}$ are the optimal objective values of the Primal and the Dual, respectively).

In our implementation this model has about 400 continuous variables and 400 constraints (including box constraints).

This is the most basic variation of the classical Markowitz model, which is not as popular as the original Markowitz, neither in academia nor industry. One possible reason is that it is much more arbitrary to set a maximum standard deviation than a minimum return (for which you have clear minimum acceptable thresholds like bond yields of maturities similar to one’s sample horizon). Furthermore, like in our particular case, the data collected does not allow us to require a very low daily portfolio standard deviation (otherwise the optimization problem is unfeasible i.e. the feasible region is empty).

Where the decision variable $x_{i}$ is the proportion of the funds allocated to asset $i$, $\sigma_{i,j}$ is the covariance between asset $i$ and asset $j$, $r_{i}$ is the expected daily return of asset $i$ (computed via the Method of Moments i.e. the arithmetic mean over the sample period), and $\sigma_{0}$ is a maximum acceptable daily standard deviation over the time horizon of the sample period.

The objective function seeks to maximize the expected return of the portfolio.

Constraint (1) ensures that the standard deviation of the optimal asset allocation does not go beyond a given threshold.

Constraint (2) enforces that exactly 100% of the funds are allocated to some combination of assets.

Constraint (3) is a set of $n$ box constraints that ensures each asset is assigned a non-negative proportion of the funds, up to a maximum of 100%.

Therefore, this model has a linear objective function and a set of quadratic and linear constraints. Note it cannot be considered a linear program because even if the objective is linear, not all constraints are. This is in fact a Quadratically Constrained Quadratic Program (QCQP).

In our implementation this model has, again, about 400 continuous variables and 400 constraints (including box constraints).

In both Model 1 and Model 2 one’s preferences are heavily constrained by the random data one collects, in the sense that one cannot require a minimum return higher than any return observed in the sample collected, and likewise one cannot require a maximum variance lower than any variance observed in the sample collected.

By optimizing both the expected return and the standard deviation simultaneously we overcome the issue above, in the sense that we will not have an unfeasible problem due to ’unrealistic market demands’.

However, this comes at the cost of introducing arbitrariness in the form of the penalty parameter $\lambda$, which balances how much we care about each of the two objectives.

In any case, as we will see in a later section, we will present a simple heuristic that attempts to remove part of this arbitrariness.

Where the decision variable $x_{i}$ is the proportion of the funds allocated to asset $i$, $\sigma_{i,j}$ is the (daily) covariance between asset $i$ and asset $j$, $r_{i}$ is the expected daily return of asset $i$ (computed via the Method of Moments i.e. the arithmetic mean over the sample period).

The objective function seeks to minimize the negative of the expected return (i.e. equivalent to maximizing the expected return) while also minimizing $\lambda$ times the variance of the portfolio.

Constraint (1) enforces that exactly 100% of the funds are allocated to some combination of assets.

Constraint (2) is a set of $n$ box constraints that ensures each asset is assigned a non-negative proportion of the funds, up to a maximum of 100%.

Therefore, this model has a quadratic objective function and a set of linear constraints, so it is a QP.

Finally, it is worth mentioning that a variation of the above three models introducing $L_{1}$ regularization was considered. However, it was eventually discarded since, by construction, it had no effect irrespective of the size of the penalty parameter $\mu>0$. We provide a simple proof next.

$L_{1}$ regularization introduces an extra term in the objective function, which, in case of a minimization problem, is $\mu\sum_{i=1}^{n}u_{i}$, with $|x_{i}|\leq u_{i}$ for all $i\in\{1,\dots,n\}$. But then, since $x_{i}\geq 0$ for all $i\in\{1,\dots,n\}$, the previous epigraph condition simplifies to $x_{i}\leq u_{i}$ for all $i\in\{1,\dots,n\}$, which implies $\sum_{i=1}^{n}x_{i}\leq\sum_{i=1}^{n}u_{i}$. But we require $\sum_{i=1}^{n}x_{i}=1$ so $1\leq\sum_{i=1}^{n}u_{i}$. Finally, since $\sum_{i=1}^{n}u_{i}$ is penalized in the objective by $\mu>0$, and there are no additional constraints on $u_{i}$, we then have $\sum_{i=1}^{n}u_{i}=1$ at the optimum, irrespective of the particular (positive) value of $\mu$.

In our implementation this model has, again, about 400 continuous variables and 400 constraints (including box constraints).

The authors propose in their 1991 paper [4] a way to turn portfolio optimization into a linear program based on the so-called ‘epigraph trick’. Their key idea is to substitute the standard deviation for the mean absolute deviation, which is a very related concept, as we show next:

(Sample) Mean absolute deviation: $\frac{1}{T}\sum_{t=1}^{T}\left|\sum_{i=1}^{n}(r_{i_{t}}-\overline{r_{i}})x_{i}\right|$

(Sample) Standard deviation: $\sqrt{\frac{1}{T}\sum_{t=1}^{T}[\sum_{i=1}^{n}(r_{i_{t}}-\overline{r_{i}})x_{i}]^{2}}$

where $\overline{r_{i}}=\sum_{t=1}^{T}x_{i}$

The above two expressions would actually be equal if the square root was placed in the innermost sum (recall that $\sqrt{f(x)^{2}}=|f(x)|$). In fact, Konno and Yamazaki prove that the two resulting optimization problems are equivalent if the returns are multivariate normally distributed.

Original program (non linear):

Linear program using epigraph trick:

We see the epigraph variable $y_{t}$ replacing the mean absolute deviation in the objective function, as well as the two sets of $T$ epigraph constraints. The rest of the constraints are identical to Models 1, 2 and 3.

As the authors discuss, this linearized model has several advantages over the usual quadratic one, and here we highlight the ones we believe are most important, in order of importance:

First, the number of functional constraints remains constant at $2T+2$ regardless of the number of stocks included in the model, so it allows one to update the optimal portfolio in real time even if the universe of stocks under consideration is thousands of stocks (which is a very standard number in modern capital markets).

Second, an optimal solution contains at most $2T+2$ non-zero components if short-selling is allowed (non-negativity constraint is dropped). In contrast, an optimal portfolio derived from $L_{2}$ risk (instead of $L_{1}$ like in this case), may contain as many as $n$ assets with non-zero allocation. This is in general not desirable due to fixed costs (transaction fees) and increased portfolio management difficulty (more companies and exposures to monitor). Note that controlling for how many stocks have non-zero allocations via a lower bound on the decision variable (that is activated only if the stock is selected) would turn the problem into a Mixed Integer Program, which is in theory even harder to solve than a QP. We will explore this option in Model 6 and we’ll see in practice this is not the case.

Third, there’s no need anymore to calculate a covariance matrix, so it is easier and faster to update ones’ optimal portfolio when new stocks are added into the universe under consideration, or when new data on individual stock returns becomes available. However, related to the second point above, this model may favor stock concentration (i.e. the opposite of stock diversification) since it does not use covariance information. This may not be desirable.

Overall, the authors report that the computational complexity of solving a $L_{1}$-based model is $O(n)$ while that of a traditional $L_{2}$-based model is $O(n^{2})$, where $n$ is the number of assets under consideration, and so the time savings for large $n$ can be very significant. Or, for a fixed solving time, the LP can consider a much larger universe of stocks, providing a much better optimal solution (at least in theory). As a side note, I believe their linear-time claim is based on empirical evidence since, for example, the complexity of a very common LP algorithm like the Simplex method is exponential in the worst case, but it has been observed to perform linearly in most cases.

But, in addition to the above advantages, we would like to add two key advantages that an LP has over a QP in any setting, not just in the case of portfolio optimization.

First, the optimal solution of an LP, if it exists, is always at a vertex of the polyhedral feasible region, so the optimum of any LP can always be found by checking a finite number of points (which is the essence of the Simplex method). On the other hand, in a QP the optimum may be reached in the interior of the feasible region, and hence there is absolutely no guarantee that it can be found by checking a finite number of points, and hence other, more sophisticated methods must be used.

Second, the objective function of an LP is by definition always convex (and concave), whereas this is not always the case in a QP (the coefficient matrix may not be positive semi-definite), in which case the problem becomes much harder to solve. In portfolio optimization, though, this second aspect will never be an issue since the covariance matrix is by definition positive semi-definite. But still, it is worth pointing this general advantage of LP compared to QP.

If we were to implement this model, it would have about 450 continuous variables and 520 constraints (including box constraints).

Next we present our proposed linearization of the portfolio optimization problem.

We propose a new way to optimize a portfolio that relies on linear programming. The idea is simple: find a portfolio of stocks that minimizes the maximum drawdown of the portfolio (subject to a minimum expected return). Chekhlov et al. (2004) consider a similar approach but they opt for maximizing expected return subject to a maximum drawdown allowed. We instead opt for the opposite formulation, which we find perhaps more intuitive (similar to how the classical Markowitz framework might be considered more intuitive than the ‘reverse’ Markowitz).

The ‘maximum drawdown’ of an asset over a time period is defined as the largest drop in price of the asset in any given period. In our case, the optimal portfolio will combine stocks such that the worst overall performance of the portfolio in any given trading day is as good (‘less bad’) as possible.

This is a reasonable goal to pursue in building a portfolio, and it has several advantages over the traditional mean-variance portfolio optimization. Most notably, the fact that we consider a downside risk metric instead of a general risk metric like the standard deviation, which also penalizes desirable outcomes like presence of returns above the mean return.

Hence, we wish to maximize the minimum portfolio return over a sample time period (equivalent to minimizing the maximum portfolio negative return).

We use the epigraph trick as means of linearization. To prevent a trivial solution allocating 100% of the funds to the one stock with the minimum maximum drawdown (largest minimum return in any given trading day of the sample period), we impose a ceiling of 50% of the funds on any given allocation, so there will be at least 2 stocks in the optimal portfolio (and note that it is not necessarily the case that they will be the 2 stocks with largest minimum return, since those may happen on the same day and hence add up to a larger maximum portfolio drawdown than the optimal achievable). Note that by setting the ceiling to 50% we avoid a trivial solution while also avoiding the arbitrariness of imposing a minimum number of $k>1$ stocks in our optimal portfolio. Finally, note that we don’t really lose anything by requiring at least 2 stocks in the optimal portfolio, since basic domain knowledge tells us that some degree of diversification is always good, and with 1 stock you have none.

Original program (non-linear):

Define $\overline{r_{t}}=\sum_{i=1}^{n}r_{i_{t}}x_{i}$ , that is, the weighted average return on day $t$ of a portfolio using weights $x$.

Linear program using epigraph trick:

The epigraph trick can be interpreted as follows: find the largest possible value of the single variable $y$ such that, for each and every day, $y$ is below (or equal to) the portfolio return given by the weights vector $x$. Therefore this achieves the goal of finding the budget allocation $x$ that maximizes the minimum portfolio return on any given day. The rest of constraints are the same as in the previous models.

Note our LP has just $T+2$ constraints, so it’s even simpler than Model 4. But even more importantly, the number of constraints is independent of the number of stocks under consideration, so it scales very well to larger sets of stocks.

In addition, our LP has $n+1$ variables, instead of $n+T$ in Model 4, and just 1 variable more than the standard QP.

Finally, we write this LP in standard form. By writing it in standard form, this program does not really gain anything (in fact, it becomes somewhat harder to read) but it may be interesting to show one example of an LP that uses the epigraph trick and is in standard form.

In our implementation this model has about 400 continuous variables and 450 constraints (including box constraints).

In this variation of Model 5 we impose a minimum allocation size, which in turn implies a maximum number of positive allocations. This is a potentially more refined formulation since having many small allocations is not desirable in practice, as we have already discussed in subsection 2.4. However, this variation is, in theory, much harder to solve, so it may not be worth it depending on the problem structure, the number of stocks ($n$) and sample time periods ($T$) under consideration.

Let $M=0.5$ be a ‘big M’ parameter. Note $0.5$ is the smallest (i.e. ’best’) $M$ can be because $x_{i}$ could be as large as 0.5 (but not more, since 0.5 is the (least) upper bound on any allocation by construction). In fact, by choosing $M$ this way we obtain the tightest LP relaxation possible; this way the feasible region we work with is as close as possible to the convex hull using available information from the problem.

We want to model for all $i\in\{1,\dots,n\}$ $x_{i}>0\Rightarrow x_{i}\geq 5\%$. This way we also ensure that at most 20 stocks (out of about 400) will be picked.

Let $z_{i}$ $i=1,\dots,n$ be a binary variable that is 1 if and only if $x_{i}>0$.

Note that if we impose $x_{i}\geq 0.05z_{i}$ then when $z_{i}=1$ indeed $x_{i}\geq 0.05$, and when $z_{i}=0$ then $x_{i}\geq 0$… but the problem is that if we don’t do anything else the solver will dodge this (attempted) logical constraint by just setting $z_{i}=0$ for all $i$. We can fix this by also requiring $x_{i}\leq Mz_{i}$ where $M=0.5$ is a ’big M’ parameter. With this additional constraint, the solver cannot dodge our previous constraint by setting all $z_{i}=0$ because that would imply $0\leq x_{i}\leq 0$ for all $i$, which is not even a feasible solution since we require $\sum_{i=1}^{n}x_{i}=1$.

MILP using epigraph trick and logical constraints:

As it can be seen, implementing a very minor refinement like the one in Model 6 required turning an LP into a MILP and increased the number of variables from $n+1$ to $2n+1$, and the number of constraints from $T+2$ to $T+2+2n$, which means the number of functional constraints is no longer independent of the number of stocks.

But more fundamentally, this problem seems similar to the famous Subset sum problem (a special case of the even more famous Knapsack problem (Mathews, 1896)), consisting of finding a subset of numbers in a set that sum to a given constant, in this case 1, which is NP-complete. Our problem at hand is at least as hard, since in our case the candidates to add up are not given ex-ante, which means that there are $2^{n}$ total possible combinations and checking all of them by brute force would would take thousands of times the current age of the universe for $n=100$. In our case we have $n=393$. However, as we will see, the particular structure of our problem and the use of a sophisticated MIP solver like Gurobi will in fact produce a solution in less time than our LP in Model 5.

In our implementation this model has about 400 continuous variables, 400 binary variables, and 1250 constraints (including box constraints).

Table 1 below shows the in-sample results from solving the portfolio optimization models that we have considered in the present work. The quantities in the first three columns below are daily figures.

Table 2 below shows the out-of-sample analogs of the results in Table 1.

The in-sample results show that the price to pay (in terms of expected return or standard deviation) in order to minimize the maximum drawdown is arguably not very high: those models with higher expected return also have higher standard deviation (and vice versa), while always having much larger maximum drawdown (as it’s not optimized for).

In addition, the MD models are much faster. Concretely, our MILP variation is the fastest, by far: 200 times faster than the QPs, and 25 times faster than the unconstrained MD (LP). This is due to the fact that Gurobi is a highly optimized solver for MIP and is able to take advantage of the the particular structure of our portfolio optimization problem. According to Gurobi, their sophisticated MIP algorithm (a combination of Branch-and-Bound and Cutting plane method, i.e. the fancier Branch-and-cut) first does some heavy preprocessing to reduce the problem dimension, and then solves a linear programming relaxation of the problem via Simplex iterations; it seems plausible that by requiring a minimum of a 5% allocation if a stock is chosen, this might already discard many ‘bad’ stocks based on the objective in the preprocessing stage, which greatly reduces the combinatorial complexity of the MILP. Further investigation suggests that after adding just 2 cuts to the original LP relaxation and solving that instance, Gurobi managed to recover an integer feasible solution (and hence solving the entire original MILP) without even needing to do any branching.

In this subsection we analyze the results obtained by each model trained with data from February 1 to May 1 of 2020 (three months), and tested on the subsequent three months (May 2 - August 1). This way we can compare the portfolio optimization solution out of sample.

The idea is to simulate what would have happened if we had optimized our portfolio according to each of the 4 models above on May 1 with data from the previous three months, and then we had checked on August 1 how well each portfolio did. The reason why we wait until August 1 to check is because we optimize our portfolio with 3-month data so it’s only natural the investment horizon should also be 3 months (with the implicit and naive assumption that history repeats itself at least to some relevant extent).

As previously reported in Table 2, our proposed models yielded substantially higher out-of-sample returns than any other model surveyed. Of course, these results should be considered preliminary and hence taken with a grain of salt, since a similar experiment should be repeated multiple times to gather enough evidence to conclude which model is likely the ‘best’.

Unsurprisingly, we notice that the out-of-sample performance (Table 2) is significantly worse than the in-sample performance (Table 1), which cautions the reader against overly optimistic expectations when trying to use the past to gain an edge into the future.

Due to its improved robustness while providing comparable risk-adjusted performance, Model 6 (MILP formulation of the MD model) is our model of choice, at least for a portfolio optimization problem of a similar size to this one (about 400 stocks). Thus, we will focus our solution analysis on the optimal solution this model has found.

According to our proposed model, the three stocks with largest allocation should be CLX (40.34%), KR (28.92%), and TIF (20.73%). But what do those tickers mean? The first one will make a lot of sense to the reader: Clorox. Clorox is a major producer of cleaning products, especially those containing bleach and other strong disinfectants. Needless to say, it seems reasonable that such a stock is picked during a pandemic. Models 1 (12.77%) and 2 (4.8%) also pick this stock, but with less emphasis.

The second one is Kroger, the largest supermarket in the US by revenue. There are three main reasons why, in the time-frame of our training data (February-May 2020) it makes sense to have a significant allocation on this stock. First, with restaurants being closed or operating at reduced capacity due to the pandemic, supermarkets have seen a rise in demand. Second, Kroger in particular has been able to benefit more than other supermarkets thanks to their investments made in their online sales service since 2017, which allowed Kroger to absorbe the surge in demand, with digital sales climbing 92% in the three months before May 23. Moreover, according to Yahoo Finance, Kroger’s reputation surged in those times for their COVID-19 response and racial equity support.

Finally, TIF is the ticker for the luxury jewelry company Tiffany & Co., which admittedly seems an odd pick considering the time-frame of our training data. However, there are two reasons that may explain this, and both of them are completely unrelated to the pandemic. First, the plans of French multinational LVMH (sometimes informally called Louis Vuitton) to acquire Tiffany - plans which were approved by Tiffany’s stockholders in February. Second, Tiffany significantly improved their internal cost structure over the preceding three years, making the company more profitable.