최적화란 무엇인가?

1. 서론

최적화가 뭐냐고 사전적인 정의를 누가 묻는다면, ‘제약조건을 만족하는 대안의 집합 중에서 의사결정권자의 목적함수를 최적화하는 것을 찾는 이론 일체’라고 답할 수 있다. 최적화의 중요성을 인식하고 발전시킨 초기 주역들은 2차 대전 세대 수리과학자 그리고 경제학자들이다. 국가의 자원과 시스템이 총체적으로 동원되는 전쟁이라는 절박한 생존의 의사결정 문제를 해결해야 했던 호모사피엔스가, 선동적인 전쟁 캠페인 이면에서, 수리과학의 힘을 빌리기 위해 결정변수를 x로 표기하기 시작한 것은 당연한 것이었다. 이후 반세기에 걸쳐 최적화는 변화하는 시대의 수요에 적응하며 학문적인 발전을 이루어 오늘의 모습을 가지게 되었다. 이러한 모습들을 다음의 이슈별로 살펴보자.
  • 응용분야
  • 모형과 해법 개발
  • 최적화의 학제적 성격

1) 응용분야

최적화는 현실 문제를 풀기 위한 학문이다. 앞에 언급한 것처럼, 최적화는 2차대전 동안 군 관련 기관에서 기획, 수송 등의 문제를 해결해야 했던, 댄직, 쿠프먼 등의 수학자와 경제학자들의 필요에 의한 창조물이다. 애로우, 새뮤엘슨, 후르위츠 등과 같은 경제학자들과 터커, 쿤, 게일 같은 수학자들이 합류한 최적화(수리계획)의 0번째 심포지엄이라고 불리우는 1949년 시카고 대학 학회 프로시딩 제목이 'Activity Analysis of Production and Allocation'라는 것이 이러한 사실을 극명하게 보여준다.
이 순간에도 최적화는 각 산업의 분야의 내면에서 그 산업 활동의 목적을 극대화하는 해를 제공하고 있다. KTX 차량 라우팅에서, 제지회사에서 경제적인 절단 패턴을 구하는데, 무선통신망의 효과적인 자원할당을 위해, 위험을 최소화하는 투자 포트폴리오를 구성하는데, 그리고 게놈을 해독 분류하는데 최적화의 모형과 해법들이 적용되고 있다. 예를 들어, 'International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks'은 그 제목에서도 알 수 있듯이, 현재 경제적 잠재력과 규모가 가장 큰 이동통신의 설계, 운용, 품질 보증, 가격정책 등 전반에 걸쳐 최적화의 모형과 해법을 적용하여 최적성을 추구하는데 초점을 둔 학회이다. 이러한 몇 가지의 예에서도 이제 최적화는 그 응용 대상이 반세기 전에 비해 훨씬 정교하고 수리적인 심도를 가지고 사회 성장 동력 산업의 전반에 걸쳐 그 응용이 확산되고 있음을 알 수 있다. 최적화 상용코드 사업은 우리나라에서도 그 잠재적 규모를 키워가고 있으며, 이를 활용할 수 있는 연구 인력이 증가하여 최적화의 해법의 효용이 증명됨에 따라, 더 넒은 분야에서 최적화의 수요를 재생산하게 될 것으로 믿는다.

2) 수리모형과 해법의 개발

