비구속 최적화

(Unconstrained   Optimization)

공학도를 위한 수치해석 : Steven C. Chapra, Raymond P. Canale 저, 김철.김태국.나양.신동신.이승배 공역, McGraw-Hill Korea, 2002 (원서 : Numerical Method for Engineers, 4th ed), Page 337~362

일차원 비구속 최적화 (One-Dimensional Unconstrained Optimization)

1. 황금분할법 (Golden-Section Search)

2. 2차 보간법 (Quadratic Interpolation)

3. Newton 법

다차원 비구속 최적화 (Multidimensional Unconstrained Optimization)

4. 직접법 (Direct Methods)

  1. 임의 탐색

  2. 단변분 및 패턴탐색

5. 구배법 (Gradient Methods)

  1. 구배 및 헤시안

  2. 최상향법

일차원 비구속 최적화 (One-Dimensional Unconstrained Optimization)

본 장은 단일변수 혹은 다변수 함수인 f(x) 의 최소값과 최대값을 구하는 방법을 설명한다. 이 내용과 관련된 이미지는 그림 1 에 보여진 1 차원 함수의 "롤러 코우스터 (roller coaster)" 모형이며, 2 차원의 경우에는 산이나 계곡과 같은 가시적 현상이 된다 (그림 2). 더 고차원 문제의 경우에는 알맞은 시각적 형상이 불가능하다.

그림 1  +∞ 와 -∞ 에서 점근적으로 0 의 값에 접근하며 원점근처에서
두 개의 극대값과 두 개의 극소값을 갖는 함수가 주어진다.
오른쪽에 있는 두 개의 극점은 국부적 최적값에 해당하고 왼쪽에 있는
두 개의 극점은 전체 최적값이 된다.

그림 2  이차원 탐색을 가시화하는 가장 손쉬운 방법은 산정상으로
오르거나 (최대화), 계곡으로 내려가는 것 (최소화) 이다.
(a) 는 (b) 에 나타난 3 차원 산에 해당하는 2 차원 지형도이다.

한 개의 함수에 대해 여러 개의 근이 존재하는 것으로 인해서 근 구하기가 매우 복잡해지는 것을 제 2 부에서 살펴본 바 있다. 최적화 문제에서도 마찬가지로 국부적 최적값과 전체 최적값이 모두 나타난다. 이런 경우를 다모드 (multimodal) 문제라고 한다. 대부분의 경우 우리는 함수의 절대적 최대값과 최소값을 찾는데 관심을 갖는다.

국부적 극대/극소값과 전체 최대/최소값을 구분하기는 일반적인 경우 매우 어려운 문제다. 이러한 문제를 다루는 일반적인 세 가지 방법을 살펴보자.

첫째, 저차원 함수의 거동에 대한 고찰을 그래프적으로 하는 방법이다. 둘째, 넓게 변동하는 매우 불규칙한 초기 추측값들을 사용하여 최적값들을 찾은 후 가장 큰 값을 전체 최적값으로 취하는 방법이다. 마지막으로 국부적인 최적값과 연관된 초기값들을 교란한 후 더 나은 값으로 옮기는지, 아니면 항상 같은 값으로 돌아오는지를 살펴보는 방법이다.

근 구하기에서처럼 1 차원의 최적화는 구간법과 개구간법으로 나누어진다. 다음 절에서 설명하듯이 황금분할법은 한 개의 최적값을 둘러싼 초기 추측값들에 의한 구간법의 예가 된다. 이 방법보다 더 정교한 구간법인 2 차 보간법을 이어서 설명한다. 1 차원 비구속 최적화의 다른 방법은 최대, 최소값을 f'(x) = 0 으로부터 구하는 방법으로 수학식에 기초한 개구간법이다. 이러한 방법 중 하나인 Newton 법을 소개한다.

다차원 비구속 최적화인 기술은 여러 가지 방법으로 분류될 수 있다. 여기서는 본 장의 설명을 위해 도함수 계산의 필요 여부에 따라 분류하려고 한다. 즉, 도함수를 구할 필요가 없는 방법은 비구매법 혹은 직접법이라 하고, 도함수 결정이 필요한 방법은 구배법 혹은 하향법 (혹은 상향법) 이라고 한다. 다차원 비구속 최적화 문제는 직접법과 구배법으로 나누어 설명하려 한다.

1. 황금분할법 (Golden-Section Search)

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

황금분할탐색법은 단순하며 일반적으로 적용 가능한 단일변수 탐색방법이다. 제 5 장에서 근을 구하기 위한 이분법과 맥을 같이한다. 이분법은 한 개의 근을 둘러싼 하부추측값 (x_l) 과 상부추측값 (x_u) 에 의해 나타내지는 구간을 정의하는 것에 기초하였다. 이 방법의 효율은 새로운 x_r 이 그 전의 경계값 중의 하나를 대신하는 것에서 기인하였다.

