MINUIT Tutorial – Function Minimization (http://seal.web.cern.ch/seal/documents/minuit/mntutorial.pdf)

6 Local and global minima

지금까지 다루었던 내용들은 국소 지역이 최소점을 찾는다는 가정하에 작동했던 방법이었다. 그렇다면 전체 영역에서의 최소점은 어떻게 다루어야 할 것인가에 대한 내용과 Gelfand 알고리즘, Goldstein-Price 방법에 대한 설명으로 문서의 한 장을 할당하고 있다. 자세한 내용은 문서를 참고하도록 하자.

7 Some sample problems for minimization routines

소개한 방법들의 성능 테스트용으로 잘 알려진 함수 예제를 소개한다.

7.1 Rosenbrock’s curved valley

$$F(x, y) = 100(y - x^2)^2 + (1 - x)^2$$

시작 지점은, $ F(-1.2, 1.0) = 24.20 $, 최소지점은 $ F(1.0, 1.0) = 0 $ 이다.

얕은 골짜기가 $ y = x^2+1/200 $ 모양으로 늘어져 있는 이 함수는 어떤 테스트에도 적당한 함수다. 골짜기의 상단 부분에서는 covariance 행렬이 positive-definite가 아닌 부분이라 어려움이 다.

7.2 Wood’s function in four parameters

$$F(w, x, y, z) = 100(x - w^2)^2 + (w-1)^2 + 90(x - y^2)^2 + (1-y)^2 \\+ 10.1[(x-1)^2+(z-1)^2] + 19.8 (x-1)(z-1)$$

시작 지점은, $ F(-3, -1, -3, -1) = 19192 $, 최소지점은 $ F(1, 1, 1, 1) = 0 $ 이다.

최소점 근처에서는 잘 작동하는 편이나 그곳에 닿으려면 평평한 부분을 지나쳐야 한다.

7.3 Powell’s quaritic function

$$F(w,x,y,z) = (w + 10x)^2 + 5(y-z)^2 + (x - 2y)^4 + 10(w-z)^4$$

시작 지점은, $ F(3, -1, 0, 1) = 215 $, 최소지점은 $ F(0,0,0,0) = 0 $ 이다.

이 함수는 2차 미분 함수가 최소지점에서 singular하다.

7.4 Fletcher and Powell’s helical valley

$$F(x,y,z) = 100\{[z - 10 \Psi(x, y)]^2 + (\sqrt{(x^2 + y^2)} - 1)^2\} + z^2$$

$$2 \pi \Phi (x,y) = arctan(y/x) \quad \text{for } x\gt0 \\ = \pi + arctan(y/z) \quad \text{for } x\lt 0$$

시작 지점은, $ F(-1, 0, 0) = 2500 $, 최소지점은 $ F(1,0,0) = 0 $ 이다.

F는 $ -0.25 \lt \Phi \lt 0.75 $ 에서만 성립한다. 이 함수는 Rosenbrock 함수와 비슷하나 3차원이다.

7.5 Goldstein and Price function with four minima

$$F(x, y) = (1 + (x + y + 1)^2 * (19 - 14x + 3x^2 - 14y + 6xy, 3y^2)) \\ * (30 + (2x - 3y)^2 * (18 - 32x + 12x^2 + 48y - 36xy + 27y^2))$$

지역 최소점들은,

$$F(1.2, 0.8) = 840 \\
F(1.8, 0.2) = 84 \\
F(-0.6, -0.4) = 30$$

이고, 최소 지점은 $ F(0, -1.0) = 3 $ 이다.

4개의 지역 최소점을 가지고 있고, 많은 영역들에서 non-positive-definite인 특성을 가진다. Saddle point인 $ F(-4.0, -0.6) $ 지점이 주로 시작 지점으로 사용된다.

7.6 Goldstein and Price function with many minima

$$F(x,y) = \exp \{ \frac{1}{2} (x^2 + y^2 - 25)^2 \} + sin^4(4x - 3y) + \frac{1}{2} (2x + y - 10)^2$$

최소점은, $ F(3, 4) = 1 $이나 이 함수는 많은 지역 최소점을 가지고 있다.

7.7 Quadratic function in four parameters

$$F(x,y,z,w) = \frac{1}{70} (21 x^2 + 20y^2 + 19z^2 - 14xz - 20yz) + w^2$$

최소점은, $ F(0,0,0,0) = 0 $ 이고, covariance 행렬은,

$$\begin{pmatrix} 4 && 1 && 2 && 0 \\
1 && 5 && 3 && 1 \\
2 && 3 && 6 && 0 \\
0 && 0 && 0 && 0
\end{pmatrix}$$

이다.

명확한 covariance 행렬 덕분에 그것에 기반한 방법들은 딱 한번의 계산으로 최소지점을 찾을 수 있다. 때문에 프로그램의 디버깅 용으로 제격이다.

7.8 Chebyquad

$$F(\vec{x}) = \sum^n_{i=1} \{ \int^1_0 T_i(x') dx' - \frac{1}{n} \sum^n_{j=1} T_i(x_j) \}^2$$

여기서 $ T_i(x) $는 i차 Chebyshev 다항식이다.
시작 지점은 $ x_j = j/(n+1) $로 주어진다.

7.9 Trigonometric functions of Fletcher and Powel

$$F(\vec{x}) = \sum^n_{i=1} \{ E_i - \sum^n_{j=1}(A_{ij} sin x_j + B_{ij} cos x_j) \}^2 \\
E_i = \sum^n_{j=1}(A_{ij} sin x_{0j} + B_{ij} cos x_{0j} )$$

시작 지점은, $ x_j = x_{0j} + 0.1 \delta _j, \pi \lt \delta j \lt \pi $ 이고, 최소점은 $ F(\vec{x} = \vec{x_0}) = 0 $ 이다.

행렬 A, B는 -100에서 100 사이 정수로 구성된 랜덤 행렬이고, $ x_{0j} $ 또한 $ -\pi \lt x_{0j} \lt \pi $의 한 수이다.

---