💰 quantitative finance

A novel robust mixed integer linear programming model for index tracking problem under no rebalancing: heuristic optimization approach

본 논문은 리밸런싱이 없는 상황에서의 인덱스 추적 문제를 위한 새로운 강건한 혼합 정수 선형 계획 모델을 제 제안하며, 이와 함께 NP-난해 문제를 효율적으로 해결하고 표본 내 및 표본 외 데이터 모두에서 상용 솔버보다 우수한 성능을 보이는 유전 알고리즘과 국소 탐색 능력을 결합한 하이브리드 휴리스틱 알고리즘을 제시한다.

원저자: Danial Ramezani, Mostafa Abouei Ardakan, Mohamadreza Dehghani Ahmadabad

게시일 2026-07-13

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Danial Ramezani, Mostafa Abouei Ardakan, Mohamadreza Dehghani Ahmadabad

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

거대하고 혼란스러운 오케스트라의 축소판을 만들려고 한다고 상상해 보십시오. 당신의 목표는 수백 개의 악기 중 단 몇 개(예를 들어 10개)만을 골라, 그것들이 함께 연주될 때 전체 교향곡과 똑같이 들리도록 하는 것입니다. 금융 세계에서 이것은 **인덱스 트래킹(Index Tracking)**이라고 불립니다. 시장에 있는 모든 주식을 사는 대신(비용이 많이 들고 복잡하기 때문입니다), 펀드 매니저들은 시장의 성과를 완벽하게 모방하는 작은 "추적 포트폴리오"를 선정하고자 합니다.

오랫동안 매니저들은 바이올린과 첼로가 항상 같은 음을 연주하는지 확인하는 것처럼, 과거에 주식들이 서로 얼마나 유사했는지를 살펴보며 이 작업을 수행해 왔습니다. 하지만 이 논문의 저자인 다니엘 라메자니(Danial Ramezani)와 그의 팀은 그러한 접근 방식이 마치 어제의 구름만 보고 내일의 날씨를 예측하려는 것과 같다고 말합니다. 그것은 너무 불안정합니다. 그들은 단순한 과거 상관관계에 의존하는 것이 노이즈가 많으며, 시장의 분위기가 바뀔 때 종종 실패한다고 주장합니다.

새로운 "강건한(Robust)" 레시피
연구팀은 "강건한" 새로운 수학적 레시피(모델)를 제안했습니다. 이것은 단순히 잔잔한 물 위에서 뜨는 배가 아니라, 최악의 폭풍 속에서도 살아남을 수 있도록 설계된 배를 만드는 것과 같습니다. 어떤 주식이 시장과 일치할지 단순히 추측하는 대신, 그들의 모델은 다음과 같이 묻습니다: "만약 이 주식들 사이의 관계가 잘못된다면? 만약 그들이 최악의 모습으로 행동한다면?" 최악의 시나리오를 계획함으로써, 이 모델은 상황이 엉망이 될 때조차 안정적으로 유지되는 자산 그룹을 선택합니다.

그들은 또한 수학에 특별한 "안전 버퍼"를 도입했습니다. 비가 올지 해가 뜰지 확실하지 않은 여행을 위해 짐을 싸는 상황을 상상해 보십시오. 일반적인 짐꾼은 그저 추측할 뿐입니다. 이 새로운 모델은 비와 햇빛 모두를 위해 짐을 싸서, 어떤 일이 일어나더라도 필요한 것을 갖출 수 있도록 보장합니다. 이러한 접근 방식은 포트폴리오가 지속적인 조정(리밸런싱) 없이도 오랫동안 시장을 추적할 수 있게 해주며, 이는 거래 비용을 절감해 줍니다.

슈퍼 탐색 팀 (GALB)
여기서 까다로운 부분이 있습니다. 수백 개 중 완벽한 10개의 악기를 찾는 것은 너무나 거대한 퍼즐이라서, CPLEX와 같은 세계에서 가장 빠른 슈퍼컴퓨터(정확한 솔버, Exact Solvers)조차 길을 잃거나 해결하는 데 영원히 걸릴 수 있습니다. 이 문제는 "NP-hard"한데, 이는 미로에 막다른 길이 너무 많아 빠져나가기 어려운 상태를 뜻하는 전문 용어입니다.

이를 해결하기 위해 저자들은 GALB라는 새로운 탐색 팀을 만들었습니다. GALB는 하이브리드 탐정이라고 생각할 수 있습니다.