1 차원 함수의 최적값을 구하는 비슷한 방법을 개발해 보도록 한다. 편의상 최대값을 구하는 문제에 집중한다. 최소값을 구하려면 컴퓨터 알고리즘을 논할 때 약간의 수정만 하면 충분하다.

이분법에서와 같이 한 개의 해를 담는 구간을 먼저 정의한다. 즉, 그 구간에는 한 개의 최대값이 담겨있어야 한다. 이러한 경우를 단 모드 (unimodal) 라고 한다. x_l 과 x_u 가 각각 그 구간의 하부 경계값과 상부 경계값을 나타내는 이분법과 같은 기호를 사용한다. 그러나 이분법과는 달리 구간 내의 최대값을 구하기 위해서는 다른 전략이 필요하다.

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

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

그림 3  황금분할 탐색 알고리즘의 첫 번째 단계는 황금비율에 따라 두 개의 내부 점을 선택하는 것이다.

                                                            (1)

                                                               (2)

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

                                                          (3)

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

                                                           (4)

혹은

                                                      (5)

여기서 실수의 근을 구하면

               (6)

고대로부터 알려져온 이 값은 황금비라고 불린다. 이것을 이용하여 최적값을 효율적으로 얻을 수 있기 때문에 우리가 지금까지 개념적으로 전개해온 황금분할법의 핵심요소가 된다. 이 방법을 컴퓨터에서 구현되도록 알고리즘을 유도하기로 한다.

앞서 언급했고 그림 4 에 나타낸 바와 같이, 이 방법은 f(x) 의 국부적 극점을 포함하는 두 개의 초기 추측값으로 시작한다. 다음은 두 개의 내부점 x₁ 과 x₂ 를 황금비를 이용해서 구한다.

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

1. 그림 4 에서처럼 f(x₁) > f(x₂) 이면 x₂ 의 왼쪽에 있는 x 의 영역, 즉 x_l 로부터 x₂ 까지의 구간을 제거할 수 있다. 왜냐하면 그 구간에는 최대값이 없기 때문이다. 이 경우 x₂ 가 다음 반복 시행의 새로운 x_l 이 된다.

2. f(x₂) > f(x₁) 인 경우 x₁ 의 오른쪽에 있는 영역, 즉 x₁ 부터 x₂ 까지의 구간이 제거된다. 이 경우 x_u 이 다음 반복시행의 새로운 x_u 가 된다.

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

그림 4 (a) 황금분할탐색 알고리즘의 첫 단계는 황금비에 따라 두 개의 내부 점을 선택하는 것이다.
(b) 두 번째 단계는 최적값을 포함하는 새 구간을 정의하는 것이다.

그림 4 에서 볼 수 있듯이 과거의 x₁ 은 새로운 x₂ 가 된다. 이것은 새로운 x₂ 에서의 함수값 f(x₂) 는 과거의 x₁ 에서의 함수값과 같아짐을 의미한다.

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

최적값이 왼쪽의 부분구간 (subinterval) 에서 발생하는 다른 경우에 대해서도 동일하게 적용된다.

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

최대값을 구하는 황금분할탐색 알고리즘에 대한 가상코드가 그림 5a 에 주어져 있으며, 알고리즘을 최소값을 구하는 문제로 바꾸는 수정 내용은 그림 5b 에 나타나 있다. 두 가지 모두 최적값 x 값이 함수값 (gold) 으로 주어진다. 덧붙여서 최적값에서의 f(x) 값은 변수 (fx) 로 주어진다.

아마도 여러분은 왜 황금분할탐색법에서 함수값 계산 수가 줄어드는 것을 강조하는지 다소 의아해 할지도 모른다. 물론 하나의 최적화 문제에 대해서는 계산시간 절약이 미미할 수도 있다. 그러나 함수값 계산 수를 감소시키는 것이 중요한 점 두 가지를 소개하면,

1. 많은 수의 값 계산 - 황금분할탐색 알고리즘이 대형 계산의 일부인 경우가 있다. 이러한 경우에는 여러 번 황금분할탐색 부프로그램을 부르게  된다. 따라서 함수값 계산 수를 최소화하는 것이 매우 유익하다.

2. 계산시간이 많이 드는 함수값의 계산 - 교육적 목적으로 대부분의 예제에서 간단한 함수를 사용하였다. 함수가 매우 복잡해지면 함수값을 구하는 시간이 많이 걸릴 수도 있다. 따라서 이러한 함수값 계산수를 줄이는 방법이 유리하다. 

