연구


非淡泊無以明志, 非寧靜無以致遠


일본의 천년사찰 호류지를 돌보며 지킨 ‘궁궐목수’ 니시오카 쓰네카즈(西岡常一)는 “벌이가 되는 일로 내달리게 되면 마음이 혼탁해지게 된다”며 평생 일반 집을 짓지 않고 농사로써 생계를 꾸리며 목수일에 전념했습니다. 유용한 수리최적화 방법론(이론 및 기법) 개발의 연구는 ‘호흡을 길게 가지고 찬찬히 살피며 전진하는’ 각고의 노력이자 '한눈 팔지 않겠다'는 다짐입니다. 그러기에 그 성취감은 무엇보다 큽니다.  


지난 28년간 수리최적화 방법론 연구에 전념해 온 본인의 연구는 크게 초기 ‘일반적인 전역최적연구’와 2013년 이후의 현재 ‘데이터분석과 연관한 이산·조합최적화 및 위상학 연구’의 단계로 구분할 수 있습니다.


Phase I. 연속함수 전역최적화 연구(2013년 이전)


세상 물정과 현상을 정확히 기술한 수리/공학모형은 비볼록·비선형함수와 비선형 및 정수변수를 포함합니다. 이런 모형은 여러 개의 최적해가 존재하고, 해법 측면에서 난이도(Numercial/Computational Complexity)가 어려운 문제를 이룹니다. '비볼록 비선형최적화' 모형의 여러 해 중 가장 우수한 해를 찾는 것을 전역최적(Global Optimization) 이라 일컫습니다. 


본인의 초기 연구는 임의의 전역최적화 문제를 풀이하는 general-purpose 해법 이론 개발과 함께 비볼록 비선형함수 중 가장 어려운 꼴인 곱셈함수(multilinear 함수)를 포함한 모형의 전역최적 방법론 연구를 두 축으로 진행되었습니다. 이 기간의 연구성과를 요약하면 아래와 같습니다.

  a. BARON (Branch-And-Reduce Optimization Navigator) 개발

  • 임의의 비선혼합정수최적화 문제를 전역최적할 수 있는 convexification scheme과 search domain contraction schemes 개발
  • 상기 기법을 branch-and-bound 프레임워크에 담은 branch-and-reduce 전역최적 알고리즘 BARON 개발
  • BARON은 현재 MATLAD, GAMS, AIMMS, AMPL, YALMIP, Pyomo, JuMP 등의 S/W에서 비선형/전역최적화 솔루션으로서 탑재
  • 더불어, 새롭게 개발되는 (INFORMS, ISMP 등 국제학술대회 논문에서 발표되는) 거의 모든 정수 및 전역최적화 알고리즘 성능 시험에 비교대상 벤치마크로 사용됨

  b. 실수변수로 정의된 Multilinear 최적화모형(이하, MP) 의 전역최적화 연구

  • 곱하기꼴 함수의 convexification 이론 및 기법 개발
  • 전역최적의 어려움으로 인해 1984 년 이후 침체해 있던 multiliear 함수 속성 전역 최적화 연구에 활기를 불러옴

  c. 대표논문

  • "Nonlinear separation of data via mixed 0-1 integer and linear programming," Applied Mathematics and Computation, 2007
  • “Data separation via a finite number of discriminant functions: a global optimization approach,” Applied Mathematics and Computation, 2007
  • "A compact mean-variance-skewness model for large-scale portfolio optimization and its application to the NYSE Market," Journal of the OR Society, 2007
  • "Global Optimization of Multiplicative Programs," Journal of Global Optimization, 2003
  • "Analysis of Bounds for Multilinear Functions," Journal of Global Optimization, 2001
  • "A Branch-and-Reduce Approach to Global Optimization," Journal of Global Optimization, 1996


새로운 연구 준비(2013-2015년 초)

최적화방법론 연구의 가치를 보여주기 위해 발표한 두 편의 논문을 통해 불린로진 기반 데이터분석(이하,LAD)연구의 패러다임을 기존 '열거법'기반에서 수리최적화(이산·정수계획법)기반으로 바꾸는 반향을 일으켰습니다. 이에 주 연구주제를 연속함수 모형의 전역최적화에서 전혀 다른 분야인 이산함수 모형의 전역최적화 방법론 연구와 이를 통한 데이터분석으로 바꾸었고, 그 토대를 견고히 구축하고자 그래프이론, 조합론과 정수계획법의 cutting planes 이론 및 polyhedral 속성을 수학하였습니다.


Phase II. Mathematical Data Analysis & Decisions

  a. 이산·조합최적화 & LAD 연구(2015년 이후, 현재)

LAD와 연관한 데이터분류 및 분석 방법론 개발을 주된 목적으로 새로운 분야인 이산·조합최적화 방법론 연구를 개시, 현재까지 진행해오고 있습니다. 

  • 2015년 상반기 삼성미래기술육성재단 '수리과학' 분야 연구 수주. 고려대학교 공대소속 중 최초이자 현재까지 非 수학과 수학연구기관 소속 연구자로서 선정된 유일한 경우
  • 기존 연구에서 발표한 내용 포함, LAD 패턴생성(지식발견)을 통섭하는 최적화 이론 제시
  • 데이터의 graph 및 hyper-graph 상 이웃속성 연구와 LAD 패턴생성 모형(이하, (PG))의 multilinear polytope 속성 규명
  • 데이터 융합/감소 및 (PG) 모형 강화기법 제시
  • 기존 군집화(클러스터링, Clustering)기법에 LAD의 장점을 융합해 새로운 감독학습(Supervised Learning) 데이터분석 기법을 개발·제시. 참고로, 이 기법은 WEKA의 대표 데이터분류 알고리즘 11개와의 비교실험에서 월등히 우수한 성능을 선보임

Boolean Logical Pattern Generation

  Polyhedral Analysis of LAD Pattern Generation




Graph Theoretic Analysis of Data



 Cliques for Data Aggregation & Analysis




  b. 위상학적 데이터분석 (2017년 이후, 현재)

  • 감독학습 기반 데이터분류 기법으로서의 위상학적 데이터분석(이하, TDA) 방법론 개발
  • TDA를 이용한 (대표)데이터 선택 및 융합 기법 개발




  c. 대표논문

  • "A Multi-Term, Polyhedral Relaxation of a 0-1 Multilinear Function for Boolean Logical Pattern Generation," Journal of Global Optimization, 2019
  • "Strong Valid Inequalities for Boolean Logical Pattern Generation," Journal of Global Optimization, 2017
  • "0-1 Multilinear Programming as a Unifying Theory for LAD Pattern Generation," Discrete Applied Mathematics, 2017
  • “Compact MILP Models for Optimal and Pareto-Optimal LAD Patterns,” Discrete Applied Mathematics, 2012
  • "MILP Approach to Pattern Generation in Logical Analysis of Data," Discrete Applied Mathematics, 2009
  • "A LAD-based method for selecting short oligo probes for genotyping applications," OR Spectrum, 2008