유전 알고리즘 (Genetic Algorithm, GA): 이 부분은 사방으로 달려가는 탐험가 무리와 같습니다. 그들은 다양한 주식 조합을 시도하며 빠르고 흥미로운 경로를 찾아내는 데 능숙합니다.
로컬 브랜칭 (Local Branching): 이것은 "확대/축소" 전문가입니다. 탐험가들이 유망한 지점을 발견하면, 이 전문가는 멈춰 서서 그 주변을 아주 면밀히 살펴보고, 해결책을 아주 조금씩 수정하여 완벽하게 만들 수 있는지 확인합니다.

이 "넓은 탐색"의 탐험가들과 "정밀 검사"의 전문가를 결합함으로써, GALB는 느리고 무식한 힘을 쓰는 컴퓨터보다 훨씬 빠르게 고품질의 솔루션을 찾아냅니다.

숫자가 말해주는 것
팀은 그들의 새로운 모델과 GALB 탐색 팀을 기존 방식 및 초고속 CPLEX 컴퓨터와 비교하여 다우 존스(Dow Jones), 항셍(Hang Seng), DAX, FTSE 100, S&P 100, **닛케이 225(Nikkei 225)**와 같은 유명한 시장 데이터를 통해 테스트했습니다.

속도: 이 테스트에서 CPLEX 컴퓨터는 일부 시장에 대해 문제를 해결하려고 최대 1,800초(30분)까지 소요되었으며, 때로는 최선의 답을 찾지 못한 채 포기하기도 했습니다. 반면, GALB 팀은 작은 시장에서는 단 120초, 큰 시장에서도 300초 만에 훌륭한 솔루션을 찾아냈습니다.
정확도: GALB가 만든 포트폴리오는 빠르게 답을 찾을 뿐만 아니라, 더 나은 답을 찾아냈습니다. 팀이 미래 데이터(out-of-sample data)를 통해 포트폴리오의 성과를 확인했을 때, 새로운 모델은 일관되게 더 낮은 오차를 보였습니다. 예를 들어, 다우 존스 테스트에서 새로운 모델의 추적 오차(MAD)는 기존의 모델 3이 보여준 0.00458에 비해 0.00402를 기록했습니다.
안정성: 그들이 구축한 포트폴리오는 수백 개의 가용 자산 중 단 10개의 자산으로 구성되었습니다. 이 작은 규모에도 불구하고, 이들은 끊임없이 재배치할 필요 없이 장기간 동안 거대 시장을 성공적으로 추적했습니다.

그것이 '아닌' 것들
저자들은 자신들의 방식이 무엇이 아닌지를 명확히 밝히며 주의를 기울입니다. 그들은 주식의 과거 상관관계만을 보고 미래를 예측할 수 있다는 생각에 대해 명시적으로 반박합니다. 그들은 "최악의 시나리오"(예: 이전의 모델 1)를 무시하는 모델들이 테스트 시에는 좋아 보일지 몰라도 실제 환경이 변할 때는 실패한다는 것을 보여줍니다. 또한 그들의 휴리스틱(GALB)이 놀랍기는 하지만, 이는 근사치(approximation)라는 점을 언급합니다. 즉, 더 짧은 시간 안에 정확한 솔버보다 "동등하거나 심지로 우수한" 솔루션을 찾아내지만, 우주의 모든 가능한 시나리오에 대해 수학적인 완벽함을 증명하는 것은 아닙니다. 다만, 테스트한 문제 규모에 대해서는 최적의 솔루션에 수렴하였습니다.

결론
이러한 시뮬레이션과 테스트를 통해, 저자들은 그들의 새로운 "강건한" 모델이 GALB 탐색 팀과 결리되어 거대 시장을 모방하는 작고 저비용인 포트폴리오를 구축하는 강력한 방법임을 시사합니다. 이 모델은 기존 방식보다 주식 시장의 혼돈을 더 잘 다루며, 추적 오차를 낮게 유지하고 값비싼 리밸런싱의 필요성을 최소화하는 것으로 보입니다. 이 논문은 이러한 결과가 여러 주요 글로벌 지수에서 유효함을 보여주지만, 저자들은 이를 모든 금융의 미스터리를 해결하는 마법의 탄환이라기보다는 강력하게 검증된 접근 방식으로 제시하고 있습니다.

