Theo Diamandis

It's Convex if You Tilt Your Head a Bit

In this post, I discuss some techniques to deal with fractional objective functions which are not convex as given but can still be tackled using the tools of convex optimization. We'll explore these techniques using a specific example: choosing the portfolio with the maximum Sharpe ratio.

Markowitz portfolio construction

First some background on portfolio construction. Consider choosing a portfolio of (long-only) positions xx which have estimated returns μ\mu and covariance Σ\Sigma. Often we aim to construct a portfolio that balances risk and return. A standard technique is Markowitz mean-variance portfolio optimization (see [BV04[1] 4.4]), which solves the convex optimization problem

maximizeμTxγxTΣxsubject to1Tx=1x0, \begin{aligned} &\text{maximize} &&\mu^Tx - \gamma x^T\Sigma x \\ &\text{subject to} &&\mathbf{1}^Tx = 1 \\ &&&x \geq 0, \end{aligned}

where γ\gamma is a parameter that controls the tradeoff between risk and return. We can easily plot this tradeoff curve (for simulated data) using the convex optimization domain specific language (DSL) Convex.jl and the solver Hypatia.jl.

using LinearAlgebra, Random, SparseArrays, Printf
using Convex, Hypatia
using Plots

# Create data
k, n = 5, 20
F = sprandn(n, k, 0.5)
D = Diagonal(rand(n) * sqrt(k))
Σ = Matrix(D + F*F')
μ = randn(n)

# Vary γ to plot tradeoff curve
N = 30
rets = zeros(N)
σs = zeros(N)
γs = 10 .^ range(-4, 3, N)

# Solve Markowitz problem with each γ
x = Variable(n)
for (ind, γ) in enumerate(γs)
    markowitz = maximize(μ'*x - γ*quadform(x, Σ), sum(x) == 1, x >= 0)
    solve!(markowitz, () -> Hypatia.Optimizer(); silent_solver=true)
    rets[ind] = dot(μ, x.value)
    σs[ind] = sqrt(dot(x.value, Σ, x.value))

plt = plot(
    xlabel="Standard Deviation of Return",
    ylabel="Mean Return",
    title="Pareto Optimal Portfolios",
    label="Pareto optimal portfolios",

Maximizing the Sharpe ratio

A parameter-free alternative to the formulation above is to maximize the Sharpe ratio of a long-only portfolio:

maximizeμTxxTΣxsubject to1Tx=1x0. \begin{aligned} &\text{maximize} &&\frac{\mu^Tx}{\sqrt{x^T\Sigma x}} \\ &\text{subject to} &&\mathbf{1}^Tx = 1 \\ &&&x \geq 0. \end{aligned}

Intuitively, we seek to maximize the return we get per unit of risk (standard deviation). We note that the objective function

f(x)=μTxxTΣx f(x) = \frac{\mu^Tx}{\sqrt{x^T\Sigma x}}

is nonconvex, so it cannot be directly tackled by a convex optimization solver. However, there are standard techniques to deal with these fractional programming problems.

Taking advantage of homogeneity

We can take advantage of the fact that the objective ff is 1-homogenous, i.e., f(αx)=αf(x)f(\alpha x) = \alpha f(x) for αR++\alpha \in \mathbb{R}_{++}, to transform the problem into a more friendly form. The general idea is to introduce some scaling factor α\alpha such that either the numerator or denominator is fixed to be 11. We'll work with a new variable y=αxy = \alpha x and reformulate the optimization problem as

maximize1yTΣysubject toμTy=1y0. \begin{aligned} &\text{maximize} &&\frac{1}{\sqrt{y^T\Sigma y}} \\ &\text{subject to} &&\mu^Ty = 1 \\ &&&y \geq 0. \end{aligned}

Note that we no longer need the normalization constraint; we simply let

α=1Ty, \alpha = \mathbf{1}^Ty,

so that 1Tx=1T(y/α)=1\mathbf{1}^Tx = \mathbf{1}^T\left(y / \alpha\right) = 1. The reformulated problem is equivalent to a convex quadratic program:

minimizeyTΣysubject toμTy=1y0. \begin{aligned} &\text{minimize} &&y^T\Sigma y \\ &\text{subject to} &&\mu^Ty = 1 \\ & &&y \geq 0. \end{aligned}

After solving this for yy^\star, we can recover the solution to the initial problem

x=αy=y1Ty, x^\star = \alpha y^\star = \frac{y^\star}{\mathbf{1}^Ty^\star},

which satisfies our constraints by construction. We can the maximum Sharpe ratio portfolio in a few lines of code:

# Construct Sharpe ratio optimization problem
y = Variable(n)
sharpe1 = minimize(quadform(y, Σ), μ'*y == 1, y >= 0)
solve!(sharpe1, () -> Hypatia.Optimizer(); silent_solver=true)

# Recover portfolio
xs = y.value ./ sum(y.value)
ret = dot(μ, xs)
σ = sqrt(dot(xs, Σ, xs))
    label="Sharpe maximizing portfolio",

A more general approach

More generally, we consider the concave-convex fractional programming problem

maximizef(x)g(x)subject toxS \begin{aligned} &\text{maximize} &&\frac{f(x)}{g(x)} \\ &\text{subject to} && x \in S &\end{aligned}

where ff is nonnegative concave, gg is positive convex, and SS is a compact convex set. To transform this problem into something tractable, we introduce the new variables

y=xg(x),t=1g(x). y = \frac{x}{g(x)}, \qquad t = \frac{1}{g(x)}.

If f(x)0f(x) \geq 0 on SS, then the optimization problem

maximizetf(y/t)subject toy/tStg(y/t)1t>0 \begin{aligned} &\text{maximize} && t\cdot f(y/t) \\ &\text{subject to} && y/t \in S \\ & && t\cdot g(y/t) \leq 1 \\ & && t > 0 \end{aligned}

is equivalent to (8) [Schaible74[2]]. (Note the relaxation of the inequality.) We note that the perspective transforms of ff and gg preserve concavity and convexity respectively [BV04[1] 3.2.6]. Furthermore, the image and inverse images of SS under the perspective transform are convex [BV04[1] 2.3.3], so

S={(y,t)y/tS, t>0} S' = \{(y,t)\mid y/t \in S, \; t > 0\}

is a convex set. Thus, the problem above is a convex optimization problem. We recently used the same idea for an optimization problem that appears in photonics.

Applying this to the Sharpe ratio problem:

It is reasonable to assume that μTx0\mu^Tx \geq 0 on x0x \geq 0, as we can usually hold a portion of our assets in cash (μn=1\mu_n = 1). Therefore, including negative returns is silly (something something inflation, I know, but this isn't a finance post). We let f(x)=μTxf(x) = \mu^Tx, which is concave, and g(x)=xTΣx=xΣg(x) = \sqrt{x^T\Sigma x} = \|x\|_\Sigma , which is convex. Applying the methods above and simplifying, we get the convex optimization problem

maximizeμTysubject toy01Ty>0yΣ1 \begin{aligned} &\text{maximize} && \mu^Ty \\ &\text{subject to} && y \geq 0 \\ & && \mathbf{1}^Ty > 0\\ & && \|y\|_\Sigma \leq 1 \\ %& t > 0.%%%% \end{aligned}

We can solve this and verify it gives the same solution as our approach using homogeneity.

# Sharpe ratio optimization: 2nd approach
y_2 = Variable(n)
sharpe2 = maximize(μ'*y_2, quadform(y_2, Σ) <= 1, y_2 >= 0)
solve!(sharpe2, () -> Hypatia.Optimizer(); silent_solver=true)

# Recover portfolio
x_sharpe_2 = y_2.value ./ sum(y_2.value)
ret2 = dot(μ, x_sharpe_2)
σ2 = sqrt(dot(x_sharpe_2, Σ, x_sharpe_2))

# Compare approaches
rel_error_ret = abs(ret - ret2) / min(ret, ret2)
rel_error_σ = abs(σ - σ2) / min(σ, σ2)
    "Relative error between approaches:" *
    "\n - mean return: $(@sprintf("%.2g", rel_error_ret))" * 
    "\n - standard deviation: $(@sprintf("%.2g", rel_error_σ))"
Relative error between approaches:
 - mean return: 1.2e-07
 - standard deviation: 1.1e-07

Concluding thoughts

In general, a lot of problems that don't look convex at first glance (or cannot be readily input into a solver) are tractable after a simple transformation. Disciplined Convex Programming (DCP) modeling tools like Convex.jl and CVXPY (which has extended DCP to classes of problems like log-log convex programs) help with a lot of these transformations, but many still require a manual approach.

Perhaps future optimization DSL's will be able to recognize a much larger class of convex problems automatically and apply the needed transformations. I'm pretty interested in this topic. If you are too, don't hesitate to reach out!

Thank you to Guillermo Angeris for helpful comments on a draft of this post!


[1] Boyd, S., Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.

[2] Schaible, S. (1974). Parameter-free convex equivalent and dual programs of fractional programming problems. Zeitschrift für Operations Research, 18(5), 187-196.