P vs NP Problem in Portfolio Optimization: Integrating the Markowitz-CAPM Framework with Cardinality Constraints and Black-Scholes Derivative Pricing

1. Probleemstelling en Context

Het paper adresseert de fundamentele spanning tussen economische theorie en computationele complexiteit in de portefeuilleoptimalisatie.

• De Kern: De klassieke Markowitz-middelpunt-variatie-optimalisatie is een convex probleem dat in polynomiale tijd oplosbaar is. Echter, wanneer een harde kardinaliteitsbeperking wordt opgelegd (een vast aantal posities $K$ in de portefeuille, $|supp(w)| \le K$), verandert het probleem in een Mixed-Integer Quadratic Program (MIQP).
• P vs NP Kader: Dit introduceert een discrete subset-selectie die gekoppeld is aan continue gewichtsoptimalisatie. De zoekruimte groeit combinatorisch ($\approx C(n,K)$), wat het probleem NP-hard maakt. Het vinden van de globale optimale subset is in het algemeen niet in polynomiale tijd oplosbaar (tenzij P=NP), terwijl het verifiëren van een oplossing wel efficiënt is.
• Praktische Uitdaging: Institutionele portefeuilles vereisen vaak beperkte posities (voor monitoring en liquiditeit) en kunnen derivaten bevatten. De paper onderzoekt hoe men deze realistische beperkingen kan modelleren zonder de auditbaarheid en reproduceerbaarheid van de resultaten te verliezen.

2. Methodologie

De auteur ontwikkelt een geïntegreerd economisch-computationeel raamwerk met de volgende pijlers:

• Data en Calibratie:

  • De asset-universe bestaat uit ongeveer 94 Amerikaanse industriële portefeuilles van Aswath Damodaran.
  • Verwachte rendementen ($\mu$): Gecalibreerd via het CAPM-model: $\mu_i = R_f + \beta_i \cdot ERP$, waarbij $\beta$ en de risicovrije rente ($R_f$) en het marktrisicopremie ($ERP$) als input dienen.
  • Covariantiematrix ($\Sigma$): Geconstrueerd via een single-index (market-model) structuur. Dit maakt de matrix volledig reconstrueerbaar op basis van de beta's en totale volatiliteit, zonder dat ruwe tijdreeksen nodig zijn. De correlatie wordt gedomineerd door de marktfactor ($\beta_i \beta_j \sigma_m^2$).

• Optimalisatiemodel:

  • Een MIQP-formulering die continue gewichten ($w$) koppelt aan binaire selectievariabelen ($z$).
  • Doel: Minimaliseren van variatie voor een gegeven rendement (of maximaliseren van de Sharpe-ratio) onder de beperking dat slechts $K$ activa een gewicht $>0$ hebben.

• Oplossingsalgoritmen (Heuristieken):
  Omdat exacte oplossingen voor grote $n$ en $K$ onhaalbaar zijn, worden drie benaderingsmethoden geëvalueerd:

  1. Greedy Screening: Selectie van de $K$ beste industrieën op basis van een CAPM-Sharpe-proxy.
  2. Monte Carlo Sampling: Willekeurige steekproeven van $K$-subsets met Dirichlet-gewichten.
  3. Genetische Algoritmen (GA): Evolutie van populaties van selectie-vectoren met crossover en mutatie, gevolgd door continue heroptimalisatie van de gewichten binnen de geselecteerde subset.

• Integratie van Derivaten:

  • Een Black-Scholes Europese call-optie wordt toegevoegd als extra instrument.
  • Delta-mapping: De optie wordt gelineariseerd via de 'delta' ($\Delta$) en gemapt naar een CAPM-consistent momentensysteem ($\beta_{optie} \approx L \cdot \beta_{onderliggend}$, waarbij $L$ de hefboomfactor is).
  • Validatie: Een "bump test" (±1% beweging in de onderliggende) vergelijkt de lineaire benadering met volledige Black-Scholes herwaardering om de nauwkeurigheid te verifiëren.

• Reproduceerbaarheid:

  • Strikte protocollen voor random seeds (10 runs), rapportage van verdelingsstatistieken (mediaan, IQR, percentielen) in plaats van alleen de "beste run", en runtime-profielering.

