함수의 최솟값 탐색

이 단원에서는 임의의 1변수 함수의 최소값을 찾는 기능들을 기술합니다. 라이브러리에서는 다양한 반복 풀이와 수렴 테스트를 위한 저수준의 기능들을 제공합니다. 이 기능들은 반복 단계를 완전히 제어할 수 있어, 잘 이용하면 사용자가 요구하는 적절한 해를 찾을 수 있습니다. 각각의 풀이 방법은 같은 작업 환경을 사용하기 때문에, 프로그램을 재컴파일 할 필요없이 여러 풀이 방법을 구동 중에 바꿀 수 있습니다. 각각의 풀이 인스턴스들은 스스로 상태를 추적하기 때문에, 다중 스레드 프로그램에서도 사용이 가능합니다.

이 단원에서 기술하는 함수들의 원형은 gsl_min.h 에 기술, 정의되어 있습니다.

이를 이용해서 함수의 최대값을 찾으려 하는 경우, 간단히 함수의 부호를 반대로 바꾸어 적용하면 됩니다.

개요

최소화 알고리즘은 최소값을 가지고 있다고 여겨지는 제한된 구간에서 시작합니다. 이 구간은 $x$ 의 하한 값 $a$ 와 상한 값 $b$ 로 구성됩니다.

Fig 27.을 참고하십시오.

../_images/min-interval.png — 그림 24 상하한 값이 주어진 닫힌 구간의 함수의 최소값 추정 장면.

$x$ 지점에서의 함수 값은 반드시 구간의 끝에서의 함수 값들보다 작아야 합니다.

\[f(a) > f(x) < f(b)\]

이 조건은 최소값이 주어진 구간 속 어딘가에 속해있다는 것을 보장해 줍니다. 각각의 반복 과정에서 새로운 지점 $x'$ 가 알고리즘에 의해 선택됩니다. 만약 새로운 지점이 최소값을 더 잘 근사한다면, 예를 들어 $f(x')<f(x)$ 일 경우, 현재 근사 최소값 $x$ 를 $x'$ 으로 갱신합니다. 새로운 지점은 $f(a) > f(x) < f(b)$ 조건을 만족하는 가장 작은 점 집합을 선택해, 주어진 닫힌 구간의 크기를 줄일 수 있게 합니다. 각 단계를 거치면서 주어진 구간의 크기는 함수의 최소 값이 적절한 상태에 이루기까지 계속 줄어듭니다. 이 과정에서 최소 지점의 근사값과 오차 값을 평가해 반환합니다.

이러한 최소화 과정 알고리즘은 괄호법(Bracket algorithm)에 속합니다. 라이브러리에서는 이러한 괄호법 알고리즘들을 동일한 작업공간에서 작동할 수 있게 구현했습니다. 사용자가 알고리즘을 사용할 수 있는 고수준의 프로그램을 작성하면, 라이브러리는 각각의 단계에 필요한 개별 함수들을 제공할 수 있습니다.

라이브러리에서 이러한 최소값 탐색 과정은 3가지로 나뉘어집니다.

알고리즘 $T$ 대한, 최소화 공간 $s$ 선언.
$T$ 를 수행해 $s$ 갱신.
$s$ 가 수렴하는 지 판별, 필요하면 계속 반복.

최소화 공간의 상태는 $gsl_min_fminimizer$ 구조체로 주어집니다. 각 상태의 갱신은 도함수를 사용하지 않고 함수 값만을 사용해 이루어집니다.

주의 사항

유의해야 할 사항은 최소한 함수들이 한번에 한 개의 최소값을 찾는 다는 점입니다. 만약, 주어진 구간에 여러 최소값이 존재한다면 대부분의 경우 첫번째 최소값이 반환됩니다. 하지만 다양한 상황이 존재해 어떤 최소값이 반환될 지 예측하기는 어렵습니다. 대부분의 경우 여러 최소값이 존재하는 구간에서 근을 찾을 때, 오류가 반환되지는 않습니다.

제공하는 모든 최소화 알고리즘을 사용과정에서, 최소값의 위치를 자료형의 최대 정밀도로 파악하기는 어렵습니다. 주어진 구간의 최소값 $x^*$ 에서 함수의 개형은 테일러 근사로 근사할 수 있습니다.

\[y= f(x^{*}) + \frac{1}{2} f''(x^{*}) (x-x^{*})^2\]

