최적화 Optimization

일차원 비구속 최적화 One-Dimensional Unconstrained Optimizaion

단일 변수 혹은 다변수 함수인 f(x) 의 최소값과 최대값을 구하는 방법, 1 차원 함수의 롤러 코스터 모형, 2차원의 산이나 계곡과 같은 가시적 현상, 더 고차원 문제의 경우 알맞은 시각적 형상이 불가능하다.

한 개의 함수에 대해 여러 개의 근이 존재하는 것으로 인해 근을 구하는 것이 매우 복잡해진다. 최적화 문제에서도 마찬가지로 국부적, 전역 최적값이 모두 나타나고 이를 다모드 multimodal 문제라고 한다. 대부분의 경우 함수의 절대적 최대, 최솟값을 찾는데 관심이 있다.

국부적 극대/극소값과 전체 최대/최소 값을 구분하는 것은 매우 어려운 문제, 이러한 문제를 다루는 방법 소개

1. 저차원 함수의 거동에 대한 고찰을 그래프적으로 하는 방법
2. 넓게 변동하는 불규칙한 초기 추축값들을 사용하여 최적값들을 찾은 후 가장 큰 값을 전체 최적값으로 취하는 방법
3. 국부적인 최적값과 연관된 초기값들을 교란한 후 더 나은 값으로 옮기는지 관찰하는 방법(또는 다시 돌아오는지)

1. 황금 분할법 Golden-Section Search

한 개의 비선형 방정식의 근을 구하는 데 있어서의 목표는 f(x) 가 0 이 되는 x 의 값을 찾는 것이다. 단일변수 최적화 문제 (single-variable optimization) 는 f(x) 의 최대값과 최소값을 나타내는 극값인 x 를 구하는 것이 목적이다.

이분법에서와 같이 한 개의 해를 담는 구간을 먼저 정의한다. 즉, 그 구간에는 한 개의 최대값이 담겨있어야 한다. 이러한 경우를 단 모드 (unimodal) 라고 한다.

최대값의 발생여부를 탐색하기 위해 세 개의 함수값이 필요하다. 따라서 구간 내의 또 다른 하나의 점을 선택해야 한다. 다음으로는 네 번째 점을 구간 내에 적절하게 배치하여 최대값이 앞의 세 점 사이에 나타났는지, 나중 세점에서 나타났는지를 확인하는 것이다.

이러한 방법이 효율적으로 진행되기 위해서는 중간 점들의 현명한 선택이 중요하다. 이분법에서처럼 그 전 값들을 새 값들로 치환하여 함수값 계산을 줄이는 것이 목표다. 이러한 목표는 다음 조건을 만족하도록 하면 달성이 된다.

 

첫 번째 조건은 두 개의 부가적 길이인 l1 과 l2 의 합이 원래 구간의 길이가 되도록 한다. 두 번째 조건은 길이의 비가 같도록 함을 나타낸다. 식 (1) 을 식 (2) 에 대입하면,

위 식의 역수를 취한 후 R = l2 / l1 으로 하면, 다음 식을 얻게 된다.

여기서 실수의 근을 구하면

이 값은 황금비라고 불린다. 이것을 이용하여 최적값을 효율적으로 얻을 수 있기 때문에 우리가 지금까지 개념적으로 전개해온 황금분할법의 핵심요소가 된다.

이 방법은 f(x) 의 국부적 극점을 포함하는 두 개의 초기 추측값으로 시작한다. 다음은 두 개의 내부점 x1 과 x2 를 황금비를 이용해서 구한다.

두 개의 내부점에서 함수값을 구하면 두 가지 결과를 얻을 수 있다. 

1. f(x1) > f(x2) 이면 x2 의 왼쪽에 있는 x 의 영역, 즉 xl 로부터 x2 까지의 구간을 제거할 수 있다. 왜냐하면 그 구간에는 최대값이 없기 때문이다. 이 경우 x2 가 다음 반복 시행의 새로운 xl 이 된다.
2. f(x2) > f(x1) 인 경우 x1 의 오른쪽에 있는 영역, 즉 x1 부터 x2 까지의 구간이 제거된다. 이 경우 xu 이 다음 반복시행의 새로운 xu 가 된다.

