최적화알고리즘과투자공학 서울대학교컴퓨터공학부 최적화및금융공학연구실 문병로 서울대학교최적화및금융공학연구실 page 1
목차 1. 도입, 문제공간 2. 최적화 3. 증권시장과최적화 4. 결론 서울대학교최적화및금융공학연구실 page 2
1. 도입 서울대학교최적화및금융공학연구실 page 3
Motivations for Optimization 기능의시대에서효율성의시대로! 효율지향솔루션시장의확대 금융 자원관리 제조 CRM ( 고객관계관리 ) SCM ( 공급망관리 ) 광고 검색 수요는급증, 방법론은정체 기법상의심층적변혁필요 서울대학교최적화및금융공학연구실 page 4
Company Intelligence Level Building Blocks Basic products Research Intellectual building blocks Outsourcing capability HIGH Transforming Level Abstraction Level Emergent behaviors Scratch Level Labor-oriented projects LOW LOW Environment Technology Culture Costomer s Royalty HIGH 서울대학교최적화및금융공학연구실 page 5
문제공간탐색 Problem space 2-D 3-D N-D? f(x) =. f(x,y) =. f(x 1,x 2,,x N-1 ) =. 서울대학교최적화및금융공학연구실 page 6
축구경기를문제공간탐색의관점에서보면.. 100ⅹ70 서울대학교최적화및금융공학연구실 문제공간크기 7000 P 23 > (10 12 ) 7 page 7
서울대학교최적화및금융공학연구실 page 8
Problem State Space 1 node / state #nodes > (10 12 ) 7 서울대학교최적화및금융공학연구실 page 9
Clustering N 개의개체들을서로관계가최소인 K 그룹으로나누기 대표적난제 Cost = 관계정도 균형정도 문제공간크기는 2 N-1 A B 서울대학교최적화및금융공학연구실 page 10
문제공간 각격자점하나는하나씩의솔루션 최적화 - 문제공간에서가장높은봉우리를찾는것 대부분문제공간은 N차원이다. 서울대학교최적화및금융공학연구실 page 11
문제공간의크기 앞의고객 clustering 문제 2 N-1 고객의수가대략 250 명정도되면앞의축구문제와비슷한크기의문제공간을가진다 인터넷사이트들의고객수는 10 만 ~ 수천만 모든경우를다따져보려면? 수조몇천년 효율적알고리즘필요 서울대학교최적화및금융공학연구실 page 12
Attractors Attractor = 끌개 문제공간상에서의지역최적점 공간탐색의목표이자장애물 끌개의예 생태계의종 : 개나리, 질경이, 치타, 가젤, 인류사의조직, 제도 : 가족, 부족, 국가, 학교, 대통령제, 인간의고정관념, 사고체계 : 시각, 습관, 편집증, 시장에서정착되는제품들 타게팅엔진이생산하는솔루션집합 테니스의스윙폼 Optimization 은가장수준높은끌개를찾는것 저수준끌개 (low-quality local optimum) 에고착되어버리지않도록 다양한끌개에접할수있도록넓은탐색기능필요 서울대학교최적화및금융공학연구실 page 13
2. 최적화 서울대학교최적화및금융공학연구실 page 14
문제를푼다는것 Decision problems 질문에대해 Yes 또는 No라고대답하면되는문제 Equations 조건을만족하는해를찾는것 유효한해의수는많지않다 ( 대부분 ) Optimization 유효한해는무수히많다 이들중가장매력적인해를찾는것 서울대학교최적화및금융공학연구실 page 15
Types of Optimization Problems Function optimization 주어진함수값을최대화 / 최소화하는변수값찾기 System identification 주어진입력 - 출력집합을가장잘설명하는시스템찾기 Function approximation, Neural-network optimization, 투자전략, Combinatorial optimization 이산적해들의집합에서가장매력적인해를찾는것 그래프분할, TSP, 차량라우팅, VLSI 회로배치, 벡터양자화, 전략최적화, 서울대학교최적화및금융공학연구실 page 16
System Identification Determines a mathematical model for an unknown system by observing input-output pairs Applications 원자력발전소 1-To-1 타게팅 Function approximation Neural-net identification Decision circuit 최적디자인 Areas 금융 e-commerce Search Regression Analysis GA TS Heuristics IO Pairs Approximation Target system Modeling & Extraction Information Function NN Circuit Log data 서울대학교최적화및금융공학연구실 page 17
Optimization Problems Function optimization 함수의최적해탐색, 방정식근사, System identification Mostly black-box models» 신경망디자인, 함수근사,» 문자인식, 질병예측, 사기진단, 주가예측, 투자전략,» Decision logic, 다중엘리베이터최적제어, 핵연료상관식디자인, Combinatorial optimization TSP, 차량라우팅, 스케줄링 시재관리최적화, 공정-장비할당최적화 그래프분할, VLSI 회로배치 벡터양자화 투자전략, 게임전략, 서울대학교최적화및금융공학연구실 page 18
Optimization Methods Deterministic algorithms Local search algorithms Greedy algorithms Heuristics Linear programming Dynamic programming Neural net Stochastic approaches Genetic algorithm, LSMC, tabu search, 서울대학교최적화및금융공학연구실 page 19
Obstacles 시간의제한 Hierarchical model 필요 경험적직관필요 Abstraction, articulation, event화 Dream: Raw data로부터바로시스템도출» 시스템의복잡성으로인해대부분가능하지않다 Articulation 필요 서울대학교최적화및금융공학연구실 page 20
Application Examples Local search algorithms LP 시재관리시스템, 택배스케줄링, 자원할당, 금융포트폴리오, 공정 / 장비할당, Dynamic programming 금융포트폴리오, 멀티캠페인할당, Neural net 주식시계열예측, 문자인식, Genetic algorithm 원자핵발전소연료디자인, 광고최적타게팅, 금융포트폴리오, 투자전략, 서울대학교최적화및금융공학연구실 page 21
3. 증권시장과최적화 서울대학교최적화및금융공학연구실 page 22
미국기업주가와관련지표추이 서울대학교최적화및금융공학연구실 page 23
Algorithm Trading 현황 2006 년의 algorithm trading 비중 EU 와미국주식거래의 1/3 외환거래주문의 1/4 런던주식거래소주문의 40% 2010 년의 algorithm trading 비중 ( 예상, Aite Group LLC) EU 와미국주식거래의 ½( 이미 2009 년미국주식거래의 73% 가 high-frequency trading 회사들의주문 ) 옵션거래의 1/5 급격한변화 (2005 2006) Avg deal size: 1000 shares -> 300 shares Trading volume: 0.35billion 1.6 billion Algorithms and quantitative techniques multiplied, it became arms race. 11/2006 Herald Tribune Goldman has more people working in their technological area than people on the trading desk. The nature of the market has changed dramatically. 7/2007 AP ATD 자동거래전문회사 미국거래의 6% 점유 City Group 이 6.8 억불에인수 Nova Fund (Renaissance Technologies) Algorithm trading fund 97 년어느날 NASDAQ 전체거래의 14% 차지 2014 년에는 80~90%? Any sort of pattern recognition or predictive model can be used to initiate algorithm trading. Neural net and genetic programming have been used to create these models. Now it s an arms race, said Andrew Lo, director of the MIT s Laboratory for Financial Engineering. -Wikipedia Quants: 금융공학적투자자를총칭 서울대학교최적화및금융공학연구실 page 24
주식관련시스템 주식투자보조시스템 주가예측, 재무적분석, 기술적분석, 자동투자시스템 Algorithm, automated, black-box trading» Open/Close» Auto portfolio rebalancing 주식, 펀드,» Scheduling(Timing) large-volume trades» Rule sets (semi-auto) 투자전략도출시스템 Trading rules» Rule generation» Combination among a rule set Risk minimization Portfolio construction Arbitrage trading Risk arbitrage Index arbitrage Pair arbitrage Value arbitrage 서울대학교최적화및금융공학연구실 page 25
간단한계량적정보 : 재무제표와수익률 1997 년 ~2007 년, 한국주식 십분위포트폴리오수익률 서울대학교최적화및금융공학연구실 page 26
PBR 십분위에따른수익률 : 1997-2007 십분위 1 (Lowest) 평균 PBR 1,000,000 Grows to: 연평균기하수익 Sharpe Ratio 0.29 11,902,094 25.25% 0.59 2 0.45 6,422,989 18.42% 0.51 * 동기간 KOSPI 연평균기하상승률 : 7.93% PBR = 시가총액 순자산 3 0.58 3,556,858 12.23% 0.32 4 0.71 5,115,234 16.00% 0.41 기하평균수익률 5 0.88 2,351,642 8.08% 0.2 6 1.05 1,508,948 3.81% 0.08 7 1.28 548,432-5.31% -0.27 8 1.6 936,806-0.59% -0.02 9 2.22 192,031-13.93% -0.38 10 (Highest) 4.61 210,947-13.19% -0.27 서울대학교최적화및금융공학연구실 page 27
미국주식의 PBR 십분위에따른수익률 : 1951-2003 십분위 1 (Lowest) 연평균기하수익 16.59% 2 15.48% 3 15.08% 4 13.98% 5 12.25% 6 11.60% 7 11.49% 8 11.35% 9 11.12% 10 (Highest) 9.26% * 동기간미국주식연평균기하수익률 : 11.7% 비교, 한국 서울대학교최적화및금융공학연구실 page 28
계량적검증, G. Morris 11/29, 1991 ~ 12/31, 2004 # of stocks: 2277 # of days: 5,490,000 S&P 500 지수 : 380 1200 패턴 빈도 %Win: 적중률수익률 : % 1 일후 5 일후 7 일후 %Win 수익률 %Win 수익률 %Win 수익률 3 White Soldiers + 2479 52% 0.18 52% 0.43 52% 0.44 3 Black Crows - 3659 49% -0.09 46% -0.73 46% -1.07 Abandoned Baby + 64 59% 0.73 56% 0.24 48% 0.81 Abandoned Baby - 44 49% 0.01 55% -0.04 53% -1.81 3 Outside Up + 16783 49% 0.05 51% 0.44 51% 0.43 3 Outside Down - 17345 48% -0.23 47% -0.60 45% -0.98 Morning Star + 1602 49% -0.02 53% 0.44 52% 0.75 Morning D. Star + 1105 47% -0.16 51% 0.25 53% 0.52 Concealing + 101 51% 0.28 50% 1.25 54% 2.31 100% 가까운적중률은있을수없다! 서울대학교최적화및금융공학연구실 page 29
Facts 총 88 패턴에대한실험에서 G. Morris 시중의믿음에대한평균적중률은고작 51% 100회이상출현패턴중 적중률 59% 이상인것은단 4개 ( 상승, 하락각 2개 ) 적중률최고치는 67% (Match High-와 Match Low+, 1일후 ) 7일내기대상승률이가장높은것은 2.31% (Concealing, 101회출현 ) 7일내기대하락률이가장낮은것은 -1.82% 적중률 50% 미만인것 ( 예측실패 ) 은 33개 백발백중은없다! 기대확률이 50% 를조금넘을뿐! 서울대학교최적화및금융공학연구실 page 30
1997 ~ 2007 # of stocks: 1668 # of days: 2,989,429 KOSPI 지수 : 651 1897 패턴빈도 계량적검증 : 한국주식 %Win: 적중률수익률 : % 1 일후 5 일후 7 일후 15 일후 %Win 수익률 %Win 수익률 %Win 수익률 %Win 수익률 모든경우 2989429 48% 0.08 48% 0.48 48% 0.67 48% 1.42 3 White Soldiers + 2466 52% 0.93 45% 1.14 45% 1.7 43% 2.4 3 Black Crows - 2684 44% 0.44 47% 1.26 48% 1.37 54% 1.08 Abandoned Baby + 20 68% 1.48 55% 1.61 40% -3.17 23% -16.6 Abandoned Baby - 31 69% -3.47 75% -8.75 69% -7.9 53% -3.96 3 Outside Up + 1920 45% 0.13 44% 0.76 43% 1.4 46% 2.62 3 Outside Down - 2626 51% -0.22 53% 0.52 55% 0.67 57% 1.47 Morning Star + 920 48% 0.57 48% 1.52 44% 1.46 46% 1.7 Evening Star - 1079 56% -0.83 58% -1.35 56% -0.81 61% -1.05 3 Outside UP w/ White Marubozu 392 54% 1.53 54% 4.12 51% 6.38 54% 10.77 175 60% 2.66 68% 7.87 65% 11.26 67% 16.15 20일이격도 90미만 서울대학교최적화및금융공학연구실 page 31
-8 일 5% 2% 5% 금일 5% 5% 숨은패턴찾기 최적화문제 Genetic algorithm/genetic programming 서울대학교최적화및금융공학연구실 page 32
Algorithm Trading 의예 : Portfolio Optimization/Rebalancing Low frequency! 대차대조표 Quantitative Analysis Optimization Algorithms 손익계산서 현금흐름표 주가 거래량 Algorithms Neural Networks Genetic Algorithms portfolio Portfolio Rebalancer 거래소 Portfolio Generator 서울대학교최적화및금융공학연구실 page 33
시스템구조 Portfolio Optimizer Portfolio Rebalancer Algorithm Studio Anchor Pattern Studio Metric Studio 서울대학교최적화및금융공학연구실 page 34
기간수익률 KOSPI 상승률 Portfolio A + Rebalancing K Still improving! 97.4~98.3-38.28% -29.0% 98.4~99.3 141.05% 28.7% 99.4~00.3 25.54% 39.1% 00.4~01.3-13.71% -39.2% 01.4~02.3 183.82% 71.2% 02.4~03.3-23.71% -40.2% 03.4~04.3 69.56% 64.4% 04.4~05.3 80.84% 9.7% 05.4~06.3 107.83% 40.8% 06.4~07.3 46.01% 6.8% 07.4~08.4 50.92% 17.3% 연평균복리수익 42.45% 8.75% 서울대학교최적화및금융공학연구실 page 35
실전 : Started in Feb. 2009 년월 실계좌월별수익률 실계좌누적수익률 KOSPI 월별수익률 KOSPI 누적수익률 2009년 02월 -4.21% -4.21% -9.75% -9.75% 2009년 03월 12.33% 7.60% 13.47% 2.41% 2009년 04월 18.76% 27.79% 13.52% 16.26% 2009년 05월 8.34% 38.44% 1.93% 18.50% 2009년 06월 -1.70% 36.09% -0.42% 18.01% 2009년 07월 4.46% 42.16% 10.41% 30.29% 2009년 08월 2.80% 46.15% 3.72% 35.14% 2009년 09월 -1.66% 43.72% 5.11% 42.04% 2009년 10월 -1.27% 41.89% -5.53% 34.19% 2009년 11월 -3.74% 36.58% -1.59% 32.06% 2009년 12월 11.35% 52.08% 8.17% 42.85% 서울대학교최적화및금융공학연구실 page 36
A Snapshot: Metric Studio 서울대학교최적화및금융공학연구실 page 37
서울대학교최적화및금융공학연구실 page 38
A Snapshot: Trading Simulation 서울대학교최적화및금융공학연구실 page 39
A Snapshot: Portfolio Manager 서울대학교최적화및금융공학연구실 page 40
Optimization 증권데이터같은양질의데이터도드물다 통계적변동이 noise 역할을한다 데이터들속에방대한관계정보가숨어있다 누군가자신을발견해주기를기다리는보석과같다 좋은시스템을만드는것은 noise 와의싸움이다 Noise 는시장참여자의합리적가격결정을방해한다 Noise 덕분에시장은활력을띤다? 입력출력 Anchor 시스템적정가평가시스템 Portfolio optimizer 투자전략 Buy/Sell, 적정가, Portfolio 서울대학교최적화및금융공학연구실 page 41 20 min
어느홈페이지 97 년어느날 Nova Fund 의자동거래가 NASDAQ 총거래량의 14% 차지 서울대학교최적화및금융공학연구실 page 42
4. 결론 서울대학교최적화및금융공학연구실 page 43
결론 기능의시대에서효율성의시대로! 최적화와증권시장 알고리즘들의전쟁터로변할것 확률과정확도의게임 널린최적화문제들 포트폴리오구성 포트폴리오리밸런싱 패턴탐색 투자전략최적화 차이거래 교과서적이론과현장의괴리 Customization Variation Abstraction Blue ocean! 아는만큼보이며, 보는만큼이룬다! 서울대학교최적화및금융공학연구실 page 44