Cardinality and Sparsity Constraints

A pension fund's mean-variance optimizer, given 500 candidate stocks, might output non-zero weights in all 500 of them, most tiny. That portfolio is optimal on paper and unmanageable in practice: every position needs monitoring, every trade costs money to execute, and a fund holding 500 names at an average of 0.2% each has effectively index-hugged its way out of any real conviction. The desk wants at most, say, 30 names. That is not a preference an ordinary optimizer can express.

The analogy before any symbols

Packing a carry-on bag for a trip is easy if you can bring anything; the problem becomes hard the moment there is a hard limit of, say, seven items. Now you are not just choosing what is useful, you are choosing which useful things to leave out, and the two decisions interact: leaving out the umbrella changes whether the raincoat earns its slot. A cardinality constraint on a portfolio is exactly this seven-item suitcase problem, applied to hundreds of stocks instead of clothes.

The mechanics

A standard mean-variance problem minimizes $w^\top \Sigma w - \eta \, \mu^\top w$ subject to $\mathbf{1}^\top w = 1$ (and usually $w \geq 0$). A cardinality constraint adds a cap on how many weights may be nonzero:

$\|w\|_0 \leq K,$

where $\|w\|_0$ counts the number of nonzero entries and $K$ is the maximum number of names allowed, say 30. In words: at most $K$ assets may be held at all; the rest must be exactly zero, not just small. This "counting" function is not smooth or convex, so it cannot be handed to a standard quadratic-program solver the way a variance term can; choosing which $K$ assets is a combinatorial decision, and with 500 candidates and $K=30$ there are more possible subsets than atoms worth checking one by one.

Two practical workarounds exist. The exact route uses mixed-integer optimization: attach a binary variable $z_i \in \{0,1\}$ to each asset meaning "held or not," force $w_i \leq z_i$, and cap $\sum z_i \leq K$. This is solvable for hundreds of assets with modern solvers but scales badly beyond a few thousand. The approximate route relaxes $\|w\|_0$ into the $\ell_1$ penalty $\lambda\|w\|_1$, the same idea as lasso regularization: penalizing the sum of absolute weights pushes many of them to exactly zero as a side effect, without ever explicitly counting names, and it is fast because it stays convex.

Estimation noise is why cardinality constraints often help out-of-sample despite discarding "optimal" information: each additional tiny weight is itself an estimate with error, so a portfolio that keeps only the assets with the strongest, most reliably estimated signal, rather than spreading conviction thin across everything within a standard deviation of noise, can generalize better even though it looks less optimal in-sample.

Worked example: exact versus relaxed on six assets

Six assets, unconstrained minimum-variance weights: 22%, 3%, 19%, 4%, 31%, 21%. With $K=3$, the exact mixed-integer solver checks combinations of three assets and finds that keeping assets 1, 3, and 5 (the three largest) and reoptimizing their weights among just those three gives variance only 4% higher than the six-asset optimum. The lasso relaxation, tuned so that $\lambda$ shrinks three weights to exactly zero, happens to select the same three assets here and lands within 1% of the exact solution's variance, cheaply.

Worked example: when the relaxation disagrees with the exact answer

Now suppose two of the six assets are highly correlated with each other (0.95) and both have moderate individual value. The lasso penalty, applied evenhandedly, often keeps both correlated assets at reduced weight rather than picking one, because $\ell_1$ regularization does not "know" they are redundant. The exact cardinality solver, forced to choose only $K=3$ total, recognizes that holding both correlated assets wastes a slot and instead picks one of them plus two more diversifying names, achieving lower variance for the same $K$. This gap, roughly 6% worse variance for the lasso version in this case, is the price of using a convex proxy instead of solving the real combinatorial problem.

What this means in practice

Cardinality constraints are standard at long-short equity funds with position-count mandates, and at any desk where operational cost per name (data feeds, compliance review, execution relationships) is a real budget line, not just an abstraction. Exact solvers are used up to a few thousand assets with a time budget; beyond that, or for daily rebalancing where speed matters, the $\ell_1$ relaxation or clustering-based methods like Nested Clustered Optimization are the practical default.