여기서 황금비 사용의 실제적인 유익을 생각해 보자. 최초의 x1 과 x2 가 황금비를 따라 선택되었기 때문에 다음 반복수행시 모든 "함수값" 을 다시 계산할 필요가 없다.

과거의 x1 은 새로운 x2 가 된다. 이것은 새로운 x2 에서의 함수값 f(x2) 는 과거의 x1 에서의 함수값과 같아짐을 의미한다.

알고리즘을 마무리하기 위해서는 새로운 x1 을 결정해야 한다. 이것은 전과 같은 비례상수를 사용해서 얻어진다.

반복법이 적용되면서 최적값을 담고 있는 구간은 매우 급속도로 줄어든다. 사실 한 번 반복에 구간은 황금비 (약 61.8 %) 의 비율로 줄어든다. 즉 10 번을 반복하면 구간이 원래 길이의 약 0.61810, 혹은 0.008 혹은 0.8 % 로 줄어들게 되며, 20 번 반복하면 약 0.0066 % 가 된다. 이는 이분법에 의한 수렴성만큼은 미치지 못하지만, 최적값을 구하는 문제로는 나쁘지 않다.

2차 보간법 Quadratic Interpolation

2차 보간법은 2 차 다항식이 종종 최적값 근처에서의 f(x) 형상을 잘 근사한다는 사실을 이용한다.

두 점을 잇는 직선은 한 개뿐인 것처럼, 세 점을 잇는 포물선도 한 개이다. 따라서 최적값을 둘러싸는 세 점이 주어진다면, 세 점을 연결하는 포물선을 구할 수 있다. 따라서 그 포물선식을 미분한 후 0 을 만족하는 x 값을 예상 최적값으로 구한다.

가위치법과 마찬가지로 2 차 보간법은 구간의 한쪽 끝에서만 수렴이 일어날 수 있음을 기억하자. 따라서 수렴속도가 다소 느릴 수도 있다. 예를 들면, 앞의 예와 같이 1.0000 이 대부분의 반복단계에서 한쪽 끝단임을 알 수가 있다.

직접법 Direct Methods

1. 임의 탐색

단순한 접근법 중의 하나는 임의탐색법이다. 이름으로도 알 수 있듯이 독립변수들을 불규칙하게 선택해서 함수값을 반복적으로 계산하는 것이다. 만일 충분한 수의 샘플이 사용된다면 결국 최적값을 찾을 수 있게 된다.

2. 단변분 및 패턴탐색

단변분 탐색법의 기본적인 전략은 근사값을 개선하기 위해 다른 변수들을 고정시키고 한 번에 하나의 변수만 변화시키는 것이다. 단 하나의 변수만이 변화되므로 이 문제는 앞서 설명된 방법들과 같은 일차원 탐색법의 순차적 적용이 된다.

그림에서 볼 수 있듯이 단변분 탐색을 그래프를 이용하여 살펴보자. 점 1 에서 출발하여 점 2 의 최대값으로 이동하기 위해 y 값은 고정하고 x 축을 따라 움직인다. 점 2 는 x 축을 따라서 움직이면서 등고선과 만나는 점이 되므로 최대 값이 됨을 알 수 있다. 다음에는 x 값을 고정하고 y 축을 따라 이동하여 점 3 에 이르게 된다. 이러한 과정을 반복하여 4, 5, 6 등의 점들에 도달한다.

비록 최대값에 서서히 접근하고 있지만, 최대값 근처의 능선을 따라 움직이면서 효율이 떨어지게 된다. 그러나 1-3, 3-5 혹은 2-4, 4-6 점들을 연결하는 선들은 최대값 방향으로 나아감을 알 수 있다. 이러한 추적궤적은 최대값을 향해 능선을 따라 진행하는 기회를 제공한다. 이러한 궤적을 패턴 (pattern) 방향이라고 한다.

