💰 quantitative finance

Large-Scale Portfolio Optimization Problem Under Cardinality Constraint With Enhanced Multi-Objective Evolutionary Algorithms

This paper proposes enhanced multi-objective evolutionary algorithms featuring novel solution representations, operators, and repair mechanisms to efficiently solve large-scale portfolio optimization problems under cardinality constraints, demonstrating faster convergence and superior performance compared to traditional methods as market complexity increases.

Original authors: Danial Ramezani, Mostafa Abouei Ardakan

Published 2026-07-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Danial Ramezani, Mostafa Abouei Ardakan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a treasure hunter trying to build the ultimate backpack for a long journey. You want two things: the most valuable gold coins (high return) and the lightest, safest load (low risk). But there's a catch: your backpack has a strict rule. You can only carry a specific number of different items, say between 3 and 10, no matter how many treasures are scattered across the map. This is the "Cardinality-Constrained Portfolio Optimization" problem.

For decades, investors have tried to solve this using "exact" math methods, like trying to count every single grain of sand on a beach to find the perfect handful. The paper explains that this approach is like trying to drink from a firehose; it's too slow and gets stuck when the number of assets (the grains of sand) gets huge. In fact, the authors note that adding these real-world rules turns the problem into a nightmare for computers, known as "NP-hard," where traditional math tools just give up or take forever.

The Big Idea: A New Backpack Design
Instead of trying to count every grain, the authors built a new kind of backpack and a new set of rules for how to pack it. They took a popular tool called NSGA-II (think of it as a smart, evolving robot that tries different backpack combinations) and gave it a major upgrade.

Here is how their new system works, using their own analogies and mechanics:

1. The "Fixed-Size" Backpack (New Encoding)
Old methods tried to carry a list of all possible treasures and just mark which ones to take. If you had 225 treasures, your list was always 225 items long, even if you only carried 10. This made the robot waste time checking empty slots.
The authors changed the backpack itself. Now, the backpack has exactly Kmax slots (the maximum number of items you are allowed to carry). If you are allowed to carry up to 5 items, your backpack has exactly 5 slots.

The Trick: If you put the same treasure in two slots, it counts as one item, but the weight (money) adds up. This makes it much easier for the robot to see if it's breaking the rules. If the backpack has fewer than Kmin unique items (say, only 2 unique items when you need at least 3), the robot knows it needs to swap in a new treasure.

2. The "Two-Phase" Hunt (Mating Strategies)
The robot doesn't just guess randomly. It hunts in two distinct phases, like a detective solving a case:

Phase 1 (The Wide Net): At the start, the robot is wild. It uses a "Knee-based" strategy to find the best combinations of treasures. It looks for the "knee" of the curve—the sweet spot where you get the most gold for the least extra weight. It mates solutions that are close to this ideal point to find the right mix of assets quickly.
Phase 2 (The Fine-Tune): Once it has a good list of treasures, it stops looking for new ones and starts adjusting the amount of each treasure. It uses a "Similarity-based" strategy, mating backpacks that already have the same treasures but different weights, to fine-tune the exact balance.

3. The "Explorer" Tool
Sometimes, the robot fixes a broken backpack (one that has too few or too many items) by just swapping a random item in. But the authors realized this is clumsy. They invented a new tool called the "Explorer."
Imagine you have a backpack that is missing an item. Instead of just grabbing the first rock you see, the Explorer looks at a few different ways to fill that gap. It tries five different "heuristic" methods (like spreading money equally, or giving more money to the safest items) to see which one makes the backpack better. It then picks the best version and even walks a little way into the "unknown" space between the old and new backpack to see if it can find something even better. This ensures the fix isn't just "okay," but actually an improvement.

4. The "Repair Crew" (Handling Constraints)
When the robot accidentally breaks the rules (like picking too many items or putting too much money in one item), it doesn't just throw the backpack away. It has a specialized repair crew:

The Association Crew: Looks at what other successful backpacks in the current group are holding and copies those patterns.
The Score Crew: Groups treasures by how well they perform together and picks the best group.
The Threshold Crew: Specifically looks for treasures that don't move in sync with the others (low correlation) to add diversity.