기술 요약: 리밸런싱 없는 인덱스 추적을 위한 새로운 강건한 혼합 정수 선형 계획법 모델

문제 정의
본 논문은 특정 시장 벤치마크의 성과를 복제하기 위해 자산의 부분 집합을 사용하여 포트폴리오를 구성하는 핵심 과제인 인덱스 추적(Index Tracking, IT) 문제를 다룹니다. 저자들은 기존 수학적 정식화의 결정적인 한계점을 다음과 같이 식별했습니다:

상관관계에 대한 민감도: 전통적인 모델은 종종 역사적 자산 상관관계에 의존하는데, 이는 노이즈가 많고 다양한 시장 국면(regime)에 따라 불안정하며, 인샘플(in-sample) 데이터에 과적합되어 아웃오브샘플(out-of-sample) 성능이 저하될 위험이 있습니다.
리밸런싱 비용: 많은 전략은 추적 정확도를 유지하기 위해 빈번한 리밸런싱을 요구하며, 이는 상당한 거래 비용과 유동성 리스크를 발생시킵니다.
계산 복잡성: IT 문제는 자산의 부분 집합 선택과 가중치 결정이라는 조합론적 특성으로 인해 NP-hard 문제이며, 이로 인해 대규모 데이터셋에 대해 적절한 시간 내에 최적해를 찾는 것이 어렵습니다.

본 연구의 구체적인 목표는 매개변수 불확실성(특히 상관관계 편차)에 대해 **강건(robust)**하고, 리밸런싱 없이도 장기간 인덱스를 추적할 수 있으며, 새로운 휴리스틱을 통해 효율적으로 해결 가능한 모델을 개발하는 것입니다.

방법론

1. 수학적 정식화 (모델 4)
저자들은 두 가지 별개의 목적을 하나의 강건한 모델로 통합하는 새로운 혼합 정수 선형 계획법(MILP) 정식화를 제안합니다:

상관관계 불확실성을 통한 강건성: Bertsimas와 Sim (2003)의 강건 최적화 접근법을 활용하여, 모델은 자산 상관관계에 대한 "최악의 시나리오"를 포함합니다. 이는 상관관계가 불리하게 변하더라도 포트폴리오가 효과적으로 유지되도록 상관관계의 하락 편차( $\Gamma$ 계수가 최악의 값을 갖는 경우)를 최소화합니다.
추적 오차 최소화: 모델은 포트폴리오 수익률과 벤치마크 인덱스 수익률 사이의 평균 절대 편차(MAD)를 동시에 최소화합니다.
제약 조건: 정식화에는 카디널리티(자산 수 제한, $K$ ), 바이인(buy-in) 임계값(최소 및 최대 가중치), 공매도 금지 등 표준적인 실무 제약 조건이 포함됩니다.
목적 함수: 목적 함수(식 19)는 추적 오차 항과 강건한 상관관계 항을 결합하며, 값을 0과 1 사이로 정규화하기 위해 계수 $\xi$ 와 $\psi$ 를 사용합니다.

2. 해결 방법: GALB 휴리스틱
정확한 솔버(exact solver)가 더 큰 규모의 문제에서 어려움을 겪는다는 점을 인식하여, 저자들은 **GALB (Genetic Algorithm with Local Branching)**라는 하이브리드 메타휴리스틱을 개발했습니다:

유전 알고리즘 (GA): 교차(crossover) 및 변이(mutation) 연산자를 사용하여 후보 솔루션(포트폴리오)의 집단을 진화시키는 전역 탐색 엔진 역할을 합니다.
로컬 브랜칭 (Local Branching): 로컬 탐색 메커니즘으로 통합되었습니다. 특정 조건(예: 개선 없이 일정 횟수의 GA 반복 발생 시)이 충족되면, 알고리즘은 현재 최적해 주변의 해밍 거리(Hamming distance) 이웃을 정의하고 제한된 MILP 부문제(sub-problem)를 풀어 근처의 솔루션을 더 깊이 탐색합니다.
적합도 함수 (Fitness Function): 매 단계마다 정확한 솔버를 실행하는 계산적 오버헤드 없이 솔루션을 평가하도록 설계된 특화된 적합도 함수(알고리즘 2)를 사용합니다. 이 함수는 자산 가중치를 디코딩하고 최악의 상관관계 시나리오를 효율적으로 처리하며 직접적으로 강건한 목적 함수 값을 계산합니다.