최적값을 효율적으로 구하기 위해서 패턴 방향의 아이디어를 이용하는 형식 (formal) 알고리즘이 개발되어 있다. 이러한 알고리즘 중에서 가장 잘 알려진 방법이 Powell 법이다. 점 1 과 점 2 가 방향은 같으나 다른 시작점을 이용한 1 차원 탐색 결과로부터 얻어진다면 점 1 과 점 2 를 연결하는 선은 최적값을 향하게 될 것이다. 이러한 선을 공액 (conjugate) 방향이라고 부른다. 만일 f(x, y) 가 2 차 함수라면 공액방향을 따르는 연속적 탐색은 초기점과 관계없이 몇 번의 단계로써 바로 수렴하게 될 것이다. 일반적인 비선형함수는 종종 2 차 함수로 근사될 수 있으므로 공액방향에 기초한 방법은 매우 효율적이며, 최적값에 근접하면서는 2 차 수렴속도를 갖게 된다.

단순화된 Powell 법으로 다음 함수의 최대값을 그래프를 이용하여 구해보자.

f(x, y) = c - (x - a)2 - (y - b)2

여기서 a, b, c 는 양의 상수이다. 이 방정식은 위 그림 에 나타난 바와 같이 x, y 평면에서 원형의 등고선을 보여준다. 출발방향을 h1, h2 로 하여 점 0 에서 출발한다. 출발방향인 h1 과 h2 는 공액방향이 아니어도 상관없다. 점 0 에서 출발하여 h1 방향을 따라 최대값인 점 1 에 도착하며, 점 1 에서 다시 h2 방향을 따라 최대값 점 2 를 얻는다.

다음은 점 0 과 점 2 를 통과하는 새로운 방향 h3 를 구한다. 이 방향을 따라서 탐색하면 점 3 을 얻는다. 다시 점 3 에서 출발하여 h2 방향으로 탐색하여 최대값 점 4 를 구한다. 점 4 에서 다시 h3 방향으로 탐색하여 점 5 를 구한다. 여기서 점 5 와 점 3 은 두 개의 다른 점들에서 h3 방향으로 탐색하여 얻어진 결과임을 관찰한다.

Powell 은 점 3 과 점 5 를 연결해서 얻어진 h4 방향과 h3 방향이 공액 방향임을 보인 바 있다. 따라서 점 5 를 출발하여 방향 h4 를 따라 탐색하면 바로 최대값에 이르게 된다.

Gradient Methods

1. gradient 및 헤시안

 1 차원 함수의 1 차 도함수는 미분되는 함수의 기울기나 접선을 나타낸다. 예를 들어 기울기가 양수이면 독립변수의 값이 증가할수록 우리가 탐색하는 함수값이 증가할 것이라는 사실을 알고 있다.

 1 차 도함수값이 최적값에 도달했는지를 판별해준다. 왜냐하면 최적값에서는 도함수값이 0 이 되기 때문이다. 더욱이 2 차 도함수의 부호로부터 최적값이 최소값 (양의 2차 도함수값) 인지, 최대값 (음의 2 차 도함수값) 인지를 구분할 수 있었다.

이러한 아이디어는 앞서 살펴본 1 차원의 탐색 알고리즘에 유익하였다. 그러나 다차원 탐색을 충분히 이해하기 위해서는 1 차 및 2 차 도함수가 다차원 환경에서는 어떻게 표현되는지를 먼저 이해해야 한다.

2 차원 함수 f(x, y) 가 주어졌다고 가정하자. 예를 들면 이 함수를 산에서 우리의 위치 함수로 나타낸 고도라고 생각해 보자. 우리가 산 위의 (a, b) 라는 위치에 있으며, 임의의 방향으로의 경사를 알고 싶다고 가정하자. 방향을 정의하는 한 방법은 x 축과 θ 의 각도를 이루는 새로운 축 h 를 따르는 것이다. 이 새로운 축을 따르는 고도는 g(h) 라는 새로운 함수로 여겨질 수 있다.

