Cardinality-constrained portfolio optimization in Python (MIQP)

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 (MIQP): 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 MIQP

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.12, 0.02, 0.05, 0.00,-0.01, 0.02, 0.03,-0.01],
    [ 0.02, 0.12, 0.00,-0.03, 0.01, 0.02,-0.02, 0.00],
    [ 0.05, 0.00, 0.24, 0.11, 0.02,-0.02, 0.00,-0.04],
    [ 0.00,-0.03, 0.11, 0.30,-0.02, 0.02,-0.03,-0.05],
    [-0.01, 0.01, 0.02,-0.02, 0.13,-0.05, 0.02, 0.02],
    [ 0.02, 0.02,-0.02, 0.02,-0.05, 0.22,-0.03,-0.01],
    [ 0.03,-0.02, 0.00,-0.03, 0.02,-0.03, 0.18, 0.03],
    [-0.01, 0.00,-0.04,-0.05, 0.02,-0.01, 0.03, 0.22]]
N, K = 8, 3
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)

result = Client().solve(m)
print(result.display)
# The weights w[0..N-1] are the model's first N variables, reported as x1..xN.
print("class:", result.model_class, "| held:", [
    f"asset {i+1} = {result.solution[f'x{i+1}']:.4f}"
    for i in range(N) if result.solution[f"x{i+1}"] > 1e-6])

├── shots
│   ├── 1 · primal-dual · global   0.0398   0.42s  ◀ best
│   ├── 2 · primal                 0.0398    2.0s
│   └── 3 · primal                 0.0398    2.0s
├── status:     optimal
├── feasible:   true
├── objective:  0.03976761723715457
├── x:          x1=0.3248, x10=0, x11=0, x12=0, x13=1, x14=1, …  (16 variables)
└── solve_time: 2.0027 s

class: miqcp | held: ['asset 1 = 0.3248', 'asset 5 = 0.4272', 'asset 6 = 0.2481']

What you get

The least-risk three-asset portfolio holds assets 1, 5 and 6, at weights 0.32, 0.43 and 0.25, for a variance of 0.0398. With sixteen variables the x: line truncates, which is why the script prints the held positions itself.

Look at which assets it did not pick. The three least volatile assets are 1, 2 and 5 (variances 0.12, 0.12, 0.13), so the obvious portfolio is those three. The model drops asset 2 and takes asset 6 instead, whose variance is 0.22 — nearly double. It is worth holding because it moves against asset 5 (Sigma[4][5] = -0.05), and that cancellation buys more than the extra volatility costs. Ranking the assets individually cannot find this; only pricing the subset as a whole can.

status: optimal means quicopt proved it — over all C(8,1)+C(8,2)+C(8,3) 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 shots block is where that proof shows up. quicopt runs several solvers on the model and reports what each one's answer is worth. All three found 0.0398 here, but three solvers agreeing is not a proof. Only the first one settles the question: it came back primal-dual · global, so it carries a dual bound, and that bound is what rules out every portfolio you never looked at. The other two returned a primal point only — the same weights, with nothing attached that says no better weights exist.

The winning shot finished in 0.42 s, yet solve_time reads 2.0 s, because solve_time is the wall clock for the whole set: quicopt waits for the slower shots even after the answer is already proved.

The same model scales from eight 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 quadratic (MIQP)
• 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.