여기서 두 번째 항은 자료형의 정밀도 한계로 인해 첫 번째 항에 더해질 때, 손실될 수 있습니다. 이때, $x^*$ 에서 오차가 증폭되어, $\sqrt{\epsilon}$ 에 비례하게 됩니다. $\epsilon$ 은 부동 소수점의 상대 오차를 의미합니다. 고차항의 최소 지점을 가지는 함수들( 예를 들어 $x^4$ )은 이러한 오차 증폭 정도가 더 증가합니다. 가장 좋은 방법은 최솟 값의 위치보다는 함수 값의 정밀도에 집중하는 것입니다.

최소화 설정하기

type gsl_min_fminimizer: 최소화 함수를 위한 작업공간을 나타냅니다.

gsl_min_fminimizer *gsl_min_fminimizer_alloc(const gsl_min_fminimizer_type *T)

$T$ 형태로 할당된 새 최소화 작업공간의 주소 포인터를 반환합니다. 예를 들어서, 다음 코드는 황금비 최소화 작업 공간을 할당해 반환합니다.

const gsl_min_fminimizer_type * T = gsl_min_fminimizer_goldensection;
gsl_min_fminimizer * s = gsl_min_fminimizer_alloc (T);

만약, 메모리 환경으로 인해 새로운 최소화 공간 할당이 불가능하다면, NULL 포인터를 반환하고, 오류 관리자가 호출되어 $GSL_ENOMEM$ 코드를 전달합니다.

int gsl_min_fminimizer_set(gsl_min_fminimizer *s, gsl_function *f, double x_minimum, double x_lower, double x_upper)

최소화 공간 $s$ 를 초기화 하거나 재설정합니다. 주어진 함수 $f$ 초기 탐색 범위 [ $x_lower$ $x_upper$ ] 를 사용하도록 설정하며, 초기 최소 지점은 $x_minimum$ 로 추정합니다.

만약, 주어진 범위가 최소 지점을 포함하고 있지 않다면, 함수는 $GSLL_EINVAL$ 오류 값를 반환합니다.

int gsl_min_fminimizer_set_with_values(gsl_min_fminimizer *s, gsl_function *f, double x_minimum, double f_minimum, double x_lower, double f_lower, double x_upper, double f_upper): $gsl_minn_fminimizer_set()$ 함수와 같습니다. 하지만, $f_minimum$ , $f_lower$ , 그리고 $f_upper$ 를 $f(x_minimum)$ , $f(x_lower)$ , 그리고 $f(x_upper)$ 대신 사용해 계산합니다.

void gsl_min_fminimizer_free(gsl_min_fminimizer *s): 최소화 공간 $s$ 메모리를 해제합니다.

const char *gsl_min_fminimizer_name(const gsl_min_fminimizer *s)

최소화 공간의 최소화 방법 이름을 가리키는 포인터를 반환합니다. 예를 들어서,

printf("s is a '%s' minimizer\n", gsl_min_fminimizer_name(s));

은 $s is a 'brent' minimizer$ 를 출력합니다.

최소화 함수

최소화를 시킬 함수는 반드시 1 변수 연속 함수여야 합니다. 일반적인 계수들을 지원하기 위해 $gsl_function$ 데이터 형을 이용합니다. (근을 찾을 함수 참고)

반복

다음 함수들은 주어진 알고리즘들을 반복 실행합니다. 각 함수는 최소화 공간의 상태를 주어진 최소화 알고리즘으로 갱신합니다. 모든 최소화 방법에 대해, 같은 함수를 사용가능합니다. 때문에, 별도의 코드 수정 없이 실행 도중에 다른 방법들을 선택할 수 있습니다.

int gsl_min_fminimizer_iterate(gsl_min_fminimizer *s)

최소화 공간 $s$ 갱신합니다. 만약, 갱신 도중 예상치 못한 문제가 생긴다면 다음의 오류 값가 반환됩니다.

GSL_EBADFUNC: 이 오류 값은 함수 값이 $Inf$ 나 $NaN$ 가 되는 특이점이 나올 경우 반환됩니다.

GSL_FAILURE: 알고리즘이 현재 최적 근사 값이나 구간을 더 최적화 하지 못할 때 반환됩니다.

최소화 공간은 항상 현재의 최적 추정값을 유지하고 보유 구간은 항상 최소 지점을 포함하고 있습니다. 이 정보들은 다음의 보조 함수들로 접근할 수 있습니다.

