P vs NP Problem in Portfolio Optimization: Integrating the Markowitz-CAPM Framework with Cardinality Constraints and Black-Scholes Derivative Pricing
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917348496113664 |
|---|---|
| author | Gondauri, Davit |
| author_facet | Gondauri, Davit |
| contents | 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. 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. Results highlight how the cardinality constraint reshapes the attainable efficient frontier, why stability and computational-cost trade-offs matter more than single-best runs, and how common-factor dependence can limit diversification in K-sparse solutions. The study provides a reproducible template for NP-hard portfolio optimization with transparent inputs and extensible derivative overlays. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_15652 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | P vs NP Problem in Portfolio Optimization: Integrating the Markowitz-CAPM Framework with Cardinality Constraints and Black-Scholes Derivative Pricing Gondauri, Davit Econometrics Portfolio Management 90C11, 90C20, 91G10, 68Q17, 65C05 F.2.2; G.1.6; I.2.8 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. 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. Results highlight how the cardinality constraint reshapes the attainable efficient frontier, why stability and computational-cost trade-offs matter more than single-best runs, and how common-factor dependence can limit diversification in K-sparse solutions. The study provides a reproducible template for NP-hard portfolio optimization with transparent inputs and extensible derivative overlays. |
| title | P vs NP Problem in Portfolio Optimization: Integrating the Markowitz-CAPM Framework with Cardinality Constraints and Black-Scholes Derivative Pricing |
| topic | Econometrics Portfolio Management 90C11, 90C20, 91G10, 68Q17, 65C05 F.2.2; G.1.6; I.2.8 |
| url | https://arxiv.org/abs/2603.15652 |