09. 최적성 조건 — 멈춰야 할 점을 판별하기

// CORE 3/7 — first-order condition, second-order condition, positive definiteness

최적화 알고리즘은 반복적으로 움직입니다. 그렇다면 언제 멈춰야 할까요? 최적성 조건은 “이 점이 최소점일 수 있는가”를 판별하는 기준입니다.

First-order condition

제약이 없는 smooth problem을 생각합니다.

\min_x f(x).

점 $x^\ast$ 가 local minimum이면 gradient가 0이어야 합니다.

\nabla f(x^\ast)=0.

이 조건은 필요조건입니다. gradient가 0이 아니면 반대 방향으로 조금 움직여 값을 줄일 수 있기 때문입니다.

하지만 gradient가 0이라고 항상 최소점은 아닙니다. 최대점이나 saddle point도 gradient가 0일 수 있습니다.

2차 조건은 Hessian으로 점의 성격을 더 구분합니다.

점 $x^\ast$ 에서

\nabla f(x^\ast)=0

이고 Hessian이 positive semidefinite이면 local minimum 후보입니다.

p^\top \nabla^2 f(x^\ast)p\ge 0\quad\text{for all }p.

Hessian이 positive definite이면 더 강합니다.

p^\top \nabla^2 f(x^\ast)p>0\quad\text{for all }p\ne 0.

이때 $x^\ast$ 는 strict local minimum입니다.

positive definiteness는 모든 방향에서 2차 곡률이 양수라는 뜻입니다. 1차원에서 $f''(x)>0$ 이면 아래로 볼록한 모양인 것과 같은 생각입니다.

Hessian의 eigenvalue로 보면 다음과 같습니다.

볼록 함수라면 first-order condition이 훨씬 강해집니다.

\nabla f(x^\ast)=0

이면 $x^\ast$ 는 global minimum입니다. 제약이 있는 convex problem에서는 KKT 조건이 같은 역할을 합니다.

실제 코드는 정확히 0을 기다리지 않습니다. 대신 다음 조건을 씁니다.

\|\nabla f(x_k)\|\le \epsilon.

또는 함수값 변화, 변수 변화, 제약 위반량을 함께 봅니다.