double gsl_min_fminimizer_x_minimum(const gsl_min_fminimizer *s): 최소화 공간 $s$ 의 현재 최적 추정치를 반환합니다.

double gsl_min_fminimizer_x_upper(const gsl_min_fminimizer *s)
double gsl_min_fminimizer_x_lower(const gsl_min_fminimizer *s): 최소화 공간 $s$ 의 현재 구간 양 끝 값을 반환합니다.

double gsl_min_fminimizer_f_minimum(const gsl_min_fminimizer *s)
double gsl_min_fminimizer_f_upper(const gsl_min_fminimizer *s)
double gsl_min_fminimizer_f_lower(const gsl_min_fminimizer *s): 최소화 공간 $s$ 의 현재 최적 추정값, 구간 양 끝 값에서의 함수 값들을 반환합니다.

탐색 정지 인자들

최소화 과정은 다음의 조건들 중 하나를 만족하면 멈추게 됩니다.

최소값이 사용자가 정의한 정밀도에 맞게 찾아진 경우,
사용자 정의 최대 반복 횟수를 넘어선 경우.
오류가 생긴 경우.

이러한 조건들은 사용자가 직접 설정할 수 있습니다. 아래의 함수는 현재 결과의 정밀도를 측정할 수 있게 해 줍니다.

int gsl_min_test_interval(double x_lower, double x_upper, double epsabs, double epsrel)