What They Found (The Results)
The authors tested this new system against the old, standard robot on four real-world markets: the DAX 100 (Germany), S&P 100 (USA), Nikkei 225 (Japan), and the Tehran Stock Exchange (TSE).

The Size of the Test: They used datasets with 85, 98, 225, and 418 assets respectively.
The Rules: They set the backpack to hold between Kmin and Kmax items (e.g., between 2 and 10, or exactly 10).
The Outcome: In simulations running for 100 iterations with a population of 100 solutions, their upgraded robot consistently found better backpacks.
- It found solutions that were closer to the "perfect" theoretical limit (measured by a metric called IGD).
- It covered a wider range of good options (measured by Hypervolume).
- It did this faster and more reliably, especially when the number of assets grew large.

What They Explicitly Rule Out
The paper is very clear about what doesn't work well for this specific problem:

Exact Methods: They argue that traditional, exact mathematical methods are inefficient for this problem because it is NP-hard. They suggest these methods are too slow for large markets.
Penalty Functions: While some researchers use "penalty functions" (giving a bad score to broken backpacks), this paper explicitly states that the vast majority of successful studies use repair mechanisms (fixing the backpack) instead. They chose to repair the solutions rather than just penalize them.
Random Guessing: They show that simply mating random solutions early on wastes time. Their "Knee-based" selection is necessary to guide the search.

How Sure Are They?
The authors are confident in their results, but they are careful with their language. They state that their approach "indicates" and "demonstrates" superiority based on 100 runs of the simulation. They used statistical tests (the Sign Test and Wilcoxon Signed-Rank Test) to prove that their results weren't just luck.

For example, in the TSE market, their method won 10 out of 10 times against the standard method for the Hypervolume metric.
However, they note that for the DAX 100 market, the improvement in one specific metric (MGD) wasn't statistically significant at the strictest level, though it was still better on average.

The Bottom Line
The paper suggests that by changing how we represent the problem (the fixed-size backpack), how we search for solutions (the two-phase hunt), and how we fix mistakes (the Explorer tool), we can find better investment portfolios much faster. This is especially true when the market gets crowded with hundreds of assets. The authors conclude that while their method is a strong improvement, it's not a magic wand; it still needs to be adapted if investors want to add even more complex rules like transaction costs later on. But for now, it's a much smarter way to pack the backpack.

Technical Summary: Large-Scale Portfolio Optimization Under Cardinality Constraint With Enhanced Multi-Objective Evolutionary Algorithms

Problem Definition
The paper addresses the Cardinality-Constrained Portfolio Optimization Problem (CCPOP), a variant of the classic Mean-Variance (MV) model introduced by Markowitz. While the MV model seeks to maximize return and minimize risk, it often fails to account for real-world constraints, rendering the problem NP-hard. Specifically, this study focuses on the Cardinality Constraint (CC), which limits the number of assets ( $K$ ) in a portfolio to a range $[K_{min}, K_{max}]$ , and the Boundary Constraint (BC), which restricts the weight of individual assets to $[\epsilon_i, \delta_i]$ . The inclusion of these constraints, alongside the conflicting objectives of risk and return, makes exact methods inefficient for large-scale markets, necessitating the use of approximation algorithms.

Methodology
The authors propose a customized version of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) designed to handle the specific complexities of CCPOP. The methodology introduces four primary innovations:

Novel Solution Encoding:
Instead of the standard real-valued vector of size $N$ (total assets), the authors propose a chromosome of fixed size $K_{max}$ consisting of two rows:
- Row 1: Asset identifiers selected for the portfolio.
- Row 2: Corresponding weights.
  This representation inherently caps the number of assets at $K_{max}$ , eliminating the need for repair mechanisms to remove excess assets when the upper bound is violated. Duplicate assets in the first row are permitted; their weights in the second row are summed to determine the total allocation for that asset.
