볼록 최적화와 제약 — 제한 속의 최적해

볼록 최적화는 머신러닝에서 "풀 수 있는" 최적화의 핵심이에요.

왜 볼록성이 이토록 중요한지, 그림을 보면서 이해해 볼게요.

왼쪽 그래프를 보세요. 비볼록 함수에요.

울퉁불퉁한 곡선에 지역 극소값이 세 개나 있어요.

경사하강법을 돌리면, 시작점에 따라 다른 극소에 빠져요.

안장점까지 있어서 그래디언트가 0인데도 최솟값이 아닌 지점이 존재해요.

전역 최소를 찾으려면 결국 모든 곳을 탐색해야 하고, 이건 NP-hard예요.

이제 오른쪽 볼록 함수를 보세요. 매끈한 그릇 모양이에요.

극소값이 딱 하나! 어디서 시작하든 경사하강이 여기로 수렴해요.

수렴 속도도 보장돼요. 일반 볼록은 O(1/t), 강볼록은 기하급수적이에요.

하단 비교 상자를 보면, 비볼록은 NP-hard에 초기값 의존적이에요.

볼록은 다항 시간에 유일해, 초기값과 무관하게 최적해를 줘요.

역사적으로 1947년 단치히의 심플렉스법부터 시작됐어요.

1951년 쿤-터커 조건, 2004년 SVM과 라쏘에서 전성기를 맞이했죠.

딥러닝 손실은 비볼록이지만, 부분문제를 볼록으로 환원하는 게 핵심 전략이에요.

볼록 최적화를 알아야 비볼록 문제도 다룰 수 있어요.

다음 슬라이드에서 볼록 집합과 볼록 함수의 정의를 배워볼게요.

정의를 정확히 알아야 어떤 문제가 볼록인지 판별할 수 있어요.

지금 본 직관을 수식으로 형식화하는 과정이에요.

이 레슨이 끝나면 SVM, 라쏘 같은 문제가 왜 잘 풀리는지 이해하게 될 거예요.