실습 · 연습문제 2개

BFGS는 역Hessian의 근사 $\mathbf{H}_k$를 step마다 갱신한다. 파라미터 변화 $\mathbf{s} = \mathbf{x}_{k+1} - \mathbf{x}_k$와 gradient 변화 $\mathbf{y} = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)$로

$$\mathbf{H}_{k+1} = (\mathbf{I} - \rho\,\mathbf{s}\mathbf{y}^\top)\,\mathbf{H}_k\,(\mathbf{I} - \rho\,\mathbf{y}\mathbf{s}^\top) + \rho\,\mathbf{s}\mathbf{s}^\top, \qquad \rho = \frac{1}{\mathbf{y}^\top\mathbf{s}}$$

이다. 함수 bfgs_update(Hinv, s, y)를 완성해 새 근사 (n, n)을 반환한다. 입력 Hinv를 제자리에서 바꾸지 않는다.

테스트는 다음을 확인한다.

• secant 조건 $\mathbf{H}_{k+1}\mathbf{y} = \mathbf{s}$를 만족한다.
• $\mathbf{y}^\top\mathbf{s} > 0$이면 대칭·양의 정부호가 유지된다.
• 이차함수 $\frac{1}{2}\mathbf{x}^\top\mathbf{A}\mathbf{x} - \mathbf{b}^\top\mathbf{x}$에서 exact line search와 함께 $n$번 갱신하면 최솟점에 도달하고 $\mathbf{H}_n = \mathbf{A}^{-1}$이 된다.

힌트: np.outer(s, y)는 $\mathbf{s}\mathbf{y}^\top$이다.

비선형 최소제곱 $\min_\theta \frac{1}{2}\lVert \mathbf{r}(\theta) \rVert^2$에서 Levenberg–Marquardt(LM) 방법의 한 step $\boldsymbol{\delta}$는

$$(\mathbf{J}^\top\mathbf{J} + \lambda\mathbf{I})\,\boldsymbol{\delta} = -\mathbf{J}^\top\mathbf{r}$$

의 해다. $\mathbf{J}$는 잔차 $\mathbf{r}$의 Jacobian(shape (N, p)), $\lambda \ge 0$은 감쇠 계수다. 함수 lm_step(J, r, lam)을 완성해 shape (p,)의 step을 반환한다.

테스트는 다음을 확인한다.

• $\lambda = 0$이면 Gauss–Newton step이다. 잔차가 파라미터에 선형이면($\mathbf{r} = \mathbf{A}\theta - \mathbf{b}$) 한 step에 최소제곱해에 도달한다.
• $\lambda$가 아주 크면 step은 $-\mathbf{J}^\top\mathbf{r}/\lambda$, 즉 짧은 gradient descent step에 가깝다.
• $\lambda$를 키울수록 step이 짧아지고, 어떤 $\lambda > 0$에서도 선형 근사 $\mathbf{r} + \mathbf{J}\boldsymbol{\delta}$의 크기는 $\lVert \mathbf{r} \rVert$보다 작다.

힌트: $\mathbf{J}^\top\mathbf{J}$의 역행렬을 직접 만들지 말고 np.linalg.solve로 연립방정식을 푼다.