최적화는 현실 문제를 수리적이고 과학적인 방법으로 해결하기 때문에, 대상문제의 본질적이고 필수적인 요소를 추출하여 논리적으로 재구성하는 모형화(modeling)라는 과정을 필수적으로 거친다. 따라서 최적화는 현상적으로 보면 수리모형의 구조와 해법을 연구하는 학문이다. 그리고 대상으로 하는 수리모형에 따라 그 하부 분야를 분류할 수 있다.
1980년대 초에 작성된 댄직의 원고에 의하면, 당시 최적화의 중요 하부 분야로, 비선형계획, 네트워크흐름, 대형문제해법, 확률과정계획(Stochastic programming), 정수계획, LCP, 선형계획의 실용적 다항해법 등을 들고 있으며, 대부분은 아직도 중요한 연구 주제로 남아있다. 그러나, 지난 20여년간 최적화 분야에서는 이산적인(discrete) 구조를 갖는 모형에 대한 중요성이 점점 증대되어 왔다. 그 이유는 현대의 시스템이 세부적으로 갈수록 더 이산적인 특성을 갖고 있기 때문이다. 이산구조의 수리모형의 최적화는, 많은 경우, 해법 개발이 본질적으로 난해한 특성, 소위 NP-hard 성질을 가지기 때문에, 관련된 정수계획 및 조합최적화 문제의 구조 연구와 해법 관련 이론은 현재 최적화의 가장 큰 주제라고 할 수 있다.
실제로 정수 및 조합최적화의 해법은 그 발전을 거듭하고 있다. 이는 최적화가 현실 문제를 풀기 위한 학문이라는 것을 생각하면 당연한 현상이라고 하겠다. 80년대 중반 이후 내부점 해법이 동기가 되어 선형계획의 대형해법 학문적으로 또한 상용적으로 급격한 발전을 이루었고, 정수계획문제를 위한 절단평면(cutting plane) 해법이 분지기법과 분해법과 결합하여, 빨라진 컴퓨터 위에서 불과 5-6년 전만 해도 불가능한 크기의 문제를 풀고 있다.
최적화연구에서 흔히 나타나는 심도 있는 수리적인 모습이 바로 이런 현실적인 동기에서 출발하였다는 것을 이해하는 것은 매우 중요하다. 또한 이러한 수리적인 심도가 최적화를 중요한 수리과학의 한 분야로 발전시키고 있는 것도 중요한 의미로 받아들여야 한다고 본다. 수학이 과거에는 존재성을 증명하는 학문이었다면 이제는 그 것을 필요한 시간에 찾아내어 활용하게 하는 측면도 중시하는 학문으로 변화하는 것이 시대의 추세에 맞는 것이기 때문이다. 미국의 경우, 최적화는 수학의 한 분야로 분류 된지 오래이다. 미국수학학회(AMS)는 최적화를 21세기의 10대 주요 수학 분야 중 하나로 꼽았다고 한다.
최적화는 수학 뿐 아니라 컴퓨터 이론과도 불가분의 연관성을 갖고 있다. 최적화가 발전하게 된 결정적인 초기 요인이 컴퓨터의 발전 때문이라는 것은 잘 알려진 사실이다. 특히, 결정문제(decision problem)를 중심으로 70년대에 시작한 NP-hard 성질을 키워드로 하는 계산이론은, 지난 10년간 최적화문제를 중심으로 한 근사해법 관련 계산이론으로 발전하고 있다.

3) 최적화의 학제적 성격

이러한 논의를 볼 때, 최적화는 학제적(interdisciplinary) 성격을 가진 학문이라는 것을 알 수 있다. 현재 대학의 교육 시스템에서 최적화와 관련이 있는 학문분야와 과목은 대략 다음과 같다.
  • 산업공학, 경영학: 미시경제, 경영과학, 생산관리, 선형계획, 네트워크최적화, 비선형계획, 정수 및 조합최적화, 근사해법, 응용 확률과정론, SCM, 금융공학, …
  • 수학: 선형대수, 실변수해석, 기초대수학, 조합론, 확률론, 통계, 그래프이론, 볼록함수해석, 확률과정론, ...
  • 컴퓨터과학: 언어, 알고리듬론, 계산론, 수치해석, ...
