수학에서의 최적화 기법
정의
- 함수 $f : \mathbb{R}^{n} \to \mathbb{R}$ 의 함수값이 최소가 되도록 하는 $x^{ \ast } = \argmin_{x} f(x)$ 를 구하는 문제를 최적화 문제optimization Problem라 하고, 그 문제를 푸는 알고리즘을 최적화 기법이라 부른다. 최적화 문제에서 주어진 함수 $f$ 를 특히 목적 함수objective function라 한다.
- 정의역의 모든 $x$ 에 대해 $f(x^{ \ast }) \le f(x)$ 를 만족하는 $x^{ \ast }$ 를 최적해global Optimizer라 부른다.
- 모든 $x \in \mathcal{N}$ 에 대해 $f(x^{ \ast }) \le f(x)$ 를 만족하는 $x^{ \ast }$ 의 네이버 후드 $\mathcal{N}$ 이 존재하면 $x^{ \ast }$ 를 국소 최적해local Optimizer라 부른다.
위 정의에서 부등호의 방향은 반대여도, 즉 설명이 최대화로 바뀌어도 여전히 이들을 통틀어서 최적화라고 부른다.
설명
최적화 기법을 사용하는 사람은 ‘이익을 극대화’하거나 ‘비용을 최소화’한다는 말을 쓸 수 있지만, 수학자에게 최대냐 최소냐는 크게 중요한 문제가 아니다. 최소화를 최적화와 거의 같은 의미로 쓰는 이유는 최소화 문제에서 쓰던 알고리즘이라도 마지막에 $-1$ 만 곱하면 최대화 문제에 쓸 수 있기도 하고, 수학적으로 대단히 중요한 함수들인 메트릭이나 놈이 $0$ 보다 크거나 같은 실수의 집합을 공역으로 갖기 때문, 다시 말해 최소값이 존재하기 때문이다.
최근 딥러닝이 유행하면서 목적 함수(혹은 비용 함수, 손실 함수)는 보통 스무스한 경우를 상정하지만, 반드시 그러리라는 보장은 없기 때문에 이를 극복하기 위한 알고리즘과 메소드 역시 연구되었다. 목적 함수의 정의역 역시 반드시 $\mathbb{R}^{n}$ 일 필요는 없다.
전역최적해
최적해의 존재성은 간단한 조건 몇가지로도 보일 수 있을지 모르나, 로컬 옵티마이저가 글로벌 옵티마이저라는 것을 보일 수 있는 정리는 없다. 이상적으로는 누구나 최적해를 구하길 바라지만, 실전적으로 구한 해가 최적해이길 진심으로 기대하는 경우는 거의 없다. 최적화 문제는 많지만 그 모든 문제에 대해 딱 맞는, ‘최적화된’ 최적화 기법은 없기 때문에 수많은 개선 알고리즘이 개발되어왔다.
최적해의 엄격성과 고립성
보통의 경우 다음의 정의들은 무의미하나, 일단 언급해둔다.
- 모든 $x \in \mathcal{N}$ 에 대해 $f(x^{ \ast }) < f(x)$ 를 만족하는 $x^{ \ast }$ 의 네이버 후드 $\mathcal{N}$ 이 존재하면 $x^{ \ast }$ 를 엄격한 국소 최적해strict Local Optimizer라 부른다.
- 모든 $x \in \mathcal{N}$ 에 대해 $f(x^{ \ast }) < f(x)$ 를 만족하는 $x^{ \ast }$ 의 유일한 네이버 후드 $\mathcal{N}$ 이 존재하면 $x^{ \ast }$ 를 고립된 국소 최적해isolated Local Optimizer라 부른다.