실험 설정
연구에는 Dow Jones, Hang Seng, CAC 40, EURO STOXX 50, DAX, FTSE 100, S&P 100, Nikkei 225 등 8개의 주요 시장 데이터가 사용되었습니다. 데이터 소스는 OR-library와 Yahoo Finance(2018년 7월 ~ 2024년 1월)를 포함합니다.

비교 대상: 제안된 모델 4와 GALB는 다음 모델들과 비교되었습니다:
- 기존 정식화 (상관관계 극대화 기반의 모델 1, MAD 최소화 기반의 모델 3).
- 상용 정확한 솔버인 CPLEX.
지표: 성능은 상관계수( $\rho$ ), 평균 절대 편차(MAD), 평균 제곱근 오차(RMSE), 추적 오차의 표준편차(STD), 그리고 베타(Beta)를 사용하여 평가되었습니다. 인샘플 및 아웃오브샘플 결과가 모두 분석되었습니다.
매개변수: 실험에서는 다양한 불확실성 수준( $\Gamma = 0, 50\%, 75\%, 90\%$ )을 테스트하였으며, 포트폴리오 크기는 10개( $K=10$ )로 고정하였습니다.

주요 결과

1. 강건한 정식화의 우수성:

CPLEX로 풀었을 때, 제안된 모델 4는 테스트된 모든 시장(Dow Jones, CAC 40, EURO STOXX 50)에서 아웃오브샘플 지표에 대해 모델 1 및 모델 3보다 일관되게 우수한 성능을 보였습니다.
구체적으로, 모델 4는 아웃오브샘플 기간 동안 인덱스와 더 높은 상관관계를 달성하고 더 낮은 추적 오차(MAD, RMSE, STD)를 기록하여, 시장 국면 변화에 대한 강건성을 입증했습니다.
계산 효율성 측면에서, CPLEX는 여러 시장(예: Dow Jones의 경우 72초 vs 118초)에서 제안된 모델을 모델 3보다 더 빠르게 해결했습니다.

2. GALB 휴리스틱의 성능:

효율성: GALB는 CPLEX보다 훨씬 적은 시간 내에 동등하거나 더 우수한 품질의 솔루션을 찾아냈습니다 (예: Dow Jones의 경우 120초 vs 1800초; 기타 시장의 경우 300초 vs 1800초).
최적성: 작은 규모의 문제에 대해, 특히 $\Gamma=0$ 일 때 GALB는 많은 실행에서 전역 최적해에 수렴하였습니다 (CPLEX와 동일한 결과).
아웃오브샘플 지배력: 대부분의 시장(Hang Seng, DAX, Nikkei 225, S&P 100)에서 GALB가 생성한 포트폴리오(특히 $\Gamma=75\%$ 또는 $90\%$ 인 경우)는 CPLEX가 더 많은 시간을 투입했음에도 불구하고 더 나은 아웃오브샘플 추적 성능을 보였습니다.
리밸런싱 없음: 단 10개의 자산으로 구성된 결과 포트폴리오는 장기간 동안 최소한의 편차로 인덱스를 추적하여 "리밸런싱 없음"의 주장을 검증했습니다.

의의 및 주장
본 논문은 다음과 같은 두 가지 기여를 주장합니다:

강건한 정식화: 기존 IT 모델보다 더 강건하며, 상관관계 불측성을 처리하고 잦은 리밸런싱 없이도 우수한 아웃오브샘플 성능을 제공할 수 있는 MILP 모델을 도입했습니다.
강력한 휴리스틱: 전역 탐색(GA)과 지역 탐색(Local Branching)을 효과적으로 균형 있게 결사한 하이브리드 알고리즘인 GALB를 제시합니다. 저자들은 GALB가 상용 솔버보다 NP-hard IT 문제를 더 빠르게 해결할 뿐만 아니라, 실제 추적 정확도 측면에서 정확한 솔버의 솔루션보다 더 뛰어난 포트폴리오를 생성한다고 주장합니다.

본 연구는 제안된 접근 방식이 (Nikkei 225와 같이) 변동성이 큰 대형 인덱스를 장기간 동안 높은 상관관계로 추적할 수 있는 경량 포트폴리오(최소 10개 자산)를 구축할 수 있게 하여, 회전율 및 리밸런싱과 관련된 관리 비용을 효과적으로 줄일 수 있다고 결론짓습니다.

유사한 논문