10.1 최적화 문제의 구조

실습 · 연습문제 2개

stationary point 분류하기 classify-stationary-point

점 x\mathbf{x}에서의 gradient g=∇f(x)\mathbf{g} = \nabla f(\mathbf{x})와 Hessian H=∇2f(x)\mathbf{H} = \nabla^2 f(\mathbf{x})가 주어졌을 때, 최적성 조건으로 판정할 수 있는 만큼만 판정하는 함수 classify(g, H, tol=1e-8)를 완성한다. 반환값은 다음 다섯 문자열 중 하나다.

반환값 조건
"not-stationary" ∥g∥>\lVert \mathbf{g} \rVert > tol
"min" stationary이고 H\mathbf{H}의 모든 고윳값 >> tol (strict 국소 최소)
"max" stationary이고 모든 고윳값 << -tol (strict 국소 최대)
"saddle" stationary이고 tol보다 큰 고윳값과 -tol보다 작은 고윳값이 함께 있음
"inconclusive" 위 어느 것도 아님: 0에 가까운 고윳값이 있고 나머지 고윳값의 부호가 한쪽뿐

"inconclusive"가 핵심이다. 예를 들어 x3x^3, x4x^4, −x4-x^4는 모두 x=0x = 0에서 f′=0f' = 0, f′′=0f'' = 0이지만 각각 최솟값도 최댓값도 아닌 점, 최소, 최대다. 2계 조건만으로는 셋을 구별할 수 없으므로 판정을 보류해야 한다.

힌트: 대칭행렬의 고윳값은 np.linalg.eigvalsh로 구한다. 음·양 고윳값이 함께 있으면 0에 가까운 고윳값이 있어도 안장점이다. 음의 고윳값 방향으로는 내려가고 양의 고윳값 방향으로는 올라가기 때문이다.

중앙 차분 Hessian으로 볼록성 판별하기 numerical-hessian

두 번 미분 가능한 함수 f:Rn→Rf: \mathbb{R}^n \to \mathbb{R}의 Hessian ∇2f(x)\nabla^2 f(\mathbf{x})를 중앙 차분으로 근사하고, 여러 점에서 Hessian이 양의 준정부호(PSD)인지 확인한다. 두 함수를 완성한다.

  1. hessian_fd(f, x, h=1e-4): 점 x(shape (n,))에서의 Hessian 근사, shape (n, n). 성분은

    Hij≈f(x+hei+hej)−f(x+hei−hej)−f(x−hei+hej)+f(x−hei−hej)4h2H_{ij} \approx \frac{f(\mathbf{x} + h\mathbf{e}_i + h\mathbf{e}_j) - f(\mathbf{x} + h\mathbf{e}_i - h\mathbf{e}_j) - f(\mathbf{x} - h\mathbf{e}_i + h\mathbf{e}_j) + f(\mathbf{x} - h\mathbf{e}_i - h\mathbf{e}_j)}{4h^2}

    이다. 결과는 대칭행렬이어야 한다.

  2. is_convex_on(f, points, tol=1e-6): points(shape (M, n))의 모든 점에서 Hessian의 최소 고윳값이 -tol 이상이면 True, 한 점이라도 그보다 작으면 False.

테스트는 해석적 Hessian을 아는 함수로 hessian_fd를 확인하고, 볼록 함수와 볼록이 아닌 함수를 구별하는지 본다.

주의: is_convex_on이 True를 반환해도 볼록성이 증명된 것은 아니다. 확인한 점들 밖에서 Hessian이 음의 고윳값을 가질 수 있다. 반대로 False는 확실한 반례다.

힌트: 대칭행렬의 고윳값은 np.linalg.eigvalsh로 구한다.