최적화알고리즘과투자공학 서울대학교컴퓨터공학부 최적화 / 금융공학연구실 문병로 서울대학교최적화및금융공학연구실 page 1
목차 1. 도입, 문제공간 2. 최적화 3. 주식투자와최적화 서울대학교최적화및금융공학연구실 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
문제공간 각격자점하나는하나씩의솔루션 최적화 - 문제공간에서가장높은봉우리를찾는것 대부분문제공간은 N차원이다. 서울대학교최적화및금융공학연구실 page 7
Traveling Salesman Problem (TSP) N 개의도시가주어지고, 모든도시를방문하고돌아오는최단경로를찾는문제 컴퓨터과학의대표적난제, NP-Hard 실제로는 N 차원
문제공간의방대함 25-city TSP ( 아주조그만문제 ) 25-city problem 6.2 * 10 23 solutions 1만 clocks/solution 모든경우를다보려면 700억년소요 8000-city TSP 문제의공간은어떨까?
끌개 - Local Optimum : 지역최적점 (local optimum) = 끌개 (attractor) 최대화문제 : 봉우리 최소화문제 : 계곡
TSP 의끌개수 10-City TSP: 끌개평균 4 개 20-City TSP: 끌개평균 170 개 100-City TSP: 끌개평균 3.4Ⅹ10 16 (3경 4천조 ) TSP 의솔루션의수 100-City TSP 의모든솔루션의수 : 9.3Ⅹ10 157 100-City TSP 에서의끌개의비율 3Ⅹ10 141 솔루션당하나씩의끌개 8000-city TSP 문제의끌개수는? 최적화알고리즘은이런공간을돌아다니는교통수단이다.
끌개 (Attractor) Attractor = 끌개 문제공간상에서의지역최적점 공간탐색의목표이자장애물 끌개의예 생태계의종 : 개나리, 질경이, 치타, 가젤, 인류사의조직, 제도 : 가족, 부족, 국가, 학교, 대통령제, 인간의고정관념, 사고체계 : 시각, 습관, 편집증, 시장에서정착되는제품들 타게팅엔진이생산하는솔루션집합 테니스의스윙폼 Optimization은가장수준높은끌개를찾는것 저수준끌개 (low-quality local optimum) 에고착되어버리지않도록 다양한끌개에접할수있도록넓은탐색기능필요 우리에게가장매력적인투자전략은아주높은하나의끌개다!
2. 최적화 서울대학교최적화및금융공학연구실 page 13
문제를푼다는것 Decision problems 질문에대해 Yes 또는 No 라고대답하면되는문제 Equations 조건을만족하는해를찾는것 유효한해의수는많지않다 ( 대부분 ) Optimization 유효한해는무수히많다 이들중가장매력적인해를찾는것 서울대학교최적화및금융공학연구실 page 14
Types of Optimization Problems Function optimization 주어진함수값을최대화 / 최소화하는변수값찾기 System identification 주어진입력 - 출력집합을가장잘설명하는시스템찾기 Function approximation, Neural-network optimization, 투자전략, Combinatorial optimization 이산적해들의집합에서가장매력적인해를찾는것 그래프분할, TSP, 차량라우팅, VLSI 회로배치, 벡터양자화, 전략최적화, 서울대학교최적화및금융공학연구실 page 15
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 16
Optimization Problems Function optimization 함수의최적해탐색, 방정식근사, System identification Mostly black-box models» 신경망디자인, 함수근사,» 문자인식, 질병예측, 사기진단, 주가예측, 투자전략,» Decision logic, 다중엘리베이터최적제어, 핵연료상관식디자인, Combinatorial optimization TSP, 차량라우팅, 스케줄링 시재관리최적화, 공정-장비할당최적화 그래프분할, VLSI 회로배치 벡터양자화 투자전략, 게임전략, 서울대학교최적화및금융공학연구실 page 17
Optimization Methods Deterministic algorithms Local search algorithms Greedy algorithms Heuristics Linear programming Dynamic programming Neural net Stochastic approaches Genetic algorithm, LSMC, tabu search, 서울대학교최적화및금융공학연구실 page 18
Obstacles 시간의제한 Hierarchical model 필요 경험적직관필요 Abstraction, articulation, event 화 Dream: Raw data로부터바로시스템도출» 시스템의복잡성으로인해대부분가능하지않다 Articulation 필요 서울대학교최적화및금융공학연구실 page 19
3. 주식투자와최적화 서울대학교최적화및금융공학연구실 page 20
투자철학에따른분류 소극적투자자 효율적시장가설학파 적극적투자자 99.9% 개인투자자, 대부분의펀드, 대부분의기관투자자, 인덱스펀드 사람중심 Computer 지원형 통계, 계산, 분석 : 컴퓨터 전략, 판단 : 사람 Computer 주도형 컴퓨터가전략까지 HFT (High-Freq. Trading) S&P 500 Wilshire 5000 KOSPI 대형 / 소형성장주인덱스대형 / 소형가치주인덱스 대부분의펀드대부분의분석기반투자자 대부분의시스템 / 알고리즘트레이딩 르네상스테크놀로지 중장기알고리즘투자 일종의전문가시스템 옵투스
알고리즘트레이딩현황 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 more people working in their technological area than on the trading desk. The nature of the market has changed dramatically. 7/2007 AP 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 Arms race! 97 년어느날 NASDAQ 전체거래의 14% 차지 2014 년에는 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
문지기의꿈 (Janitor s Dream) 인지물리학자들 사람의의식을표현할수있는수식이있을것이다 의식의추상화레벨은 10층, 논의는지하1층 일반투자자들, 수학 - 물리학자들 시장의원리를설명하는마법의수식이있을것이다 시장의추상화레벨은 10층, 논의는 1층
주가는장기적으로장부가치를반영한다 300 250 MKF2000 자본총계지수 200 150 100 50 0 2000 년 1 월 ~ 2012 년 6 월
한국증시의평균상승폭, 2000~2011 평균상승폭 (%) 7 5 산술평균상승폭 기하평균상승폭 3 1-1 1 일후 1 주후 2 주후 3 주후 6 주후 3 개월후 6 개월후 -3-5
상식과다른예 : 볼린저밴드 12 10 8 6 상단 3% 근접상단돌파시장평균 6 5 4 3 2 1 상단3% 근접상단돌파시장평균 4 0-1 1 주후 2 주후 3 주후 6 주후 3 개월후 6 개월후 2-2 0 1 주후 2 주후 3 주후 6 주후 3 개월후 6 개월후 -3-4 -5 산술평균 기하평균
인기의실체, w/ PBR 1 년평균상승폭 (%) 80 60 40 PBR 1 미만 PBR 1 이상 PBR 5 이상 20 0-20 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011-40 -60
미국주식의 PBR 십분위에따른수익률 1951-2003 비교, 한국 (2000~2012) 십분위 1 (Lowest) 연평균기하수익 16.59% 동기간미국주식연평균기하수익률 : 11.7% 기하수익률 30% 25% 2 15.48% 20% 3 15.08% 15% 4 13.98% 10% 5 12.25% 5% 6 11.60% 7 11.49% 1 2 3 4 5 6 7 8 9 10 0% -5% 1 2 3 4 5 6 7 8 9 10 8 11.35% -10% 9 11.12% 10 (Highest) 9.26% 실제투자수익은여러요인으로이보다다소낮게나온다 -15% -20%
극단치의함정 0 주수익률 (Log) 하단극단치, 8 년 ( 전후 4 년 ) -2-4 -6-8 -10 평균 : -4.27σ 최고 : -1.57σ 최저 : -12.02σ -12-14 1/416 의확률지점 : -2.82σ -4.27σ 이하는십만분의 1 정도 (2 천년에한번 ) -6σ 이하는 10 억분의 1 정도 (2 천만년에한번 ) 이런일이 8년동안무수히일어난다정규분포턱없이맞지않고, log 처리해도여전히턱없다
기록들 Graph partitioning Johnson Benchmark (1994, 2004) Circuit partitioning MCNC Benchmark (1998) TSP TSP LIB (1994, 2002) 198- 꼭지지수귀문도발견 (2003) 유전알고리즘사용 행렬곱셈의복잡도 O(n 2.81 ) 알고리즘 유전알고리즘에의한자동발견 ( 세계최초 ) 6700 만년 10 분 GECCO 2D Assignment Contest 우승 (2008) 우리의관점에서이런문제들이나주식투자문제모두최적화문제다
누적수익률 180% 160% 포트폴리오누적수익률 KOSPI 누적수익률 168% 140% 120% 100% 80% 60% 67% 40% 20% 0%
분기 포트폴리오분기별수익률 포트폴리오누적수익률 KOSPI 분기별수익률 KOSPI 누적수익률 09. 1 분기 7.60 7.60% 2.41 2.41% 2 분기 25.75 35.31% 15.24 18.01% 3 분기 5.60 42.90% 20.36 42.05% 4 분기 7.71 53.91% 0.58 42.86% 10. 1 분기 4.45 60.76% 0.60 43.72% 2 분기 6.79 71.68% 0.32 44.18% 3 분기 11.88 92.06% 10.28 59.00% 4 분기 13.26 117.53% 9.51 74.13% 11. 1 분기 5.80 130.14% 2.72 78.86% 2 분기 -0.84 128.21% -0.29 78.34% 3 분기 -12.75 99.12% -15.76 50.24% 4 분기 12.19 123.39% 3.17 55.00% 12. 1 분기 9.12 143.77% 10.31 70.99% 2 분기 -7.05 126.58% -7.95 57.40% 3 분기 17.37 165.93% 7.67 69.47% 4 분기 1.16* 168.96% 0.04 69.55% 13. 1. 25-0.19 168.45% -1.76 66.57% * 추정배당 2% 반영
연도별수익률비교 with KOSPI 60% 50% 40% 30% 20% 10% 옵투스수익률 KOSPI 수익률 0% -10% 2009 2010 2011 2012-20%
연도별수익률비교 with KOSPI 60% 50% 40% 30% 20% 10% 옵투스수익률 KOSPI 수익률 0% -10% 2009 2010 2011 2012-20%
Betti ng 기하평균 0 1.0 1/36 1.022 1/18 1.036 2/18 (1/9) 1.04 5 3/18 1.038 4/18 1.019 5/18 0.990 6/18 0.954 9/18 0.808 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 최적화문제투성이 켈리베팅선 ( 최적투자율 ) r=0.085 4 산술평균수익 대차대조표 3 배 평균 2.5배 2 배 3.5 3 2.5 2 1.5 1 0.5 0.1 r=0.040 r=0.036 r=0.044 r=0.037 0.4 0.3 0.2 0. 1 표준편차 Portfolio 손익계산서현금흐름표주가거래량 50.00% PSR PSR 5배 0.01배 POR 14.26% 6.18% POR 8.53% -12.50% 문제모델링과최적화알고리즘 0.00% 1 3 5 7 9-50.00% 기하수익 ( 복리수익 ) 변동성감소, 수익감소수익감소, 변동성증가기하평균표 : 앞의예 투자전략 Pattern 경제지표 Kelly bet/2 Kelly bet Kelly bet*2 Portfolio Optimize r Algori thm Studio Portfolio Rebalanc er 과소배팅 과대배팅 Anchor Metric Studio Pattern Studio 2020 년어느칼럼... 10 년전만해도이렇게변수가많고복잡한투자를기계보다사람이더잘할수있다고대부분믿었다. 그런시절도있었다.
사람은아니다 사람의인지적오류가발생하는곳에수익의기회가있다 컴퓨터지원형까지인지적오류가산재한다 컴퓨터주도형에도모델링에인지적오류가존재한다 주식투자는한단계들어가보면리스크를거래하는것이다 리스크를현명하게견딜수있는사람은극소수 기계적인매매가답이다 사람중심 미국, 알고리즘트레이딩 - 2006 년 1/3-2009 년 3/4-2015 년? 컴퓨터지원형 컴퓨터주도형 당분간은혼재하면서점점컴퓨터주도형의비중이커질것
결론 기능의시대에서효율성의시대로! 최적화와증권시장 : 패러다임의전환 알고리즘들의전쟁터로변할것 확률과정확도의게임 널린최적화문제들 포트폴리오구성 포트폴리오리밸런싱 패턴탐색 투자전략최적화 차익거래 교과서적이론과현장의괴리 Customization Variation Abstraction Blue ocean! 아는만큼보이며, 보는만큼이룬다! 서울대학교최적화및금융공학연구실 page 37