Cardinality-constrained portfolio optimization in Python (MINLP)

Classic minimum-variance portfolio optimization gives every asset a weight. In practice you often want to hold only a handful of positions — fewer tickets, lower transaction and monitoring cost. Adding "hold at most K assets" turns the smooth quadratic problem into a mixed-integer quadratic program (MINLP): binary hold/skip decisions on top of a variance objective. With quicopt it is a short Pyomo model, solved to a proven optimum.

The naive approach

The tempting shortcut is to solve the ordinary minimum-variance QP, then keep the K largest weights and renormalize. That is only a heuristic: dropping the small positions changes which weights are optimal for the ones that remain, so the truncated portfolio is usually not the best K-asset portfolio.

The exhaustive fix — enumerate every allowed subset of assets and solve a QP for each — is correct but blows up: choosing at most K of N assets is C(N,1) + … + C(N,K) subsets, hopeless the moment N is realistic. Let the solver make the discrete choice and the continuous one together.

Model it as an MINLP

A continuous weight w[i] per asset and a binary d[i] that is 1 only if the asset is held. Fully invested (sum(w) == 1), a weight can be positive only when its asset is held (w[i] <= d[i]), and at most K assets are held (sum(d) <= K). Minimize the portfolio variance wᵀΣw. Modeled in Pyomo (pip install "quicopt[pyomo]"):

import pyomo.environ as pyo
from quicopt import Client
Sigma = [[0.10,0.02,0.04,0.00],[0.02,0.08,0.01,0.02],[0.04,0.01,0.12,0.03],[0.00,0.02,0.03,0.06]]
N, K = 4, 2
m = pyo.ConcreteModel()
m.w = pyo.Var(range(N), bounds=(0, 1))
m.d = pyo.Var(range(N), domain=pyo.Binary)
m.budget = pyo.Constraint(expr=sum(m.w[i] for i in range(N)) == 1)
m.link = pyo.Constraint(range(N), rule=lambda m, i: m.w[i] <= m.d[i])
m.card = pyo.Constraint(expr=sum(m.d[i] for i in range(N)) <= K)
m.obj = pyo.Objective(expr=sum(Sigma[i][j]*m.w[i]*m.w[j] for i in range(N) for j in range(N)), sense=pyo.minimize)
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(m).display)

├── status:     optimal
├── feasible:   true
├── objective:  0.037500218891769396
├── x:          x1=0.3738, x2=0, x3=0, x4=0.6262, x5=1, x6=0, …  (8 variables)
└── solve_time: 0.1888 s

What you get

The least-risk two-asset portfolio holds assets 1 and 4 — weights 0.37 and 0.63 (x1, x4), with the two hold flags on (x5=1, and the flag for asset 4 set) and assets 2 and 3 dropped. The variance is 0.0375 (the …218 tail is floating point). Even though only two assets are held, this beats every other pair and every single-asset portfolio.

status: optimal means quicopt proved it — over all C(4,1)+C(4,2) ways to choose the held assets and every continuous weighting of each, no portfolio has lower variance. It picks the discrete subset and the weights in one solve, because the binary hold/skip decisions and the quadratic variance are handled together rather than as a relaxation.

The same model scales from four assets to hundreds — change the covariance matrix and K, not the method. (This is an illustrative optimization example, not financial advice.)

Next

• The problem class behind this: Mixed-integer nonlinear (MINLP)
• The unconstrained cousin: Portfolio optimization (QP)
• A runnable model for every supported class: Examples

Reference: T.-J. Chang, N. Meade, J. E. Beasley, Y. M. Sharaiha, Heuristics for cardinality constrained portfolio optimisation, Computers & Operations Research, 2000.