최적화 이론

조합 최적화 (Combinatorial Optimization): 주어진 항목들의 조합으로 해가 표현되는 최적화 문제. 계산 복잡도에서 'NP-어려움'이 나오는 비선형계획법 문제들은 최적해를 구하기 힘들다. 구할 수 있다 해도 비용이 많이 든다. 따라서 NP-어려움임을 증명하는 방법, NP-어려움일 경우 해의 품질을 포기하고 근사해를 구하는 기법들을 배우게 된다. 대표적으로 '외판원 순회 문제'가 있다.

함수 최적화(function optimization): 어떤 목적 함수(objective function)가 있을 때, 이 함수를 최대로 하거나 최소로 하는 변수 값을 찾는 최적화 문제. 수리계획법 문제들은 상당수 이쪽 범주에 들어간다.

경제학: 수리경제학에서 최적화를 다룬다. 최적화는 의사결정을 내리는 경제 주체가 가장 바람직하다고 생각하는 상태를 만들기 위해 하는 것이다. 인간의 합리성 등을 가정하고 소비자의 효용극대화, 기업의 이윤극대화의 해를 구한다. 동적 계획법이나 최적제어론 역시 경제학에 응용되고 있다. 레닌그라드 공방전 당시 라도가 호수의 수송 문제에 이런 방법론들이 적용되어 수많은 사람들의 목숨을 구했다. 당시 이 방법론을 적용하여 수송 작전을 설계한 레오니트 칸토로비치는 이 최적화 이론으로 1975년 노벨경제학상을 수상했다.

컴퓨터과학의 한 분야인 이론 컴퓨터 과학에서 많이 쓰인다. 세부적으로 들어가면 담금질 기법, 선형계획법, 비선형계획법 등 다양한 알고리즘을 활용한다.

선형 계획법(심플렉스 방법)

비선형 계획법 (1차원 최소화 방법, 비제약 최적화 기법, 제약 최적화 기법)

기하급수 계획법

정수 계획법

확률 계획법

경사하강법(Gradient Descent)

최적제어 및 최적기준 방법

최적의 정지(Optimal stopping)

다중 목적 최적화(파레토 최적화)

볼록(Convex)함수와 오목(Concave)함수

Proximal Gradient and Accelration

Newton's Method

MATLAB

SCIP - 제약 조건 정수 프로그래밍 문제를 해결(오픈 소스)