[Optimization] Nelder-Mead method (넬더-미드 방법)

1. 개요

Nelder-Mead 방법은 미분 불가능하거나, 노이즈가 많은 함수의 최솟값을 찾기 위한 미분 없는 수치 최적화 기법이다. 1965년 John Nelder와 Roger Mead가 제안한 알고리즘으로, 특히 파라미터 수가 많지 않은 저차원 문제에서 널리 사용된다.

그라디언트를 이용하는 방법과 달리, 넬더 미드 방법은 미분 없이 함수값 $f(x)$가 작을수록 더 좋은 점이라고 판단하고, 가장 함수값이 큰 점(= 최악의 점)을 반사·수축·축소해서 없애는 방식이다. 즉! 경사하강법의 '기울기를 타고 내려간다'는 개념을, 기울기 없이 함수값 크기 비교만으로 흉내내는 방식이라고 할 수 있다.

2. 기본 아이디어

이 방법은 $n$차원 공간에서 $(n+1)$개의 점으로 이루어진 단순체(simplex)를 움직이며 최적점을 탐색한다.

• 2차원: 삼각형
• 3차원: 사면체
• n차원: $(n+1)$개의 점이 만드는 단순 다면체

이 단순체를 반복적으로 반사(reflection), 팽창(expansion), 수축(contraction), 축소(shrink) 시키면서 함수 값이 더 작은 쪽으로 단순체를 이동시킨다.

3. 알고리즘 단계

Step 0: 초기화

• $(n+1)$개의 시작점 $\{x_1, x_2, \dots, x_{n+1}\}$을 선택
• 각 점에서 함수 값 $f(x_i)$를 계산

Step 1: 정렬

• 함수 값을 기준으로 정렬:
  $f(x_1) \leq f(x_2) \leq \dots \leq f(x_{n+1})$
• $x_1$: 최적점 후보
• $x_{n+1}$: 최악점

Step 2: 반사 (Reflection)

• 단순체의 나머지 점들의 중심을 계산.

  $x_c = \frac{1}{n} \sum_{i=1}^{n} x_i$

• 반사점 계산.

  $x_r = x_c + \alpha (x_c - x_{n+1})$

  (일반적으로 $\alpha = 1$)

• $f(x_r)$를 계산하고 다음 경우로 나눈다:

  1. $f(x_1) \leq f(x_r) < f(x_n)$ → 반사 성공* → $x_r$를 대체
  2. $f(x_r) < f(x_1)$ → 팽창 단계로 이동
  3. $f(x_r) \geq f(x_n)$ → 수축 단계로 이동

Step 3: 팽창 (Expansion)

• 팽창점 계산:

  $x_e = x_c + \gamma (x_r - x_c)$

  (일반적으로 $\gamma = 2$)

• $f(x_e) < f(x_r)$이면 → $x_e$ 채택

• 그렇지 않으면 → $x_r$ 채택

Step 4: 수축 (Contraction)

• 내부 수축 (if $f(x_r) < f(x_{n+1})$):

  $x_{con} = x_c + \rho (x_r - x_c)$

• 외부 수축 (if $f(x_r) \geq f(x_{n+1})$):

  $x_{con} = x_c + \rho (x_{n+1} - x_c)$

  (일반적으로 $\rho = 0.5$)

• $f(x_{con})$이 개선되면 → 채택, 그렇지 않으면 → 축소 단계.

Step 5: 축소 (Shrink)

모든 점을 최적점 $x_1$ 방향으로 이동한다.

(일반적으로 $\sigma = 0.5$)

Step 6: 수렴 검사

• $f(x_i)$ 값의 분산이나 단순체 크기가 작아졌는지 확인
• 수렴 조건 만족 시 종료

4. 파라미터 요약

이름	기호	일반값	의미
반사 계수	$\alpha$	1	기본 반사 속도
팽창 계수	$\gamma$	2	반사보다 더 나아감
수축 계수	$\rho$	0.5	반사 실패 시 뒤로 물러남
축소 계수	$\sigma$	0.5	전체 단순체 축소

5. 장점/단점

장점

• 미분이 필요 없다.
• 구현이 간단하고 직관적이다.
• 저차원 문제에 효과적이다.

단점

• 고차원에서는 비효율적이다
• 수렴 속도가 느릴 수 있다.
• 로컬 최소값에 빠질 수 있다.

6. 수학적 정당화와 근거

직관적 규칙 기반의 탐색으로 생각하는 편이 합당하다. 경사하강법의 '기울기를 타고 내려간다'는 개념을,
기울기 없이 함수값 크기 비교만으로 흉내내는 방식이라고 볼 수 있다. 다만 글로벌 최소값에 수렴함이 꼭 보장되어있지는 않다. 1998년에 Lagarias et al.이 제한된 조건 하에서 수렴성을 증명했다.(예: 2차원, 함수가 convex하고 매끄러울 때 등등)

7. 최적화 방법 사용 예시

• 우도 함수가 미분 불가능하거나 복잡한 경우
• 목적 함수의 그래디언트 정보를 구할 수 없는 경우
• 작은 차원의 최적화 문제 (예: 2~10차원 정도)

References

• Nelder, J.A., & Mead, R. (1965). A simplex method for function minimization. The Computer Journal, 7(4), 308–313.
• https://en.wikipedia.org/wiki/Nelder–Mead_method