따라서 체계적이고 심도 있는 교육과 연구를 위해서는 이러한 관련 학문 분야에 대한 인식과 이를 고려한 협동 커리큘럼이 전제되어야 한다는 것을 알 수 있다. 특히 학문의 저변이 크지 않은 우리나라의 경우, 이러한 학제적 분야에 대한 열린 자세가 더욱 필요하다고 하겠다. 필요한 경우, 산업공학과는 이니셔티브를 가지고 관련 학과들과 협력 프로그램을 만들 수 있다고 본다.

2. 최적화 연구 동향 - 대표적 사례

경영과학 및 최적화의 연구 동향을 모두 망라한다는 것은 필자의 능력의 한계를 넘는 일이다. 다만 필자가 생각하기에 응용분야와 이론분야의 몇 가지 중요한 사례를 통하여 연구의 동향을 가늠할 수 있겠다.

1) 다수의 의사결정자들의 결정 문제 - 게임이론

여러 명의 의사결정자들의 이해관계가 서로 상충되는 상황에서의 결정 문제는 다양한 맥락에서 관찰할 수 있다. 이러한 상황을 설명하는 대표적인 문제가 ‘죄수의 딜레마’이다.
    담당 검사는 두 용의자를 다른 취조실에 데려다 놓고 다음과 같이 이야기를 했다. "만약 너희 둘 다 자백을 한다면, 수사에 협조한 대가로 5년 정도로 양형을 해줄 것이다. 그러나 둘 중 하나만 자백을 할 경우, 자백을 한 사람은 유죄협상에 의거 1년 정도의 구형을 하겠지만, 자백을 거부한 사람에겐 10년형을 청구할 것이다." 하지만 둘 모두 자백하지 않은 경우에는 징역 최대 2년형만을 받게 된다.
우리의 직관과는 반대로, 두 용의자 모두 침묵하여 2년형을 받는 것이 가장 좋은 결과를 가져옴에도 불구하고, 둘 모두 자백하게 된다. 이를 설명하는 모형이 바로 게임이론이다. 게임이론은 1944년 폰 노이만과 모겐스턴에 의해 본격적으로 시작되었다. 그러나 이들의 게임이론은 제로섬 게임과 같이 게임 참가자 간의 이해가 완전히 상반되는 경우의 최적 전략은 명확히 설명하지만, 게임 참가자 간의 협력의 여지가 있는 협력게임에서 나타나는 참가자들의 최적 행태에 대해서는 잘 설명하지 못한다. 이러한 이론의 한계를 극복할 수 있는 계기는 내쉬(J. Nash)가 발표한 일반화된 전략적 균형의 개념이며, 이를 내쉬균형(Nash equilibrium)이라고 부르고 있다. 이후 약 사반세기 동안 게임이론은 내쉬, 섀플리, 그리고 하사니 등과 같은 학자들의 연구 결과를 바탕으로 급속한 발전을 이루었으며 경제학이나 경영학의 중요한 패러다임으로 자리잡았다. 지금도 게임이론은 사회과학뿐만 아니라 진화생물학 등과 같은 분야까지 그 응용의 범위를 넓혀가며 발전하고 있다.
다수의 의사결정자들이 때로는 상충되는 이해관계 속에서, 혹은 때로는 협력관계 속에서 서로의 목적을 위해 합리적인 의사결정을 해야 하는 경우는 매우 다양하다. 국제 관계에서 나타나는 상충 관계 혹은 협력 관계, 시장에서의 기업 간 이해 관계 등에서 나타나는 의사결정 문제가 하나의 응용분야이고, 또한 사용자들의 대중 교통망 내 이동경로 선택도 게임의 균형을 통해 설명할 수 있다.

2) 선형계획의 확장 - 원추선형계획

