Portfolio optimization with cardinality constraint

mixed-integer programmingoptimization

The simple portfolio optimization problem with cardinality constraint is stated as

\begin{align}
\min_{\vec{w}} -\vec{\mu}^T \vec{w} + \frac{\gamma}{2} \vec{w}^T \Sigma \vec{w}
\end{align}

such that

\begin{align}
\sum_{i}^{N} w_i &= 1 \\
\epsilon_i z_i \leq w_i \leq& \xi_i z_i \;\;\; i = 1,2,\cdots,n\\
\sum_i^{N} z_i &= K \;\;\; K < N
\end{align}

The first term in the objective function maximizes the returns and the second term minimizes the risk of the portfolio. $\gamma$ is the risk aversion factor.

In the constraints, $\epsilon_i$ and $\xi_i$ are lower bound and upper bound on weight for $i^{th}$ asset. $z_i \in \lbrace 0,1 \rbrace $ are binary variables which says whether the $i^{th}$ asset is included in portfolio or not. The third constraint is the cardinality constraint which says that there must be atmost $K$ assets in the portfolio.

Assuming, $\epsilon_i = 0,\; \xi_i = 1 \; \forall i$, instead of the second constraint above, can I have the following constraint
$$\sum_i^{N} z_i w_i = 1$$
If yes, then does it make the problem harder to solve using some MINLP solver?

Best Answer

The change you propose is mathematically valid (meaning it will not alter the feasible region or the optimal solution), but it likely will make the problem harder (perhaps much harder) to solve. The original formulation has linear constraints and minimizes a convex quadratic function, for which many high quality solvers exist. The convex feasible region contributes to making the problem relatively easy to solve. Your substitute constraint makes the feasible region nonconvex, which complicates things.

Related Solutions

Correct way to interpret notation used in optimization problem

$$\min_{\boldsymbol{\mathcal{x}}} \max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) \tag{4.15}$$

Define $$f(\boldsymbol{\mathcal{x}})=\max_{\boldsymbol{\mathcal{\lambda}}} g(\boldsymbol{\mathcal{x}},\boldsymbol{\mathcal{\lambda}})$$ with $$g(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}) = \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$$ then: $$\min_{\boldsymbol{\mathcal{x}}} \max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = \min_{\boldsymbol{\mathcal{x}}} f(\boldsymbol{\mathcal{x}})$$

Get the weights of porfolio variance given standard deviation

The following code generates points directly on the Pareto frontier. It uses the fact that the minimizer of a quadratic objective under linear constraints can be obtained by solving a linear system. The frontier changes shape if you uncomment the lines that add the risk-free asset.

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

# read data
stock_prices = pd.read_csv('Elegible stocks-Grid view.csv', index_col=0)
returns = stock_prices.pct_change()
mu = 252 * returns.mean().values
sigma = 252 * returns.cov().values
n = mu.shape[0]

# add risk free asset to mu/sigma
risk_free_rate = 0.0178
z = np.zeros((n,1))
#mu = np.block([mu, risk_free_rate])
#sigma = np.block([[sigma, z], [z.T, 0]])
#n = mu.shape[0]

# solve minimize w'∑w subject to μ'w = r, e'w=1 for varying r
mu = np.expand_dims(mu, axis=1)
e = np.ones((n,1))
returns = np.linspace(risk_free_rate, np.max(mu))
volatilities = []
for r in returns:
    A = np.block([[2*sigma, mu, e], [mu.T, 0, 0], [e.T, 0, 0]])
    b = np.zeros(n+2)
    b[n] = r
    b[n+1] = 1
    w = np.linalg.solve(A, b)[:n]

    volatility = np.sqrt( w.T @ sigma @ w )
    volatilities.append(volatility)

# plot results
plt.plot(volatilities, returns)
plt.xlabel('Volatility')
plt.ylabel('Return')
plt.show()

Related Question

Non-linear optimization programming, with step function in constraint