7.24 안장점의 식별과 해석

1. 안장점의 정의

다변수 함수 $f: \mathbb{R}^n \to \mathbb{R}$ 의 임계점(critical point) $\mathbf{x}^*$ 에서 그래디언트가 영벡터가 된다.

$\nabla f(\mathbf{x}^*) = \mathbf{0}$

이 임계점이 극소점도 극대점도 아닌 경우, 즉 $\mathbf{x}^*$ 의 임의의 근방에서 $f(\mathbf{x}) > f(\mathbf{x}^*)$ 인 점과 $f(\mathbf{x}) < f(\mathbf{x}^*)$ 인 점이 동시에 존재하는 경우, $\mathbf{x}^*$ 를 안장점(saddle point)이라 한다.

안장점이라는 명칭은 말안장(saddle)의 형상에서 유래하였다. 말안장의 중심점은 전후 방향으로는 극소이고 좌우 방향으로는 극대인 성질을 갖는다.

2. 이변수 함수에서의 안장점

이변수 함수 $f(x, y)$ 의 임계점 $(x^*, y^*)$ 에서의 헤시안 행렬은 다음과 같다.

$\mathbf{H}(x^*, y^*) = \begin{bmatrix} f_{xx} & f_{xy} \\ f_{xy} & f_{yy} \end{bmatrix}$

여기서 편미분은 모두 $(x^*, y^*)$ 에서 평가한 값이다. 이계도함수 판정법(second derivative test)에 의하면 다음이 성립한다.

행렬식 $D$ 를 다음과 같이 정의한다.

$D = f_{xx} f_{yy} - (f_{xy})^2 = \det(\mathbf{H})$

판정 기준은 다음과 같다.

조건	판정 결과
$D > 0$ 이고 $f_{xx} > 0$	극소점
$D > 0$ 이고 $f_{xx} < 0$	극대점
$D < 0$	안장점
$D = 0$	판정 불가

$D < 0$ 이면 헤시안의 고유값이 서로 다른 부호를 가지며, 이는 헤시안이 부정치(indefinite)임을 의미한다.

2.1 예제: 쌍곡 포물면

함수 $f(x, y) = x^2 - y^2$ 를 살펴보자. 그래디언트는 다음과 같다.

$\nabla f = \begin{bmatrix} 2x \\ -2y \end{bmatrix}$

임계점은 $(0, 0)$ 이다. 헤시안은 다음과 같다.

$\mathbf{H} = \begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix}$

행렬식 $D = 2 \cdot (-2) - 0^2 = -4 < 0$ 이므로 원점은 안장점이다. 고유값은 $\lambda_1 = 2 > 0$ , $\lambda_2 = -2 < 0$ 으로, $x$ -방향으로는 위로 볼록하고 $y$ -방향으로는 아래로 볼록하다.

3. 다변수 함수에서의 안장점 식별

$n$ 변수 함수 $f(\mathbf{x})$ 의 임계점 $\mathbf{x}^*$ 에서 안장점을 식별하려면 헤시안 행렬 $\mathbf{H}(\mathbf{x}^*)$ 의 정치성을 분석해야 한다.

3.1 고유값 분석에 의한 식별

헤시안의 고유값을 $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ 이라 하면 다음과 같이 판정한다.

$\lambda_1 > 0 \implies \text{극소점 (모든 고유값이 양수)}$

$\lambda_n < 0 \implies \text{극대점 (모든 고유값이 음수)}$

$\lambda_1 < 0 \;\text{이고}\; \lambda_n > 0 \implies \text{안장점}$

안장점에서는 음의 고유값에 대응하는 고유벡터 방향으로 함수값이 감소하고, 양의 고유값에 대응하는 고유벡터 방향으로 함수값이 증가한다.

3.2 안장점의 지수

안장점의 지수(index)는 헤시안의 음의 고유값의 개수로 정의한다. 임계점 $\mathbf{x}^*$ 에서의 안장점 지수를 $\text{ind}(\mathbf{x}^*)$ 라 하면 다음과 같다.

$\text{ind}(\mathbf{x}^*) = \#\{i : \lambda_i < 0\}$

지수가 0이면 극소점, 지수가 $n$ 이면 극대점, 지수가 $1$ 이상 $n-1$ 이하이면 안장점이다. 지수의 값은 안장점의 기하학적 구조를 특성화한다.

4. 테일러 전개를 통한 해석

임계점 $\mathbf{x}^*$ 근방에서 함수 $f$ 의 이차 테일러 전개는 다음과 같다.

$f(\mathbf{x}^* + \boldsymbol{\delta}) \approx f(\mathbf{x}^*) + \frac{1}{2} \boldsymbol{\delta}^\top \mathbf{H}(\mathbf{x}^*) \boldsymbol{\delta}$

