혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 5강

혁펜하임의 “탄탄한” 컨벡스 최적화는 머신러닝·딥러닝을 공부하는 사람들이 ‘최적화’를 진짜 수학적으로, 그러면서도 직관적으로 이해하도록 도와주는 한국어 강의 시리즈입니다.​​ 강의의 전체 구성, 수강 난이도, 어떤 수학/ML 배경이 연결되는지, 그리고 어떻게 활용하면 좋은지는 아래의 포스팅에 정리되어 있습니다.

 

[AI 인공지능 머신러닝 딥러닝] - 혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 강의 소개

혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 강의 소개

 

혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 강의

 

 

 

[최적화] 5-1강. 라그랑주 승수법 (Lagrangian multiplier) | 딱 화살표 두 개로 설명 끝! (라그랑주 승수 기하학적 설명)

이 강의는 혁펜하임 “탄탄한 컨벡스 최적화” 5-1강으로, 등식 제약이 있는 최적화 문제에서 라그랑주 승수법이 왜 나오고, 왜 ‘gradient가 평행’해지는지가 기하학적으로 이해되도록 설명하는 영상입니다.​ 

즉 ∇ f ( x \* ) = λ ∇ g ( x \* ) ∇f(x \* )=λ∇g(x \* )라는 조건을 식 외우기가 아니라 “화살표 두 개”의 그림으로 납득시키는 데 초점을 둡니다.​ 

 

 

제약 없는 경우 복습 

초반에는 제약이 없는 경우, 미분이 0인 지점이 극값 후보가 되는 이유를 다시 짚습니다.​ 

다변수 함수에서 ∇ f ( x ) = 0 ∇f(x)=0은 “어느 방향으로 조금 움직여도 1차 변화가 0인 지점”, 즉 더 이상 내려갈 수 있는 1차 방향이 없는 정지점이라는 해석을 상기시킵니다.​ 

 

 

 

등식 제약이 있을 때의 필요조건 

이제 제약 g ( x ) = 0 g(x)=0이 있는 문제에서, 최적점에서는 **모든 허용 가능한 방향(feasible direction)**으로의 1차 변화가 0이어야 한다는 조건을 설명합니다.​ 

여기서 “허용 가능한 방향”이란 제약 곡선/곡면을 따라 움직일 수 있는 접선 방향들이고, 그 모든 방향에서 f f의 방향미분이 0이 되어야 최적이라는 직관을 세팅합니다.​ 

 

 

 

왜 ∇ f ∇f와 ∇ g ∇g가 평행한가 

기하학적 핵심은 다음 한 문장으로 요약됩니다.​ 

- g ( x ) = 0 g(x)=0이 만드는 곡선/곡면에서 최적점이 발생할 때,

  그 점에서 f f의 gradient ∇ f ∇f는 제약의 gradient ∇ g ∇g와 평행해야 한다.

 

 

영상에서는 등고선 f ( x ) = const f(x)=const와 제약 곡선 g ( x ) = 0 g(x)=0이 “딱 접하는 지점”에서, 각자의 법선 벡터(gradient)가 같은 방향(또는 반대 방향)을 가리키게 됨을 그림으로 보여 주며, 바로 이 관계를 ∇ f = λ ∇ g ∇f=λ∇g로 쓰는 것이 라그랑주 승수 조건임을 설명합니다.​

 

 

 

라그랑주 함수와 해법 세 가지

이 기하학적 직관을 토대로, 라그랑주 함수

L ( x , λ ) = f ( x ) + λ g ( x ) L(x,λ)=f(x)+λg(x)

를 정의하고, 최적점 후보가 만족해야 할 조건

∇ x L ( x , λ ) = 0 , g ( x ) = 0 ∇ x L(x,λ)=0,g(x)=0

를 이용해 문제를 푸는 표준 절차를 소개합니다.​

 

 

영상에서는

- 직접 제약을 풀어 대입하는 방법

- ∇ f = λ ∇ g ∇f=λ∇g를 바로 쓰는 방법

- 라그랑주 함수를 세워 연립방정식을 푸는 방법

세 가지를 비교하면서, 일반화·확장에 유리한 것이 라그랑주 함수 방식이라는 점을 보여 줍니다.​

 

 

예시와 직관 정리