2. 2차 보간법 (Quadratic Interpolation)

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

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

               (7)

여기서 x₀, x₁, x₂ 는 최적값을 둘러싼다고 여겨지는 추측값들이며, x₃ 는 추측 값들을 2 차식으로 근사할 경우 최대값에 해당한다.

그림 5  황금분할탐색법의 알고리즘

그림 6  2 차보간법의 그래프를 이용한 설명

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

3. Newton 법

제 6 장의 Newton-Raphson 방법은 f(x) = 0 을 만족하는 근 x 를 찾는 개구간법이다. 이 방법은 다음과 같이 요약된다.

비슷한 개구간법을 적용하기 위해 g(x) = f'(x) 로 정의한 후 f(x) 의 최적값을 구한다. 즉, 최적값 x^* 은

f'(x*) = g(x^*) = 0

을 만족하므로, 다음 식을 이용하여 f(x) 의 최소값 혹은 최대값을 구한다.

                                                    (8)

이 식은 f(x) 에 대한 2 차 테일러 급수를 전개한 후 급수의 도함수가 0 이 되도록 하여 유도될 수 있음을 주목하자. Newton 법은 최적값을 포함하는 구간에 대한 초기 추측값이 필요하지 않으므로 Newton-Raphson 법과 유사한 개구간법이 된다. 이 방법에 대한 문제는 함수의 특성과 초기 추측값 선택에 따라 발산할 수 있다는 것이다. 따라서 최적값에 근접했을 경우에만 주로 이 방법이 사용된다. 최적값과 멀리 떨어진 경우에는 구간법을  사용하고 최적값 근처에서는 개구간법을 사용하여 각 방법의 장점을 이용하는 복합방법이 종종 사용된다. 끝으로 이 방법이 원하는 결과로 수렴하는지를 확인하기 위해 2 차 도함수가 올바른 부호를 갖는지를 알아보는 것도 유익한 방법이다. 

4. 직접법 (Direct Methods)

이 방법은 단순한 기초적 계산에서부터 함수의 특성을 조사하여 활용하는 훨씬 개선된 방법까지 다양하다. 먼저 단순한 방법부터 설명한다.

1. 임의 탐색

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

......

본 장에서 기술된 나머지 방법들은 모두 수렴속도를 개선하기 위해 전 단계의 시도결과 뿐만 아니라, 함수의 거동을 고려한다.

2. 단변분 및 패턴탐색

도함수의 계산을 하지 않는 효율적 최적화 방법이 매우 호소력이 있다. 앞서 설명된 임의탐색법은 도함수의 계산이 필요하지는 않았지만 매우 효율적이지도 않았다. 이 절에서는 더욱 효율적이면서도 도함수의 계산이 필요하지 않는 단변분 (univariate) 탐색법을 소개한다.

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

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

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

그림 7  단변분 탐색이 어떻게 수행되는지를 그래프를 이용하여 나타냄

그림 8  공액 방향들

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

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

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

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

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

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

그림 9  Powell 법

5. 구배법 (Gradient Methods)

이름이 의미하는 바와 같이 최적값을 구하기 위해 구배와 관련된 정보를 이용하는 방법이다. 자세한 내용을 설명하기 앞서 먼저 주요한 수학적 개념과 연산에 대해서 살펴본다.

1. 구배 및 헤시안

대학 수학에서 1 차원 함수의 1 차 도함수는 미분되는 함수의 기울기나 접선을 나타낸다고 배웠다. 최적화의 관점에서 보면 이것은 매우 유용한 정보가 된다. 예를 들어 기울기가 양수이면 독립변수의 값이 증가할수록 우리가 탐색하는 함수값이 증가할 것이라는 사실을 알고 있다.

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

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

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

그림 10  방향 구배는 x 축과 θ 의 각을 이루는 축 hh 를 따라 정의된다.

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

                                       (9)

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

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

                                               (10)

이 벡터는 "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 차 도함수가 어떻게 활용되는지를 알아보자.

그림 11  안장점 (x = a, y = b). x, y 방향을 따라서는 함수가 최소점 (양의 2 차 도함수) 을 통과하는 것처럼 보이는 반면, x = y 인 축을 따라서는 아래에서 볼록한 형상 (음의 2 차 도함수) 을 갖는다.

만일 x, y 에 대한 2 차 편미분 도함수 모두가 음수이면 최대값을 갖는 것으로 예상할 수 있다. 그림 11 은 이것이 반드시 옳지는 않은 경우를 보여준다. 이 그래프의 점 (a, b) 는 x 축, 혹은 y 축을 따라 관찰하면 최소값처럼 보인다. 두 방향 모두에 대한 2 차 도함수가 곧 양수를 말한다. 그러나 함수를 y = x 직선을 따라 관찰하면 최대점이 같은 점에서 발생함을 알 수 있다. 이러한 형상을 안장 (saddle) 점이라고 부르며, 이 점은 분명히 최대값이나 최소값도 아니다.