Dynamic Mating Strategies:
The selection process is divided into two phases to balance exploration and exploitation:
- Early Iterations (Exploration): A Knee-based Tournament Selection is used. It selects individuals based on their Euclidean distance to the "Utopia Point" (ideal max return/min risk), prioritizing solutions near the knee of the Pareto Front (PF) to find high-quality asset combinations quickly.
- Late Iterations (Exploitation): A Similarity-based Matrix Tournament Selection is activated. It identifies portfolios with identical or similar asset combinations and mates them to fine-tune capital allocations (weights) rather than searching for new asset mixes.
Specialized Mutation and the "Explorer" Operator:
- Mutations: Three types of mutations are dynamically combined. Early iterations utilize mutations that swap assets (global search), while later iterations focus on adjusting weights (local search).
- Explorer Operator: A novel repair and optimization operator designed for individuals that violate constraints. It generates candidate solutions using five heuristic capital distribution methods (e.g., equal distribution, volatility-based, return-to-risk ratio). It then explores the space between the target solution and the best candidate using a specific interpolation formula (Equation 10) to find superior weight allocations without altering the asset set.
Constraint Handling Mechanisms:
- Cardinality Repair: Three techniques are proposed to add assets to portfolios violating the $K_{min}$ $K_{min}$ constraint:
  - Associated-based: Uses clustering of the current Pareto Front to identify assets that frequently co-occur with the violated portfolio's assets.
  - Score-based: Clusters the entire asset universe and selects assets from the highest-scoring clusters based on correlation and performance metrics.
  - Threshold-based: Selects assets with low correlation to existing portfolio assets, controlled by a strictness coefficient.
- Boundary Repair: A modified version of Chang et al. (2000) is used to adjust weights to satisfy $[\epsilon_i, \delta_i]$ , specifically handling cases where duplicate assets cause total weight violations.

Key Contributions

Encoding Efficiency: The fixed-size chromosome representation simplifies the handling of the upper cardinality bound and reduces the computational overhead of repair mechanisms.
Adaptive Search: The two-phase mating strategy (Knee-based vs. Similarity-based) effectively balances the discovery of diverse asset combinations with the optimization of capital allocation.
Enhanced Repair: The "Explorer" operator provides a structured way to re-optimize weights for repaired solutions, ensuring feasibility does not come at the cost of performance.
Scalability: The approach is specifically designed to maintain performance as the number of available assets ( $N$ ) increases, addressing a known weakness in standard evolutionary algorithms for large-scale problems.

Experimental Results
The proposed algorithm was tested against standard NSGA-II and a version using the new encoding but standard mating strategies. Experiments were conducted on four datasets: DAX 100, S&P 100, Nikkei 225, and the Tehran Stock Exchange (TSE) (418 assets).

Performance Metrics: The study utilized Hypervolume (HV), Generational Distance (GD), Inverted Generational Distance (IGD), and Diversity Metric ( $\Delta$ ). A "Modified Generational Distance" (MGD) was also introduced to normalize comparisons.
Findings:
- The proposed approach consistently outperformed standard NSGA-II across all metrics and markets.
- The performance gap widened as the number of assets increased, demonstrating superior scalability.
- The algorithm achieved faster convergence rates, particularly evident in the IGD plots over generations.
- Statistical validation via Sign Tests and Wilcoxon Signed-Rank Tests confirmed the significance of the improvements (p < 0.05) in most metrics, with the exception of MGD in the DAX 100 market.
- Computational time analysis indicated that while Python is slower than C++, the proposed encoding and logic resulted in execution times comparable to or better than standard approaches, even for the larger TSE dataset.

Significance and Claims
The paper claims that the proposed strategy offers a robust solution for large-scale portfolio optimization under cardinality constraints. The authors assert that their approach:

Provides faster convergence and extensive search ability compared to traditional methods.
Maintains performance stability as the market size (number of assets) grows, whereas standard algorithms tend to degrade.
Effectively handles the trade-off between finding the optimal set of assets and the optimal allocation of weights through its phased mating and "Explorer" operator.

The study concludes that while the current formulation addresses CC and BC, future work could incorporate additional real-world constraints such as transaction costs and liquidity, which would require further modifications to the proposed repair mechanisms.

More like this