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

Summary

This paper makes the Millennium Prize problem P vs NP operational in quantitative finance by studying cardinality-constrained portfolio selection. Starting from the convex Markowitz mean-variance program with CAPM-based expected returns (Rf plus beta times ERP), we impose a hard sparsity rule that limits the portfolio to K assets out of approximately 94 industry portfolios (Damodaran). The constraint couples discrete subset selection with continuous weight optimization, yielding a mixed-integer quadratic program and an NP-hard search space that grows combinatorially with n and K. We therefore evaluate scalable approximation schemes (greedy screening, Monte Carlo sampling, and genetic algorithms) under a replication-oriented protocol with random-seed control, distributional performance summaries (median and quantiles), runtime profiling, and convergence diagnostics. Dependence structure is documented via correlation and covariance diagnostics and positive-semidefinite checks to link algorithm behavior to the geometry implied by the risk matrix.

Plain-language summary

This paper makes the Millennium Prize problem P vs NP operational in quantitative finance by studying cardinality-constrained portfolio selection. Starting from the convex Markowitz mean-variance program with CAPM-based expected returns (Rf plus beta times ERP), we impose a hard sparsity rule that limits the portfolio to K assets out of approximately 94 industry portfolios (Damodaran). The constraint couples discrete subset selection with continuous weight optimization, yielding a mixed-integer quadratic program and an NP-hard search space that grows combinatorially with n and K. We therefore evaluate scalable approximation schemes (greedy screening, Monte Carlo sampling, and genetic algorithms) under a replication-oriented protocol with random-seed control, distributional performance summaries (median and quantiles), runtime profiling, and convergence diagnostics. Dependence structure is documented via correlation and covariance diagnostics and positive-semidefinite checks to link algorithm behavior to the geometry implied by the risk matrix.

Research problem

This paper makes the Millennium Prize problem P vs NP operational in quantitative finance by studying cardinality-constrained portfolio selection. 1 P vs NP Problem in Portfolio Optimization: Integrating the Markowitz–CAPM Framework with Cardinality Constraints and Black–Scholes Derivative Pricing Davit Gondauri, ORCID: https://orcid.org/0000-0002-9611-3688 Professor, Doctor of Business Administration, Business & Technology University, Georgia Corresponding author: Davit Gondauri, Dgondauri@gmail.com Type of manuscript: research paper Abstract This study develops an integrated economic–computational framework for portfolio construction that makes the P versus NP divide operational within a financially auditable Markowitz–CAPM setting. Because the resulting search space grows combinatorially (≈C(n,K)), the paper treats scalable optimization as an approximation problem and evaluates practical solution schemes—greedy screening, Monte Carlo sampling over K‑subsets, and genetic algorithms—under a replication‑oriented protocol with random‑seed logging, distributional performance reporting (median/IQR/quantiles), convergence/effort curves, and runtime profiling.

Methodology

To support the title's derivatives component, we add a European call option priced by the Black-Scholes model and map it into CAPM-consistent moments using delta-based linearization, validated with a bump test and moneyness/maturity sensitivity. 1 P vs NP Problem in Portfolio Optimization: Integrating the Markowitz–CAPM Framework with Cardinality Constraints and Black–Scholes Derivative Pricing Davit Gondauri, ORCID: https://orcid.org/0000-0002-9611-3688 Professor, Doctor of Business Administration, Business & Technology University, Georgia Corresponding author: Davit Gondauri, Dgondauri@gmail.com Type of manuscript: research paper Abstract This study develops an integrated economic–computational framework for portfolio construction that makes the P versus NP divide operational within a financially auditable Markowitz–CAPM setting. To ensure empirical transparency, the asset universe is built from approximately n≈94 U.S. industry portfolios from Aswath Damodaran, using levered betas and annualized equity volatilities to calibrate expected returns via μ_i = R_f + β_i·ERP and to construct a fully reconstructible covariance matrix through a single‑index (market‑model) structure. To support financial realism beyond linear assets, the framework is extended to a derivative‑augmented universe by embedding a Black–Scholes European call as an additional instrument, mapped into CAPM‑consistent moments via delta‑based linearization and validated by moneyness–maturity robustness and a bump test (delta vs. repricing). Keywords: P vs NP; Cardinality‑constrained portfolio optimization; Mixed‑integer quadratic programming (MIQP); Markowitz mean–variance; CAPM calibration; Damodaran industry portfolios; Single‑index covariance model; Efficient frontier approximation; Genetic algorithm; Monte Carlo sampling; Reproducibility and seed control; Black–Scholes option overlay; Delta mapping and bump test; Correlation diagnostics and eigenvalue concentration.