최대값이나 최소값이 일어나는지의 여부는 x, y 에 대한 1 차 편미분 도함수 뿐만 아니라 2 차 편미분 도함수도 필요하다. 계산하려는 점 근처에서 편미분 도함수가 연속이라면 다음의 물리량이 계산될 수 있다.

                                               (11)

여기서 세 가지의 경우가 발생한다.

• 만일 |H| > 0 이고 ∂²f / ∂x² >0 이면, f(x, y) 는 국부적 최소값을 갖는다.
• 만일 |H| > 0 이고 ∂²f / ∂x² < 0 이면, f(x, y) 는 국부적 최대값을 갖는다.
• 만일 |H| < 0 이면 f(x, y) 는 안장점을 갖는다.

|H| 는 2 차 도함수들로 구성된 행렬의 판별식과 같다.

                                                     (12)

여기서 이 행렬은 공식적으로 f 의 헤시안이라고 불린다.

다차원 함수가 최적값에 도달했는지를 구분하는 방법 외에도, 헤시안은 최적화에서 다른 활용도를 갖는다 (예를 들면, 다차원 형태의 Newton 법). 특별히 더 나은 결과를 얻기 위해 2 차의 곡률을 포함하는 탐색을 가능하게 한다.

2. 최상향법

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

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

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

이러한 방법을 최상향법 (Steepest Ascent Method) 이라고 부르며, 구배 탐색법들 중에서 가장 분명한 방법이다. 이 방법의 기본 아이디어는 그림 12 에 잘 나타나 있다.

그림 12  최상향법의 그래프적 표현

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

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

당분간 최상향법은 "최선" 의 방향 선택을 위해 구배법을 이용한다. 어떻게 구배의 값을 구하는지는 이미 예제 4 에서 살펴보았다. 최상향 방향을 따라 최대값을 구하도록 어떻게 알고리즘을 구성하는지를 살펴보기 전에, x, y 의 함수를 구배 방향을 따르는 h 의 함수로 변환하는지를 살펴보기로 한다.

점 x₀, y₀ 에서 출발한 구배 방향의 임의의 점의 좌표는 다음과 같이 표시된다.

                                                           (13)

                                                           (14)

여기서 h 는 h 축을 따르는 거리이다. 예를 들어, x₀ = 1 과 y₀ = 2 그리고 ∇f = 3i +4j 를 그림 13 과 같이 가정하자. h 축을 따르는 점들의 좌표는 다음과 같다.

x = 1 + 3h                                                              (15)

y = 2 + 4h                                                              (16)

다음 예제는 이러한 변환을 이용하여 x, y 의 2 차원 함수를 h 의 1 차원 함수로 어떻게 변환하는지를 보여준다.

그림 13  임의의 방향 h 와 x, y 좌표 사이의 관계

지금까지는 최상향의 경로를 따르는 함수를 구하였으므로 두 번째 질문에 대한 답을 구한다. 즉, "이 경로를 따라 얼마나 멀리 갈 것인가?" 이다. 여기서 한 가지의 방법은 이 함수가 최대값이 될 때까지 진행하는 것이다. 이러한 최대값의 위치를 h^* 라고 부르기로 한다.

이것은 구배방향으로 g (결국 f) 를 극대화하는 거리의 값이 된다. 이 문제는 단변수 h 의 함수는 최대값을 구하는 문제와 같다. 이것은 앞 절에서 다룬 여러 가지의 1 차원 탐색법을 사용해서 구한다. 따라서 2 차원 함수의 최대값을 구하는 문제를 구배 방향으로 1 차원 탐색을 수행하는 문제로 바꾸었다.

이 방법은 임의의 이동 간격 크기 h 가 사용될 때 최상향법이라고 불린다. 만일 구배 방향을 따라 최대값에 도달하는 단 하나의 이동 간격인 h^* 의 값이 구해지면 이 방법은 최적 최상향법이라고 불린다.

최상향법은 선형적으로 수렴함을 보일 수 있다. 이 방법은 길고 좁은 능선을 따라서는 매우 천천히 움직인다. 이것은 각 최대값의 점에서 구한 구배의 방향이 전 방향과 수직하기 때문이다. 따라서, 이 방법에서는 정상까지 오르는데 서로 교차하는 많은 작은 스텝들이 필요하게 된다. 이 방법이 신뢰성이 있기는 하지만 최적값의 근처에서 보다 빨리 수렴하는 다른 방법들이 있다.