전역 최적해와 지역 최적해 (Global Optimum and Local Optimum)
쉽게 풀면
지역 최적해는 주변만 둘러봤을 때 가장 낮은(혹은 높은) 골짜기이고, 전역 최적해는 전체 지형을 통틀어 진짜로 가장 낮은(혹은 높은) 지점이다. 등산할 때 안개 속에서 내려가다 보면 작은 웅덩이(지역 최적해)에 갇혀서 그곳이 가장 낮은 곳이라고 착각할 수 있지만, 실제로는 저 너머에 훨씬 더 깊은 계곡(전역 최적해)이 있을 수 있다. 볼록함수처럼 특별한 경우가 아니면 지역 최적해가 전역 최적해라는 보장은 없다.
왜 중요한가
지역 최적해와 전역 최적해의 구분은 최적화 이론뿐 아니라 머신러닝, 운용과학, 제어공학 등 최적화 문제를 다루는 거의 모든 분야에서 알고리즘의 성능과 신뢰성을 평가하는 기본 틀이 됩니다. 딥러닝 모델 학습, 하이퍼파라미터 탐색, 신경망 구조 탐색처럼 목적함수가 복잡하고 볼록하지 않은 문제에서는 지역 최적해에 갇히는 것을 얼마나 잘 피하느냐가 알고리즘 설계의 핵심 관심사입니다. 실험 재현성 측면에서도 초기값이나 무작위성에 따라 결과가 달라질 수 있다는 점이 알고리즘 비교 연구에서 자주 언급됩니다.
논문에서는 이렇게 쓰입니다
볼록하지 않은 손실함수를 최적화할 때 알고리즘이 지역 최적해에 갇히는 문제는 실무에서 흔히 다뤄지는 과제다.
진화연산 연구에서 탐색 집단이 특정 해 주변에 몰려 지역 최적해에 갇히는 문제를 완화하기 위한 기법을 제안한 예입니다.
운용과학 연구에서 조합 최적화 문제에 확률적 탐색 기법을 적용해 지역 최적해를 회피한 사례입니다.
조금 더 깊게 보면
지역 최적해 문제를 다루는 대표적인 접근으로는 여러 초기값에서 반복 탐색하는 다중 시작(multi-start) 방법, 확률적으로 더 나쁜 해도 일정 확률로 받아들여 탐색 공간을 넓히는 시뮬레이티드 어닐링, 여러 후보 해 집단을 유지하며 탐색하는 유전 알고리즘 같은 메타휴리스틱 기법이 있습니다. 한편 목적함수가 볼록함수인 경우에는 지역 최적해가 곧 전역 최적해임이 수학적으로 보장되기 때문에, 볼록 최적화 문제로 재구성할 수 있는지 여부가 문제 난이도를 가늠하는 중요한 기준이 됩니다.
주의할 점
딥러닝처럼 매우 고차원인 문제에서는 안장점이 지역 최적해보다 더 흔한 장애물로 지적되기도 한다.