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

1. Problem Statement

The paper addresses the intersection of financial theory and computational complexity by tackling the Cardinality-Constrained Portfolio Optimization (CCPO) problem.

• The Core Conflict: Classical Markowitz mean–variance optimization is a convex quadratic program solvable in polynomial time. However, imposing a hard cardinality constraint (limiting the portfolio to $K$ assets, i.e., $|supp(w)| \le K$) transforms the problem into a Mixed-Integer Quadratic Program (MIQP).
• Complexity Implication: This discrete–continuous coupling renders the problem NP-hard. While verifying a candidate solution is polynomial, finding the globally optimal subset of assets requires exploring a combinatorial space of size $\binom{n}{K}$, which grows exponentially with the number of assets ($n$) and the constraint ($K$).
• The Gap: Existing literature often treats portfolio theory and algorithm engineering separately. This paper aims to operationalize the P vs NP divide within a financially auditable framework, demonstrating how to handle intractable optimization with transparent, reproducible heuristics.

2. Methodology

The study employs a rigorous, reproducible empirical workflow combining financial modeling, complexity theory, and stochastic optimization.

A. Data and Financial Modeling

• Asset Universe: Constructed from Aswath Damodaran's ~94 U.S. industry portfolios.
• Expected Returns ($\mu$): Calibrated using the Capital Asset Pricing Model (CAPM): $\mu_i = R_f + \beta_i \cdot ERP$, where inputs are levered betas and an equity risk premium.
• Covariance Matrix ($\Sigma$): Constructed via a Single-Index (Market Model) approach. Since time-series data was not used, $\Sigma$ is reconstructed analytically using industry betas, volatilities, and market variance. This ensures the matrix is fully auditable and positive semi-definite (PSD).
• Derivative Integration: A Black–Scholes European Call is embedded as an additional asset. Its moments are mapped into the mean–variance framework using Delta-based linearization:
  • $\beta_{option} \approx L \cdot \beta_{underlying}$
  • $\sigma_{option} \approx L \cdot \sigma_{underlying}$
  • Where $L$ is the leverage factor derived from the option price and delta.

B. Optimization Framework

The problem is formalized as an MIQP:
$$\min_{w,z} w^T \Sigma w - \lambda \mu^T w$$
Subject to:

• $\sum w_i = 1, w_i \ge 0$
• $w_i \le u_i z_i$ (Linking continuous weights to binary selection)
• $\sum z_i = K$ (Cardinality constraint)

C. Solution Algorithms

Due to NP-hardness, the paper evaluates three approximation schemes:

1. Greedy Screening: Ranks assets by a CAPM Sharpe proxy and selects the top $K$.
2. Monte Carlo Sampling: Randomly samples $K$-subsets and assigns weights (Dirichlet distribution), retaining the best performers.
3. Genetic Algorithm (GA): Evolves binary selection vectors ($z$) with crossover/mutation, followed by continuous re-optimization of weights on the selected subset to find the local optimum.

D. Reproducibility Protocol

A key methodological contribution is the strict adherence to reproducibility:

• Seed Control: All stochastic methods are run across 10 independent random seeds.
• Reporting: Results are reported as distributions (Median, IQR, Quantiles) rather than single "best-run" outcomes.
• Benchmarking: A reduced universe ($n=20, K=6$) is solved via full enumeration to provide a ground-truth benchmark for measuring heuristic optimality gaps.

3. Key Contributions

1. Complexity Anchoring: Explicitly frames cardinality-constrained portfolio selection as an NP-hard problem, justifying the reliance on heuristics and the necessity of distributional reporting over optimality guarantees.
2. Audit-Ready Empirical Backbone: Provides a fully reconstructible covariance matrix and CAPM calibration based on public industry data, eliminating "black box" inputs.
3. Derivative Overlay: Demonstrates a replicable method to integrate nonlinear derivatives (options) into a linear mean–variance scaffold via Delta mapping, including robustness checks (bump tests) for approximation errors.
4. Stochastic Validation: Shifts the evaluation metric from "best Sharpe ratio" to stability and convergence, proving that heuristic credibility depends on median performance and runtime profiling.
5. Dependence Diagnostics: Uses eigenvalue concentration and correlation heatmaps to explain why certain high-beta industries cluster in optimal solutions under single-index constraints.

4. Key Results

• Efficient Frontiers: The cardinality constraint ($K=10$) creates a discontinuous efficient frontier compared to the unconstrained convex case. The attainable risk-return space is significantly compressed.
• Heuristic Performance:
  • Monte Carlo and Genetic Algorithms achieved a Best Sharpe Ratio of ~0.088.
  • Stability: The median Sharpe across 10 seeds was highly stable (0.086–0.088), with narrow interquartile ranges, indicating robust convergence.
  • Optimality Gap: On the reduced benchmark ($n=20, K=6$), both MC and GA found the exact global optimum (0.088003), validating their efficacy for moderate-scale problems.
• Derivative Impact:
  • Adding a call option increased portfolio volatility ($\sigma_p$) and expected return ($\mu_p$) due to leverage but did not automatically improve the Sharpe ratio.
  • Delta Approximation: Bump tests ($\pm 1\%$ underlying move) showed relative errors $< 0.1\%$, confirming Delta-linearization is adequate for small moves but warns of Gamma risks for larger shocks.
• Computational Scaling:
  • Runtime scales linearly with effort budget (samples for MC, $P \times G$ for GA).
  • Greedy is instantaneous; MC and GA take seconds to minutes, offering a clear "cost vs. performance" trade-off.

5. Significance and Conclusion

The paper successfully bridges financial theory, computational complexity, and scientific reproducibility.

• Theoretical: It confirms that while the P vs NP divide prevents scalable exact solutions for large $n$, practical investment constraints can be managed effectively using distributionally validated heuristics.
• Practical: It provides a template for institutional investors to construct sparse portfolios with derivative overlays while maintaining auditability.
• Methodological: It sets a new standard for computational finance research by demanding seed logging, convergence curves, and small-n exact benchmarks, moving the field away from "cherry-picked" best-run results.

Limitations & Future Work: The study relies on CAPM-implied returns (not realized) and a single-index covariance model. Future research should incorporate multi-factor models, realized return data for out-of-sample testing, and full non-linear derivative dynamics (Gamma/Vega).