3. Belangrijkste Resultaten

• Efficiënte Rand en Discontinuïteiten:
  De harde kardinaliteitsbeperking vervormt de efficiënte rand aanzienlijk ten opzichte van de ongeconstrueerde Markowitz-oplossing. Er treden discontinuïteiten op, en de optimale portefeuilles vertonen vaak een concentratie in sectoren met hoge beta's (hoge verwachte rendementen) ondanks de beperkte diversificatie.

• Prestatie van Heuristieken:

  • De Genetische Algoritme met continue heroptimalisatie van gewichten levert de meest stabiele resultaten, met een mediaan Sharpe-ratio van ongeveer 0,088 (onder de specifieke CAPM-aannames).
  • Het is cruciaal om te rapporteren op basis van mediaan en IQR over meerdere seeds; het "beste resultaat" is statistisch fragiel.
  • Op een gereduceerd probleem ($n=20, K=6$) konden heuristieken de exacte oplossing (via volledige enumeratie) bereiken, wat de validiteit van de benadering bevestigt.

• Afhankelijkheidsdiagnostiek:
  De single-index structuur resulteert in sterke onderlinge correlaties (mediaan $\rho \approx 0,77$) en een dominante eerste eigenwaarde ($\approx 76\%$ van de totale variantie). Dit beperkt de effectieve diversificatie en verklaart waarom de optimalisatie vaak clusters van sectoren selecteert die sterk met de markt bewegen.

• Derivaten-Overlay:

  • Het toevoegen van een optie via delta-mapping verhoogt zowel het verwachte rendement als het risico (volatiliteit) drastisch door de hefboomwerking.
  • Conclusie: Een hogere Sharpe-ratio is niet automatisch het gevolg van het toevoegen van een optie; vaak neemt het risico meer toe dan het rendement, wat leidt tot een lagere of gelijke risk-adjusted performance. De lineaire benadering (delta) bleek zeer nauwkeurig voor kleine schokken (<1%), maar gamma- en vega-effecten worden genegeerd.

4. Bijdragen aan de Wetenschap

1. Complexiteitskadering: Het paper positioneert de portefeuilleselectie met kardinaliteitsbeperkingen expliciet binnen de P vs NP taxonomie, onderbouwd met een formele schets van NP-hardheid.
2. Auditbare Empirische Back-bone: Het biedt een volledig reconstrueerbaar dataset-ontwerp (Damodaran inputs + single-index $\Sigma$) dat onafhankelijke verificatie mogelijk maakt zonder toegang tot geheime handelsdata.
3. Reproduceerbaarheid in Heuristieken: Het stelt een nieuwe standaard voor het rapporteren van stochastische optimalisatie, waarbij verdelingsstatistieken (mediaan/IQR) en convergentiecurves prioriteit krijgen boven enkelvoudige "beste run" resultaten.
4. Reproduceerbare Derivaten-Integratie: Het demonstreert hoe niet-lineaire instrumenten (opties) op een transparante, CAPM-consistente manier in een lineair raamwerk kunnen worden opgenomen, inclusief validatie via bump-tests.

5. Betekenis en Conclusie

Dit onderzoek toont aan dat het oplossen van realistische portefeuilleproblemen niet alleen een economisch, maar ook een computationeel uitdaging is. De invoering van kardinaliteitsbeperkingen verplaatst het probleem van een convex, polynomiaal oplosbaar probleem naar een NP-hard domein.

De belangrijkste implicatie is dat er geen universeel, schaalbaar exact algoritme bestaat voor dit type probleem (als P $\neq$ NP). Daarom is de focus verschoven naar gecontroleerde heuristieken met strikte reproduceerbaarheidsprotocollen. Het paper biedt een "journal-grade" template voor het bestuderen van NP-hard portfolio selection, waarbij de trade-off tussen rekentijd en oplossingskwaliteit transparant wordt gemaakt. Het benadrukt dat in de praktijk de "beste" oplossing vaak een compromis is tussen computationele haalbaarheid, stabiliteit over verschillende seeds, en de economische realiteit van beperkte diversificatie en derivatenrisico's.