후반부 예제에서는 2차원 함수와 단일 등식 제약을 두고, 실제로 등고선과 제약곡선이 접하는 지점에서 gradient 두 화살표가 평행해지는 장면을 계산과 그림으로 확인합니다.​

이를 통해 “제약이 없으면 ∇ f = 0 ∇f=0, 제약이 있으면 ∇ f ∇f가 제약들의 gradient 선형결합에 놓인다”는 일반 원리를 자연스럽게 연결해 주고, 이후 KKT 조건·부등식 제약으로 확장될 발판을 마련합니다.​

 

 

 

 

[최적화] 5-2강. 등식 제약 조건 (Equality constraints) 문제 - 알고리즘으로 풀기

이 강의는 혁펜하임 “탄탄한 컨벡스 최적화” 5-2강으로, 등식 제약 조건이 있는 최적화 문제를 실제 알고리즘(뉴턴법)으로 어떻게 푸는지를 보여주는 영상입니다.​ 

5-1강에서 라그랑주 승수법을 기하학적으로 이해했다면, 5-2강은 그 조건들을 모아 **“뿅=0 형태의 방정식 → 뉴턴으로 푸는 절차”**로 구현하는 단계입니다.​ 

 

 

 

핵심 아이디어: KKT = “뿅=0” 시스템 

등식 제약이 있는 문제 

min ⁡ f ( x ) s.t. h ( x ) = 0 minf(x)s.t. h(x)=0 

에서 최적해는 KKT 조건, 즉 

∇ x L ( x , λ ) = 0 , h ( x ) = 0 ∇ x L(x,λ)=0,h(x)=0 

을 만족합니다.​ 

 

강의에서는 이 두 식을 하나의 벡터식 F ( x , λ ) = 0 F(x,λ)=0 꼴(영상에서 말하는 “뿅=0”)로 묶어 버리고, 이 F = 0 F=0을 푸는 문제를 뉴턴법으로 푼다는 관점으로 정리합니다.​ 

 

 

 

뉴턴 스텝: 자코비안과 블록 선형시스템 

벡터 방정식 F ( x , λ ) = 0 F(x,λ)=0에 뉴턴법을 적용하면, 각 스텝에서 다음 선형 시스템을 풀어야 합니다.​ 

J F ( x k , λ k ) [ Δ x Δ λ ] = − F ( x k , λ k ) J F (x k ,λ k )[ Δx Δλ ]=−F(x k ,λ k ) 여기서 J F J F 는 F F의 자코비안으로, 블록 행렬 형태 [ ∇ x x 2 L ∇ h ( x ) ⊤ ∇ h ( x ) 0 ] [ ∇ xx 2 L ∇h(x) ∇h(x) ⊤ 0 ] 

가 됩니다.​ 

강의에서는 이 블록 구조가 어떻게 나오는지, 각 블록이 의미하는 바(헤시안, 제약의 자코비안)를 벡터·행렬 미분 복습과 함께 차근차근 설명합니다.​ 

 

 

infeasible start 뉴턴법 직관 

전통적인 등식 제약 뉴턴법은 초기값이 제약을 이미 만족하는(feasible) 점이어야 한다는 제약이 있지만, 영상에서는 infeasible start Newton method를 써서 제약을 안 만족하는 점에서 시작해도 점점 제약을 만족하도록 수렴시키는 방식을 설명합니다.​ 

이때 뉴턴 스텝은 “목적함수 최적성 조건 잔차 + 제약 위반량 잔차”를 한꺼번에 줄이는 방향으로 정의되고, 라인 서치는 목적함수 값이 아니라 잔차의 노름 감소를 기준으로 수행한다는 점을 짚어 줍니다.​ 

 

 

알고리즘 요약 

강의에서 정리하는 알고리즘 흐름은 대략 다음과 같습니다.​ 

1. 초기 ( x 0 , λ 0 ) (x 0 ,λ 0 )를 정함 (제약 만족 여부와 무관)

2. 현재 F ( x k , λ k ) F(x k ,λ k )와 자코비안 J F J F 를 계산

3. 선형 시스템을 풀어 ( Δ x , Δ λ ) (Δx,Δλ)를 구함

4. 백트래킹 라인 서치 등으로 step size t t를 골라 ( x k + 1 , λ k + 1 ) = ( x k , λ k ) + t ( Δ x , Δ λ ) (x k+1 ,λ k+1 )=(x k ,λ k )+t(Δx,Δλ)