Main findings

We therefore evaluate scalable approximation schemes (greedy screening, Monte Carlo sampling, and genetic algorithms) under a replication-oriented protocol with random-seed control, distributional performance summaries (median and quantiles), runtime profiling, and convergence diagnostics. Because the resulting search space grows combinatorially (≈C(n,K)), the paper treats scalable optimization as an approximation problem and evaluates practical solution schemes—greedy screening, Monte Carlo sampling over K‑subsets, and genetic algorithms—under a replication‑oriented protocol with random‑seed logging, distributional performance reporting (median/IQR/quantiles), convergence/effort curves, and runtime profiling. Results demonstrate that (i) the hard cardinality rule materially reshapes attainable efficient frontiers and induces discontinuities relative to the unconstrained benchmark; (ii) heuristic performance must be assessed by stability and compute‑cost trade‑offs rather than single best‑run outcomes; and (iii) under a single‑index covariance, strong common‑factor dependence limits diversification, explaining why high‑β industries and clustered sectors may co‑appear in K‑sparse solutions. This paper uses that tension as its organizing principle: it treats cardinality‑constrained portfolio selection as a concrete instantiation of the P vs NP divide, and then demonstrates how a journal‑grade empirical workflow can be built around it—transparent inputs, auditable covariance construction, reproducible stochastic search, and diagnostics that connect algorithmic behavior to the underlying dependence structure. In this document’s design, CAPM is used as an auditable, reconstructable prior for μ, not as a claim of realized performance.

Key contributions

Limitations

• 3.3 Covariance and correlation construction (single-index Σ) Because the beta table typically does not provide industry return time series, Σ is constructed via a single- index (market model) approach: R_i = α_i + β_i R_m + ε_i, E[ε_i]=0, Cov(ε_i, R_m)=0 (3.2) Cov(R_i, R_j) = β_i β_j Var(R_m) for i≠j (3.3) The diagonal is matched to Damodaran’s total risk σ_i: Var(R_i) = σ_i^2 = β_i^2 Var(R_m) + σ^2_{ε,i} (3.4) σ^2_{ε,i} = max(0, σ_i^2 − β_i^2 σ_m^2) (3.5) Here σ_m denotes market volatility.
• Note: with CAPM- implied μ, shifting Rf alone does not change Sharpe because (μ−Rf) scales with β·ERP.
• 4.2 Using Heuristic Algorithms for Portfolio Optimization 4.2.1 Monte Carlo search as an approximation scheme 19 Monte Carlo sampling does not guarantee optimality but provides a practical approximation to the efficient frontier.
• Case Asset Weight β μ (CAPM) A Auto & Truck 0.263 1.456 0.101 A Engineering/Construction 0.255 1.210 0.091 A Steel 0.211 1.063 0.085 B Option (Call overlay on Software (Internet)) 0.669 6.430 0.312 B Financial Svcs. (Non- bank & Insurance) 0.138 0.970 0.081 B Brokerage & Investment Banking 0.059 1.171 0.089 Note: Under CAPM-implied μ and a single-index Σ, delta-implied leverage can raise both μ and σ substantially; Sharpe does not necessarily increase.
• Continuous re-optimization step (subset fixed → weights optimized) To avoid the ‘equal-weight only’ limitation in the GA stage, we apply a continuous refinement step after GA selects a subset.
• CAPM‑implied μ is a model‑based expectation, not realized return; the single‑factor Σ simplifies a multi‑factor reality; delta‑only option embedding does not capture the full spectrum of nonlinearity; and heuristics do not guarantee global optimality.

Future work

• Future research directions follow naturally from the presented results. (1) Alternative estimation of Σ (multi‑factor models, shrinkage covariance, or empirical correlations from historical return series) is necessary to assess the dependence of the conclusions on one‑factor geometry. (2) Extending the derivative layer with gamma/vega components and tail‑risk metrics (e.g., CVaR/EVaR) would enable a more realistic integration of nonlinear payoffs. (3) Applying modern MIQP branch‑and‑bound/cutting‑plane strategies to small‑to‑medium instances—paired with explicit optimality‑gap reporting relative to heuristics—would further strengthen optimality evidence. (4) Finally, moving to realized return data and conducting out‑of‑sample evaluation would bridge model‑implied Sharpe proxies to realized performance.

Models and methods

Datasets

Evaluation metrics

Keywords