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

1. 연구 배경 및 문제 정의 (Problem Definition)

• 핵심 문제: 전통적인 마코비츠 (Markowitz) 평균 - 분산 포트폴리오 최적화 문제는 볼록 (convex) 최적화 문제로, 다항 시간 내에 해결 가능합니다. 그러나 실제 기관 투자자들은 포트폴리오 내 자산의 수를 제한하는 카디널리티 제약 (Cardinality Constraint, $|supp(w)| \le K$) 을 부과합니다.
• 복잡도 도약: 이 제약은 연속적인 가중치 최적화와 이산적인 자산 선택 (Subset Selection) 을 결합하여 문제를 혼합 정수 2 차 계획법 (MIQP) 으로 변환시킵니다. 이는 NP-난해 (NP-hard) 문제 클래스에 속하며, 최악의 경우 $C(n, K)$ 개의 조합을 탐색해야 하므로 대규모 $n$ (자산 수) 에 대해 전역 최적해를 찾는 것이 계산적으로 불가능합니다.
• 연구 목적: 본 연구는 이 계산적 난이도 (P vs NP 문제) 를 금융 실증 분석에 적용하여, 제약 조건 하에서 효율적 프론티어를 어떻게 근사할 수 있는지, 그리고 파생상품을 포함한 현실적인 포트폴리오 구성이 어떻게 복잡성과 계산 비용에 영향을 미치는지를 규명하는 것을 목표로 합니다.

2. 방법론 (Methodology)

연구는 투명하고 재현 가능한 (reproducible) 실증 프레임워크를 구축하는 데 중점을 두었습니다.

가. 데이터 및 입력값 (Data & Calibration)

• 자산 우주: Aswath Damodaran 의 약 94 개 미국 산업 포트폴리오를 사용 ($n \approx 94$).
• 기대 수익률 ($\mu$): CAPM(자본자산가격결정모형) 을 기반으로 산출.
  • 공식: $\mu_i = R_f + \beta_i \cdot ERP$ (무위험이자율 + 베타 $\times$ 시장위험프리미엄).
• 공분산 행렬 ($\Sigma$): 단일 지수 모델 (Single-index model) 을 사용하여 구성.
  • 시장 모델: $R_i = \alpha_i + \beta_i R_m + \epsilon_i$.
  • 공분산 구조: $Cov(R_i, R_j) = \beta_i \beta_j Var(R_m)$ (상관관계는 베타에 의해 주도됨).
  • 이 접근법은 원시 수익률 시계열 없이도 $\Sigma$ 와 $\rho$ 행렬을 감사 가능한 입력값 (베타, 변동성) 에서 완전히 재구성할 수 있게 합니다.

나. 최적화 모델 (Optimization Model)

• 목적 함수: 위험 ($\sigma_p^2$) 최소화 또는 샤프 비율 최대화.
• 제약 조건:
  • 예산 제약 ($\sum w_i = 1$), 비음수 제약 ($w_i \ge 0$).
  • 카디널리티 제약: 선택된 자산의 개수 $K$ (예: $K=10$).
  • 이진 선택 변수 $z_i$ 와 가중치 $w_i$ 의 결합 ($w_i \le u_i z_i$).

다. 알고리즘 및 해법 (Algorithms)

전역 최적해가 불가능하므로, 다양한 휴리스틱 (Heuristic) 및 메타휴리스틱 기법을 비교 평가했습니다.

1. Greedy (탐욕적 알고리즘): CAPM 샤프 비율 등으로 순위를 매겨 상위 $K$ 개를 선택.
2. Monte Carlo Sampling: 무작위로 $K$ 개의 부분집합을 추출하고, 그 안에서 가중치를 최적화 (Dirichlet 분포 등) 하여 샤프 비율이 높은 포트폴리오를 선별.
3. Genetic Algorithm (GA): 부분집합 선택을 염색체로 인코딩하여 진화 연산 (선택, 교차, 변이) 을 수행. 선택된 부분집합 내에서 가중치를 다시 최적화 (Continuous Re-optimization) 하는 2 단계 방식을 사용.
4. 정확한 벤치마크 (Exact Benchmark): $n=20, K=6$ 과 같은 축소된 사례에서 전수 조사 (Full Enumeration) 를 통해 휴리스틱의 오차 (Gap) 를 검증.

라. 파생상품 통합 (Derivative Integration)

• 블랙 - 숄즈 (Black-Scholes) 모델: 유럽형 콜옵션을 포트폴리오에 추가.
• 델타 기반 선형화 (Delta-based Linearization): 옵션을 선형 자산으로 근사화하여 평균 - 분산 프레임워크에 통합.
  • 옵션의 베타 ($\beta_{opt}$) 와 변동성 ($\sigma_{opt}$) 을 레버리지 계수 $L = (\Delta \cdot S_0) / C$ 를 통해 기초자산의 값에 매핑.
  • Bump Test: 델타 근사의 정확도를 검증하기 위해 기초자산 가격 변동 ($\pm 1\%$) 에 따른 재가격 (Repricing) 오차를 분석.

3. 주요 결과 (Key Results)

가. 계산 복잡도 및 휴리스틱 성능