이 함수는 구간 [ $x_lower$ $x_upper$ 의 수렴을 절대 오차 $epsabs$ 상대 오차 $epsrel$ 판별합니다. 판정 결과는 다음의 조건을 만족했을 때, $GSL_SUCESS$ 반환합니다.

구간 $x = [a,b]$ 가 원점을 포함하지 않을 때,: $$|a-b| < epsabs + epsrel \text{ min}(|a|,|b|)$ $

만약 구간이 원점을 포함하고 있다면, $\text{min}(|a|,|b|)$ 는 0으로 바뀝니다. 이런 과정을 통해 원점에 가까운 최소값에 대해 상대오차를 정확하게 추정할 수 있습니다.

추정 최소값 $x_m$ 과 실제 최소값 $x_m^*$ 에 대해서도 같은 조건을 쓸 수 있습니다. 구간에 $x_m^*$ 이 존재한다는 가정하에 다음을 볼 수 있습니다.

$$|x_m-x_m^*| < epsabs + epsrel \cdot x_m^*$ $

최소화 알고리즘

이 단락에서 기술할 최소화 알고리즘은 최소값이 포함되어있음을 보장하는 초기 추정 구간이 주어져야합니다. 만약, $a,b$ 가 구간의 끝 값들이고 $x$ 가 최소값 지점을 나타내면, $f(a) > f(x) < f(b)$ 를 만족해야 합니다. 이 조건은 함수가 주어진 구간에서 적어도 1개의 최소값을 가지고 있음을 보장합니다. 만약, 적절한 시작 구간과 함수가 주어진다면, 알고리즘은 제대로 된 값을 반환합니다.

type gsl_min_fminimizer_type

gsl_min_fminimizer_type *gsl_min_fminimizer_goldensect

황금비 알고리즘(Golden section algorithm) 은 가장 간단한 괄호법을 이용하는 최소화 알고리즘입니다. 이는 선형 수렴하며 라이브러리에서 제공하는 알고리즘 중 가장 느린 알고리즘입니다.

각각의 반복 단계에서, 알고리즘은 먼저 끝 지점에서 현재 구해진 최소 지점으로 이루어진 부분 구간을 비교합니다. 더 큰 부분 구간은 황금비( $(3-\sqrt{5})/2 \approx 0.3819660$ )로 분할합니다. 그리고 이렇게 만들어진 새로운 지점의 함수값을 계산합니다. 주어진 최소점 조건 :math:` f(a) > f(x) < f(b)` 을 이용해서, 나머지 지점을 제외하고 최소 지점을 포함하는 새로운 구간을 찾습니다. 이 과정은 구간이 충분히 작아질 때까지 계속 반복됩니다. 황금비로 구간을 이분하는 것은 이러한 알고리즘에서 가장 빠르게 수렴한다고 알려져 있습니다.

gsl_min_fminimizer_type *gsl_min_fminimizer_brent

브렌트 최소 알고리즘(Brent minimization algorithm) 은 포물선 보간법을 황금비 탐색 알고리즘과 함께 이용합니다. 이 방법은 충분히 빠르면서도 좋은 결과를 내놓습니다.

알고리즘의 진행과정은 다음과 같이 요약될 수 있습니다. 각각의 반복 단계에서 브렌트 알고리즘은 포물선과 주어진 구간의 세 지점을 이용해 함수를 근사합니다. 포물선의 최소 지점이 최소값으로 추정이 되고, 만약 이 값이 현재 구간에 포함된다면, 보간 지점이 받아들여지고 이를 이용해 더 작은 구간을 만들게 됩니다. 만약 보간 지점이 받아들여지지 않을 경우 기존의 황금비 방법을 사용해 새 구간을 형성합니다. 브렌트 방법은 수렴성을 높이기 위한 추가 검토 절차를 포함합니다.

gsl_min_fminimizer_type *gsl_min_fminimizer_quad_golden: 이 알고리즘은 브랜트 알고리즘에 길과 머레이(Gill and Murray)가 만든 단계 길이 보호 알고리즘을 더한 방법입니다.

예제

다음 코드는 브랜트 알고리즘을 이용해서 함수 $f(x) = \cos(x) +1$ 의 최소값을 찾는 프로그램입니다. 해당 함수의 최소값은 $x= \pi$ 지점입니다. 시작 구간은 $(0,6)$ , 초기 추정 최소값은 $2$ 입니다.

#include <stdio.h>
#include <gsl/gsl_errno.h>
#include <gsl/gsl_math.h>
#include <gsl/gsl_min.h>

double fn1 (double x, void * params)
{
  (void)(params); /* avoid unused parameter warning */
  return cos(x) + 1.0;
}

int
main (void)
{
  int status;
  int iter = 0, max_iter = 100;
  const gsl_min_fminimizer_type *T;
  gsl_min_fminimizer *s;
  double m = 2.0, m_expected = M_PI;
  double a = 0.0, b = 6.0;
  gsl_function F;

  F.function = &fn1;
  F.params = 0;

  T = gsl_min_fminimizer_brent;
  s = gsl_min_fminimizer_alloc (T);
  gsl_min_fminimizer_set (s, &F, m, a, b);

  printf ("using %s method\n",
          gsl_min_fminimizer_name (s));

  printf ("%5s [%9s, %9s] %9s %10s %9s\n",
          "iter", "lower", "upper", "min",
          "err", "err(est)");

  printf ("%5d [%.7f, %.7f] %.7f %+.7f %.7f\n",
          iter, a, b,
          m, m - m_expected, b - a);

  do
    {
      iter++;
      status = gsl_min_fminimizer_iterate (s);

      m = gsl_min_fminimizer_x_minimum (s);
      a = gsl_min_fminimizer_x_lower (s);
      b = gsl_min_fminimizer_x_upper (s);

      status
        = gsl_min_test_interval (a, b, 0.001, 0.0);

      if (status == GSL_SUCCESS)
        printf ("Converged:\n");

      printf ("%5d [%.7f, %.7f] "
              "%.7f %+.7f %.7f\n",
              iter, a, b,
              m, m - m_expected, b - a);
    }
  while (status == GSL_CONTINUE && iter < max_iter);

  gsl_min_fminimizer_free (s);

  return status;
}

다음은 작성한 최소화 프로그램의 결과입니다.

using brent method
 iter [    lower,     upper]       min        err  err(est)
[0.0000000, 6.0000000] 2.0000000 -1.1415927 6.0000000
[2.0000000, 6.0000000] 3.5278640 +0.3862713 4.0000000
[2.0000000, 3.5278640] 3.1748217 +0.0332290 1.5278640
[2.0000000, 3.1748217] 3.1264576 -0.0151351 1.1748217
[3.1264576, 3.1748217] 3.1414743 -0.0001183 0.0483641
[3.1414743, 3.1748217] 3.1415930 +0.0000004 0.0333474
Converged:
[3.1414743, 3.1415930] 3.1415927 +0.0000000 0.0001187

참고 문헌과 추가 자료

브렌트 알고리즘 (Brent Algorithm)에 대한 추가 정보를 얻고 싶다면, 음을 참고할 수 있습니다.

Richard Brent, Algorithms for minimization without derivatives, Prentice-Hall (1973), republished by Dover in paperback (2002), ISBN 0-486-41998-3.