최적화 이론

1. 개요

• 조합 최적화 (Combinatorial Optimization): 주어진 항목들의 조합으로 해가 표현되는 최적화 문제. 계산 복잡도에서 'NP-어려움'이 나오는 비선형계획법 문제들은 최적해를 구하기 힘들다. 구할 수 있다 해도 비용이 많이 든다. 따라서 NP-어려움임을 증명하는 방법, NP-어려움일 경우 해의 품질을 포기하고 근사해를 구하는 기법들을 배우게 된다. 대표적으로 '외판원 순회 문제'가 있다.
• 메타 휴리스틱(meta heuristics): 최적해(optimal solution)을 보장하지는 않지만 준최적해(suboptimal solution)을 빠르게 찾는 알고리즘. 유전 알고리즘, 모방 알고리즘, 입자 군집 최적화(particle swarm optimization, PSO), 개미 집단(ant colony) 알고리즘, 타부 탐색(Tabu search), 담금질 기법(simulated annealing), 하모니 탐색(Harmonic search) 등이 있다.
• 함수 최적화(function optimization): 어떤 목적 함수(objective function)가 있을 때, 이 함수를 최대로 하거나 최소로 하는 변수 값을 찾는 최적화 문제. 수리계획법 문제들은 상당수 이쪽 범주에 들어간다.
• 경제학: 수리경제학에서 최적화를 다룬다. 최적화는 의사결정을 내리는 경제 주체가 가장 바람직하다고 생각하는 상태를 만들기 위해 하는 것이다. 인간의 합리성 등을 가정하고 소비자의 효용극대화, 기업의 이윤극대화의 해를 구한다. 동적 계획법이나 최적제어론 역시 경제학에 응용되고 있다. 레닌그라드 공방전 당시 라도가 호수의 수송 문제에 이런 방법론들이 적용되어 수많은 사람들의 목숨을 구했다. 당시 이 방법론을 적용하여 수송 작전을 설계한 레오니트 칸토로비치는 이 최적화 이론으로 1975년 노벨경제학상을 수상했다.
• 컴퓨터과학의 한 분야인 이론 컴퓨터 과학에서 많이 쓰인다. 세부적으로 들어가면 담금질 기법, 선형계획법, 비선형계획법 등 다양한 알고리즘을 활용한다.

2. 세부 내용

• 선형 계획법(심플렉스 방법)
• 비선형 계획법 (1차원 최소화 방법, 비제약 최적화 기법, 제약 최적화 기법)
• 라그랑주 승수법
• 기하급수 계획법
• 동적 계획법
• 정수 계획법
• 확률 계획법
• 경사하강법(Gradient Descent)
• Lipschitz continuity
• Subgradient Method
• 최적제어 및 최적기준 방법
• 최적의 정지(Optimal stopping)
• 다중 목적 최적화(파레토 최적화)
• 볼록(Convex)함수와 오목(Concave)함수
• KKT(Karush-Kuhn-Tucker) Condition
• Proximal Gradient and Accelration
• backtracking line search
• Newton's Method

3. 최적화 해 계산 도구

• MATLAB
• Optimization Toolbox #
• Global Optimization Toolbox #
• MOSEC 툴박스
• SCIP - 제약 조건 정수 프로그래밍 문제를 해결(오픈 소스)
• 파이썬
• PuLP 라이브러리* [1]
• Pyomo 라이브러리 *