5. 잔차 ∥ F ∥ ∥F∥가 충분히 작아질 때까지 반복

 

이 과정을 통해 “라그랑주 승수 = 이론”이 아니라 실제 구현 가능한 뉴턴 기반 알고리즘으로 연결된다는 점을 보여 주는 것이 강의의 포인트입니다.​

 

 

[최적화] 5-3강. Backtracking line search 알고리즘 수렴 속도를 배로 키워준다고?!

이 강의는 혁펜하임 “탄탄한 컨벡스 최적화” 5-3강으로, 경사하강법·뉴턴법·quasi-Newton 등에서 step size(learning rate)를 똑똑하게 정하는 ‘Backtracking line search’ 알고리즘을 설명하는 영상입니다.​ 

고정된 α α를 쓰는 것보다 훨씬 안정적이고 빠르게 수렴하게 해 주는, 최적화 이론의 기본 도구 중 하나입니다.​ 

 

 

 

Line search 기본 아이디어 

먼저 line search 자체를 “방향 p k p k 는 이미 정해져 있고, 그 방향으로 얼마나 갈지를 정하는 문제”로 정리합니다.​ 

즉, x k + 1 = x k + t p k x k+1 =x k +tp k 에서, t > 0 t>0을 잘 골라 함수값 f ( x k + 1 ) f(x k+1 )가 충분히 줄어들게 만드는 과정을 line search라고 부르며, exact line search는 이 t t를 정확히 최소화하지만 계산 비용이 커서 현실적으로 잘 쓰지 않는다는 점을 짚습니다.​ 

 

 

 

 

Backtracking line search 절차

Backtracking line search는 초기 큰 step에서 시작해서, 조건을 만족할 때까지 줄여 나가는 방식입니다.​

 

일반적인 형태는 다음과 같습니다.​

1. descent 방향 p k p k 가 주어졌다고 가정 ( ∇ f ( x k ) ⊤ p k < 0 ∇f(x k ) ⊤ p k <0)

2. 초기 step t ← 1 t←1 (또는 다른 값)

3. Armijo(충분 감소) 조건

f ( x k + t p k ) ≤ f ( x k ) + α t ∇ f ( x k ) ⊤ p k f(x k +tp k )≤f(x k )+αt∇f(x k ) ⊤ p k

  을 만족하는지 검사 ( α ∈ ( 0 , 0.5 ) α∈(0,0.5))

4. 만족하지 않으면 t ← β t t←βt로 줄임 ( 0 < β < 1 0<β<1)

5. 만족하는 t t를 찾으면 그걸로 업데이트: x k + 1 = x k + t p k x k+1 =x k +tp k

 

강의에서는 이 과정을 “한 줄 요약” 수준의 직관으로도 설명해 주며, α , β α,β를 어떻게 고르는지, 실제 구현에서의 관례도 함께 보여 줍니다.​

 

 

 

왜 수렴 속도가 빨라지는가

Backtracking을 쓰면, 경사하강법이나 뉴턴법에서

- 너무 큰 step으로 발산하는 것을 막고

- 너무 작은 step만 쓰는 비효율도 피하면서

  각 스텝에서 “적당히 충분히 줄어드는” step을 자동으로 선택하게 됩니다.​

  이 때문에 고정 learning rate보다 더 안정적으로, 이론적으로도 좋은 수렴 보장을 가지며, 많은 최적화 교과서에서 표준적인 line search 방식으로 채택됩니다.​

 

 

다른 강의들과의 연결

이 강의에서 배운 Backtracking line search는 앞에서 공부한

- 경사하강법, 뉴턴법, quasi-Newton(BFGS/DFP),

- Infeasible start Newton (등식/부등식 제약)

  등 거의 모든 알고리즘의 “step size 모듈”로 공통 사용됩니다.​

  그래서 최적화 알고리즘을 실제 구현하거나 응용 논문을 읽을 때, Backtracking과 Armijo 조건을 이해하고 있으면 전체 구조를 훨씬 쉽게 따라갈 수 있습니다.​

 

 

 

 

[AI 인공지능 머신러닝 딥러닝] - 혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 6강

혁펜하임의 “탄탄한” 컨벡스 최적화 (Convex Optimization) 6강