x축과 a의 각을 이루는 축 h를 따라 정의된다.

현재의 위치를 이 축의 시작점으로 정의한다면 (즉, h = 0), 이 방향으로의 기울기는 g'(0) 로 구해진다. 방향미분 (directional derivative) 이라고 불리는 이 기울기는 x 축과 y 축을 따르는 편미분식으로부터 다음과 같이 계산된다.

여기서 편미분값들은 x = a, y = b 에서 계산된 값들이다.

우리의 목적이 그 다음 단계에서 가장 많이 오르는 것이라면 다음의 논리적인 질문은 "어느 방향이 가장 급한 경사를 갖는가?" 라는 것이다. 이 질문에 대한 대답은 다음과 같이 수학적으로 정의된 구배에 의해 주어진다.

 

이 벡터는 "del f" 로 불려지며, x = a, y = b 점에서의 f(x, y) 의 방향미분을 나타내게 된다.

최상향 방향을 정하는 것과는 별도로 1 차 도함수는 최적값에 도달했는지를 판별하는데 사용된다. 1 차원 함수의 경우와 같이 x, y 에 대한 편미분 값이 모두 0 이 되면 2 차원 최적값에 도달하게 된다.

헤시안 (Hessian) - 1 차원 문제에 대해서는 1 차 및 2 차 도함수 모두는 최적값을 찾는 가치 있는 정보를 제공해 준다. 1 차 도함수는 (a) 함수의 최고 경사 궤적을 알게 하며, (b) 최적값에 도달했는지를 말해준다. 일단 최적값에 도달하면, 2 차 도함수는 최대값인지 (음의 f''(x)), 혹은 최소값인지 (양의 f''(x)) 도 잘 판별해준다.

2. 최상향법

언덕을 오르는 분명한 전략은 당신의 출발점에서 최대 경사값을 결정한 후, 그 방향으로 걸어가는 것이다. 그러나 이 경우 다른 문제가 바로 발생한다. 운이 좋게도 정상으로 뻗어있는 산등성을 따라 출발한 경우가 아니라면, 당신의 경로는 최상향 방향에서 벗어날 수 있다.

이 사실을 염두에 두고 다음의 전략을 선택해 보자. 기울기의 방향을 따라 짧은 거리를 움직인 후 정지한다. 그리고 다시 기울기를 구한 후, 또 다른 짧은 거리를 이동한다. 이 과정을 반복하면 결국 정상에 오르게 된다.

비록 이 전략이 피상적으로 좋아 보여도 매우 실제적인 방법은 못된다. 특히 구배를 계속해서 구하는 것은 많은 계산시간을 필요로 하기 때문이다. 다른 좋은 방법은 최초의 기울기방향으로 움직이되 f(x, y) 값이 더 이상 증가하지 않을 때까지, 예를 들면 이동 방향으로 평탄해질 때까지 이동하는 것이다. 이 정지점은 다시 ∇f 가 계산되어 새로운 방향이 정해지는 출발점이 된다. 이 과정을 정상에 도달할 때까지 반복하는 것이다.

이러한 방법을 최상향법 (Steepest Ascent Method) 이라고 부르며, 기울기 탐색법들 중에서 가장 분명한 방법이다.

우리는 그림에서 "0" 이라고 표시된 초기 위치 (x0, y0) 에서 출발한다. 이 점에서 최상향 방향인 기울기를 결정한다. 우리는 그림에서 "1" 이라고 표기된 최대 값을 찾을 때까지 기울기 방향인 h0 를 따라 탐색한다. 그 후 이러한 과정을 반복한다.

따라서 이 문제는 두 부분으로 나누어 진다. 첫째는 탐색의 "최선" 의 방향을 정하는 것이고, 둘째는 그 탐색방향을 따라서 "최선의 값" 을 결정하는 것이다. 따라서 알고리즘의 효율성은 이 두 가지 점을 얼마나 현명하게 만족시키냐에 달려 있다.