반세기 동안 연구자들은 많은 종류의 수리계획의 모형을 개발하였고, 그것들을 위한 해법들을 개발하였지만, 아직도 선형계획은 모든 최적화 연구의 중심을 지키고 있다. 그 이유는 두 가지가 있다고 본다.
첫째는 선형계획은 풀기 쉽다는 것이다. 이것은 이론적인 측면과 실용적인 측면 모두에 해당하는 말이다. 타원 해법이나 내부점 해법은 선형계획이 다항시간의 계산 복잡성을 갖는다는 것을 증명하였다. 또한 수십 년간 사용해온 심플렉스해법은, 내부점 해법과의 비교에서 논란의 여지는 있지만, 아직도 대부분의 대형 응용문제를 만족할만한 속도로 풀어내고 있다. 아마 이것은 선형계획의 해집합인 다면체가 갖는 구조의 상대적인 단순성에서 기인하는 것 같다.
둘째로는 선형계획은 그 수리적인 단순성에 비해 놀랄 만큼 적용성이 크다는 것이다. 이것은 첫째 이유보다 더 중요하다고 할 수 있겠다. 현실적 응용 뿐 아니라, 이론적으로도 많은 응용성을 가진다. 선형계획은 NP-hard 문제의 구조나 해법연구에 중요한 방법론을 제시한다. 예를 들어, 최근 발간된 슈라이버의 방대한 저서 Combinatorial Optimization은 많은 조합최적화문제의 구조와 해법을, 선형계획이라는 접근법으로 일관되게 설명할 수 있다는 것을 보여준다. 이런 측면에서 볼 때, 선형계획은 최적화의 연구자들이 추구할만한 모든 조건을 가지고 있는 수리모형이라고 할 수 있다. 더 정확히 말하면, 선형계획이 가진 조건을 갖춘 수리모형이 최적화의 궁극적인 목표라고 말해도 틀리지 않을 것이다.
SDP는 이러한 선형계획의 확장인 원추선형계획의 특수한 경우이다. 원추선형계획은 선형계획에 변수가 원추에 속한다는 제약이 추가된 수리모형을 말한다. 선형계획의 확장이기 때문에 선형계획 보다 나은 역할을 수행할 수 있는 개연성이 있다. 어떤 조합최적화문제의 경우는 SDP 완화를 사용하면 선형완화를 사용할 때보다 더 좋은 품질의 해를 얻을 수 있다. 하지만 이 방법의 단점은 선형계획에 비해 풀기가 어렵다는 것이다. 주어진 문제의 크기가 큰 경우에 대한 효율적인 코드가 아직 발견되지 않았다.
원추선형계획은 공학 분야의 전통적인 고유치 관련 최적화문제를 비롯하여, 통신, 패턴 인식 등에 그 응용범위를 확장하며 최적화의 연구의 진화과정을 잘 보여 주고 있다. 중요 응용의 하나로 원추선형계획법을 통해 특정 다항식이 다른 다항식의 제곱 합으로 표현되는지 여부를 파악할 수 있다. 그리고 어떤 다항식이 다항식의 제곱 합으로 표현되는 성질은 모든 점에서 그 다항식의 함수값이 비음이라는 것에 충분조건이 된다. 이러한 성질은 전통적 ‘순수 수학’(Hilbert의 17번째 문제)과도 깊은 연관성을 가지며, 최근 연구가 활발하게 이루어지고 있는 다항최적화문제(목적함수 식과 제약조건 식이 다항식으로 주어진 문제)에 대한 해법에 핵심을 이루고 있다.

바라는 인재상

  • 현실 문제를 과학적/수리적 방법론으로 모델링하려는 동기를 가진 학생
  • 수학 및 컴퓨터를 활용하여 현실의 최적화 문제를 해결하고자 하는 학생
  • 수학적 성숙도를 갖춘 학생
  • 족구 혹은 탁구에 일가견이 있는 학생

  • 서울대학교 산업공학과 경영과학/최적화 연구실, 서울시 관악구 신림동 56-2 39동 411호 우)151-742
    Management Science/Optimization Lab., 39-411 Seoul National University, 56-2 Shilim-dong, Kwanak-gu, Seoul, Korea
    Tel) 82-2-884-1164 E-mail) webadmin@polytope.snu.ac.kr