• 효율적 프론티어 변화: 카디널리티 제약은 비제약 포트폴리오의 프론티어와 비교하여 불연속적인 구조를 만들고, 달성 가능한 위험 - 수익 영역을 제한합니다.
• 휴리스틱 평가: 단일 "최고 결과 (Best Run)"보다는 중앙값 (Median), 사분위수 (IQR), 분포를 통한 재현성 있는 평가가 필수적입니다.
  • Monte Carlo 와 GA 는 여러 시드 (Seed) 를 통해 실행 시 안정성을 보였으며, GA 에 연속 최적화를 결합하면 성능이 향상되었습니다.
  • 축소된 사례 ($n=20$) 에서 휴리스틱은 전수 조사 결과와 거의 동일한 샤프 비율 (약 0.088) 을 달성하여 실용적 유효성을 입증했습니다.

나. 의존성 구조의 영향 (Dependence Diagnostics)

• 단일 지수 모델의 한계: 단일 지수 모델은 높은 공통 요인 (시장) 의존성을 가정합니다.
  • 결과: 중간 상관관계 (Median $\rho$) 가 약 0.77 로 매우 높고, 첫 번째 고유값 (Eigenvalue) 이 전체 분산의 약 76% 를 설명합니다.
  • 시사점: 이러한 강한 상관관계는 분산 투자 효과를 제한하며, 고베타 산업군이 K-희소 (K-sparse) 포트폴리오에 함께 선택되는 경향을 설명합니다.

다. 파생상품 통합 결과

• 레버리지 효과: 옵션을 추가하면 기대수익률 ($\mu$) 과 위험 ($\sigma$) 이 모두 급격히 증가합니다.
• 샤프 비율: 높은 레버리지로 인해 샤프 비율이 자동으로 향상되는 것은 아니며, 오히려 위험 증가로 인해 샤프 비율이 하락하거나 변동성이 커질 수 있습니다.
• 근사 정확도: 델타 기반 선형화는 소폭의 가격 변동 (Bump test) 에서 매우 높은 정확도를 보였으나, 감마 (Gamma) 나 베가 (Vega) 효과가 중요한 상황에서는 한계가 있음을 확인했습니다.

4. 주요 기여 (Key Contributions)

1. 복잡도 이론의 실증적 적용: 포트폴리오 최적화 문제를 P vs NP 관점에서 명확히 정의하고, NP-난해 문제로서의 특성을 금융 실증 데이터로 검증했습니다.
2. 재현 가능한 실증 백본 (Replicable Backbone): Damodaran 의 데이터를 기반으로 CAPM 과 단일 지수 모델을 사용하여, 외부 데이터 없이도 공분산 행렬과 기대수익률을 완전히 재구성할 수 있는 감사 가능한 (Auditable) 프레임워크를 제시했습니다.
3. 휴리스틱 평가 기준의 정립: 단일 최적값 보고를 지양하고, 다중 시드 (Multi-seed) 에 따른 분포 통계 (중앙값, IQR) 와 수렴 곡선 (Convergence curves) 을 통한 안정성 평가를 표준으로 제시했습니다.
4. 파생상품 통합의 재현성: 블랙 - 숄즈 옵션을 델타 매핑을 통해 평균 - 분산 모델에 통합하는 구체적인 사례를 제시하고, 근사 오차를 검증하는 방법론을 확립했습니다.
5. 의존성 진단 도구: 알고리즘의 출력이 단순한 숫자가 아니라, 공분산 행렬의 기하학적 구조 (상관관계, 고유값 집중도) 와 어떻게 연결되는지를 설명하는 진단 지표를 제공했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 학문적 의의: 이 연구는 금융 이론 (Markowitz-CAPM), 계산 복잡도 이론 (P vs NP), 그리고 계산 실험 (Heuristics) 을 통합한 체계적인 연구 모델을 제시합니다. 이는 포트폴리오 최적화가 단순한 계산 문제가 아니라, 제약 조건 하에서의 NP-난해 문제임을 실증적으로 보여줍니다.
• 실무적 시사점: 기관 투자자들이 직면한 현실적인 제약 (자산 수 제한, 파생상품 포함) 하에서 최적의 포트폴리오를 찾는 과정이 "전역 최적해"를 찾는 것이 아니라, "계산 비용과 성능의 트레이드오프"를 관리하는 과정임을 강조합니다.
• 한계 및 향후 연구: CAPM 기반 기대수익률의 모델 의존성, 단일 지수 모델의 단순화, 델타 근사의 한계 등을 인정하며, 향후 다요인 모델, 비선형 리스크 지표 (CVaR 등) 적용, 그리고 실수익률 데이터에 대한 아웃 - 오브 - 샘플 검증이 필요함을 제언합니다.

요약하자면, 본 논문은 카디널리티 제약이 포트폴리오 최적화를 NP-난해 문제로 전환시키는 메커니즘을 규명하고, 이를 해결하기 위한 투명하고 재현 가능한 휴리스틱 접근법과 파생상품 통합 기법을 제시함으로써, 현대 포트폴리오 이론과 계산 과학의 교차점에서 중요한 방법론적 기여를 하고 있습니다.