여기서 $\nabla f(\mathbf{x}^*) = \mathbf{0}$ 이므로 일차항이 소거된다. 헤시안의 스펙트럼 분해 $\mathbf{H} = \sum_{i=1}^{n} \lambda_i \mathbf{v}_i \mathbf{v}_i^\top$ 를 대입하면 다음을 얻는다.

$f(\mathbf{x}^* + \boldsymbol{\delta}) - f(\mathbf{x}^*) \approx \frac{1}{2} \sum_{i=1}^{n} \lambda_i (\mathbf{v}_i^\top \boldsymbol{\delta})^2$

안장점에서는 양의 고유값과 음의 고유값이 공존하므로, 변위 $\boldsymbol{\delta}$ 의 방향에 따라 함수값이 증가하거나 감소한다.

5. 로봇공학에서의 안장점

5.1 역기구학의 안장점

로봇 매니퓰레이터의 역기구학(inverse kinematics) 문제를 최적화로 풀 때, 비용 함수는 다음과 같이 설정한다.

$f(\mathbf{q}) = \frac{1}{2} \lVert \mathbf{p}_d - \mathbf{p}(\mathbf{q}) \rVert^2$

여기서 $\mathbf{p}_d$ 는 목표 위치이고 $\mathbf{p}(\mathbf{q})$ 는 순기구학에 의한 말단장치의 위치이다. 특이 형상(singular configuration) 근방에서 이 비용 함수는 안장점을 가질 수 있으며, 이는 그래디언트 기반 최적화 알고리즘의 수렴 속도를 저하시키거나 수렴 실패를 유발한다.

5.2 경로 최적화에서의 안장점

로봇 경로 최적화에서 비용 범함수(cost functional)의 안장점은 최적 경로도 최악 경로도 아닌 정체점(stagnation point)에 해당한다. 경로 공간에서의 안장점을 탈출하기 위해 다음과 같은 기법이 사용된다.

안장점 자유 뉴턴법(saddle-free Newton method): 헤시안의 절댓값 행렬 $\lvert \mathbf{H} \rvert = \sum_i \lvert \lambda_i \rvert \mathbf{v}_i \mathbf{v}_i^\top$ 를 사용하여 갱신 방향을 수정한다.

$\boldsymbol{\delta} = -\lvert \mathbf{H} \rvert^{-1} \nabla f$

신뢰 영역법(trust region method): 헤시안에 양의 정칙화 항을 추가하여 부정치 문제를 양정치로 변환한다.

$(\mathbf{H} + \mu \mathbf{I}) \boldsymbol{\delta} = -\nabla f, \quad \mu > 0$

5.3 게임 이론적 안장점

로봇과 환경 간의 상호작용을 미니맥스(minimax) 문제로 모델링하면, 최적 해는 안장점이 된다. 비용 함수 $L(\mathbf{u}, \mathbf{w})$ 에 대해 다음 조건을 만족하는 점 $(\mathbf{u}^*, \mathbf{w}^*)$ 가 안장점이다.

$L(\mathbf{u}^*, \mathbf{w}) \leq L(\mathbf{u}^*, \mathbf{w}^*) \leq L(\mathbf{u}, \mathbf{w}^*), \quad \forall \mathbf{u}, \mathbf{w}$

이는 로버스트 제어(robust control)에서 $H_\infty$ 제어 설계의 수학적 기초가 된다.

6. 퇴화 임계점

헤시안 행렬이 특이(singular)한 임계점, 즉 $\det(\mathbf{H}(\mathbf{x}^*)) = 0$ 인 경우를 퇴화 임계점(degenerate critical point)이라 한다. 이 경우 이차 도함수 판정법으로는 극값의 종류를 결정할 수 없으며, 고차 도함수의 분석이 필요하다.

퇴화 임계점에서는 영 고유값에 대응하는 고유벡터 방향으로의 곡률이 0이므로, 그 방향의 삼차 이상의 도함수를 검사해야 한다.

$f(\mathbf{x}^* + t\mathbf{v}_0) = f(\mathbf{x}^*) + \frac{t^k}{k!} D_{\mathbf{v}_0}^k f(\mathbf{x}^*) + O(t^{k+1})$

여기서 $\mathbf{v}_0$ 은 영 고유값에 대응하는 고유벡터이고, $k$ 는 처음으로 0이 아닌 방향 도함수의 차수이다.

참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. 2nd Edition. Springer.
Milnor, J. (1963). Morse Theory. Princeton University Press.
Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
Dauphin, Y. N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., & Bengio, Y. (2014). Identifying and Attacking the Saddle Point Problem in High-Dimensional Non-Convex Optimization. Advances in Neural Information Processing Systems, 27.

v 0.1