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

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

 

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

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

 

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

 

 

 

 

[최적화] 6-1강. KKT 조건 기하학적으로 쉽게 이해하기! (Karush–Kuhn–Tucker conditions & Slater's condition)

이 영상은 혁펜하임 “탄탄한 컨벡스 최적화” 6-1강으로, KKT 조건(Karush–Kuhn–Tucker conditions)을 라그랑주 승수에서 부등식 제약까지 확장해, 기하학적으로 이해시키는 강의입니다.​ 

등식 제약만 있던 5장까지의 내용을 토대로, 이제 부등식 제약을 포함한 일반 제약 최적화에서 왜 KKT가 “필요조건(컨벡스에선 충분조건까지)”이 되는지 직관적으로 설명합니다.​ 

 

 

 

KKT 조건 구조 

일반 문제 

min ⁡ f ( x ) s.t. g i ( x ) ≤ 0 , h j ( x ) = 0 minf(x)s.t. g i (x)≤0,h j (x)=0 

에 대해, KKT 조건은 보통 다음 네 가지(혹은 다섯 가지)로 정리됩니다.​

 

- Stationarity: ∇ x L ( x \* , λ \* , μ \* ) = 0 ∇ x L(x \* ,λ \* ,μ \* )=0

- Primal feasibility: 제약 g i ( x \* ) ≤ 0 , h j ( x \* ) = 0 g i (x \* )≤0,h j (x \* )=0 만족

- Dual feasibility: 부등식 제약의 승수 λ i \* ≥ 0 λ i \* ≥0

- Complementary slackness: λ i \* g i ( x \* ) = 0 λ i \* g i (x \* )=0

 

강의에서는 등식 제약만 있던 라그랑주 조건 위에 “dual feasibility + complementary slackness”가 하나 더 붙는 구조라는 점을 강조하면서, 용어에 겁먹지 말라고 반복해 줍니다.​

 

 

Stationarity의 기하학적 의미

등식 제약만 있을 때와 마찬가지로, stationarity는 최적점에서 목적함수의 gradient가 제약들 gradient의 선형결합으로 표현된다는 것을 의미합니다.​

영상에서는 “gradient 화살표들”을 법선 벡터로 보고, 최적점에서 더 내려갈 수 있는 허용 방향(feasible direction)이 없어지려면 목적함수 gradient가 제약들의 법선 조합 위에 얹혀 있어야 한다는 그림을 통해 설명합니다.​

 

 

 

Complementary slackness 직관

Complementary slackness λ i g i ( x \* ) = 0 λ i g i (x \* )=0는

- 제약이 **활성(active)**이면 g i ( x \* ) = 0 g i (x \* )=0이고, 이때는 λ i λ i 가 0이 아닐 수 있음

- 제약이 **비활성(slack)**이면 g i ( x \* ) < 0 g i (x \* )<0, 이때는 λ i = 0 λ i =0이어야 함

  이라는 “어느 한쪽만 살아 있는” 관계를 말합니다.​

  강의에서는 “경계에 딱 붙어 있는 제약만 실제로 힘을 준다, 안쪽에 여유가 있는 제약은 승수가 0이라 최적성 조건에 기여하지 않는다”는 기하학적/물리적 비유로 이 조건을 설명합니다.​

 

 

 

정규성(regularity)와 Slater 조건

KKT가 “로컬 최적점의 필요조건”으로 성립하려면 정규성(regularity) 가정이 필요하다고 설명합니다.​

- LICQ(Linear Independence Constraint Qualification): 최적점에서 활성 부등식/등식 제약들의 gradient가 선형독립이어야 한다는 조건

- Slater’s condition: 컨벡스 문제에서, 모든 부등식 제약을 엄격히 만족시키는 점이 하나 존재하면(즉, g i ( x ) < 0 g i (x)<0인 interior feasible point), strong duality와 KKT의 충분조건성을 보장하는 중요한 정규성 조건​

 

영상에서는 슬레이터 조건을 “컨벡스 문제에서 제약이 너무 빡빡하지 않고, 안쪽에 넉넉한 feasible interior가 있는 상황”으로 직관화하고, 이때 KKT를 만족하는 ( x \* , λ \* , μ \* ) (x \* ,λ \* ,μ \* )만 찾으면 곧 최적해라는 점을 짚습니다.​

 

 

컨벡스 문제에서의 의미

마지막으로, 컨벡스 문제 + Slater 조건이 성립하면 KKT가 단순 필요조건이 아니라 필요충분조건이 되어, KKT를 만족하는 점은 곧 global optimum이라는 사실을 언급합니다.​

이로써 1–5장에서 배운 컨벡스·라그랑주·듀얼리티 내용이 “컨벡스 최적화 = KKT만 풀면 되는 세계”라는 큰 그림으로 묶이며, 이후 듀얼 문제·강한 쌍대성(strong duality) 강의로 자연스럽게 이어질 수 있게 준비해 줍니다.​

 

 

 

[최적화] 6-2강. Dual problem 으로 풀기 | 부등식 제약 조건 (Inequality constraints) 문제

이 강의는 혁펜하임 “탄탄한 컨벡스 최적화” 6-2강으로, 부등식 제약이 있는 문제를 ‘듀얼 문제(dual problem)’로 푸는 의미와 직관을 설명하는 영상입니다.​

KKT로 직접 푸는 방법과 대비하면서, 라그랑주 듀얼 함수, weak/strong duality, duality gap이 무엇인지 한 번에 연결해 줍니다.​

 

 

 

프라이멀 vs 듀얼 문제

먼저 원래 풀고 싶은 문제를 프라이멀(primal) 문제라고 부르고, 이 문제에서 정의한 라그랑지안 L ( x , λ , ν ) L(x,λ,ν)로부터 듀얼 함수와 듀얼 문제를 만드는 과정을 정리합니다.​

 

- 듀얼 함수 q ( λ , ν ) q(λ,ν)는 L L을 x x에 대해 최소화한 값으로 정의

- 듀얼 문제는 이 q ( λ , ν ) q(λ,ν)를 λ ≥ 0 λ≥0 제약 아래에서 최대화하는 문제

 

즉 “x를 줄이는 문제(프라이멀)”를 “ λ , ν λ,ν를 키우는 문제(듀얼)”로 바꿔 푸는 셈입니다.​

 

 

 

weak duality, strong duality, duality gap

강의의 핵심 재료는 다음 세 가지 관계입니다.​

 

- Weak duality: 모든 듀얼 feasible ( λ , ν ) (λ,ν)에 대해

  q ( λ , ν ) ≤ f \* q(λ,ν)≤f \*

  항상 성립 (여기서 f \* f \* 는 primal 최적값)

- Duality gap: f \* − q \* f \* −q \* (프라이멀 최적값과 듀얼 최적값의 차이)

- Strong duality: 어떤 문제에서는 f \* = q \* f \* =q \* 가 되어 duality gap이 0이 됨

 

영상에서는 듀얼 문제를 푸는 것이 “최적값의 **최선의 하한(lower bound)**를 찾는 일”이며, strong duality가 성립하는 컨벡스 문제에서는 이 하한이 곧 정답이 된다고 설명합니다.​

 

 

 

 

듀얼 함수가 항상 concave인 이유

듀얼 함수 q ( λ , ν ) q(λ,ν)는 라그랑지안 L ( x , λ , ν ) L(x,λ,ν)에 대해 x x를 최소화한 값인데, 이는 ( λ , ν ) (λ,ν)에 관한 아핀 함수들의 점별 infimum으로 표현됩니다.​

이 구조 때문에, 원래 프라이멀 문제가 비컨벡스여도 듀얼 함수는 항상 concave가 되며, 듀얼 문제는 “concave 함수 최대화”라는 잘 구조화된 문제로 바뀝니다.​

강의에서는 이 점을 이용해 “듀얼은 항상 concave → 로컬 최대점 = 글로벌 최대점”이라는 깔끔한 성질을 강조합니다.​

 

 

 

듀얼로 푸는 게 왜 유리한가

요약하면 듀얼 문제를 푸는 이유는 두 가지입니다.​

 

- (항상) 어려운 프라이멀 문제의 유의미한 하한(lower bound)를 얻기 위해

- (컨벡스 + Slater 조건 등 strong duality 조건에서) 듀얼만 풀어도 프라이멀 최적해를 복원하기 위해 영상의 예제에서는 간단한 부등식 제약 문제를 실제로 듀얼로 바꾸어 풀어 보면서, 듀얼 함수의 모양, 하한→정답으로 딱 붙는 지점, 그리고 그때의 λ \* λ \* 로부터 x \* x \* 를 다시 얻는 과정을 직접 보여 줍니다.​

 

이 강의까지 보면 “라그랑지안–KKT–듀얼–weak/strong duality”가 한 맥락으로 연결되어, 이후 프라이멀–듀얼 인테리어 포인트법 같은 알고리즘을 이해할 준비가 갖춰집니다.​​

 

 

 

[최적화] 6-3강. 엄청 자주 쓰이는 KKT 관련 핵심 명제 두 가지

이 영상은 혁펜하임 “탄탄한 컨벡스 최적화” 6-3강으로, 실전에서 KKT를 쓸 때 거의 항상 인용하게 되는 핵심 명제 두 가지를 정리해 주는 강의입니다.

6-1, 6-2강에서 배운 KKT·듀얼리티를 “이론–정리 수준”으로 한 번 더 정리해 주는 역할을 합니다.​

 

 

 

첫 번째 명제: 컨벡스 + Strong duality ⇒ KKT ⇔ 최적해

컨벡스 최적화 문제에서 Slater 조건 등 적당한 정규성(regularity, strong duality)을 만족하면, 다음이 성립하는 내용을 다룹니다.​

 

- 어떤 ( x \* , λ \* , ν \* ) (x \* ,λ \* ,ν \* )가 KKT 조건을 만족하면, x \* x \* 는 primal 최적해, ( λ \* , ν \* ) (λ \* ,ν \* )는 dual 최적해 - 반대로 primal·dual 최적해가 존재하면, 그 점에서 KKT 조건이 항상 성립

 

즉 이 경우 KKT는 단순 “필요조건”이 아니라 필요충분조건이 된다는 사실을 명제로 정리합니다.​

 

 

두 번째 명제: 비컨벡스에서도 KKT는 여전히 필요조건

두 번째 명제는 비컨벡스 문제에서도 KKT는 (정규성 가정 하에) 로컬 최적점의 필요조건이라는 내용입니다.​ 즉 문제 구조가 비컨벡스여서 KKT가 충분조건이 되지는 않더라도, 로컬 최소점이라면 여전히 어떤 라그랑주 승수와 함께 KKT를 만족해야 한다는 점을 강조합니다.​

 

 

 

자주 헷갈리는 잘못된 문장들 정리

영상 후반부에서는 인터넷 등에 떠도는 “KKT가 언제나 충분조건이다” 같은 잘못된 요약을 짚고, 상황별로 정확히 구분해 정리해 줍니다.​

 

- 일반 비컨벡스: KKT = 필요조건 (정규성 하에서)

- 선형/컨벡스 + strong duality: KKT = 필요충분조건, duality gap = 0

- strong duality가 깨진 컨벡스 또는 비정규 상황에서는, KKT가 최적해를 보장하지 않을 수 있음

 

이 두 명제를 알고 있으면, KKT를 쓸 때 “지금 이 문제에서 KKT를 쓰면 어디까지 말할 수 있나?”를 정확히 판단할 수 있게 됩니다.

 

 

 

[최적화] 6-4강. 내부점 방법 (Interior-point method, Barrier method) | 부등식 제약 조건 (Inequality constraints) 문제

이 강의는 혁펜하임 “탄탄한 컨벡스 최적화” 6-4강으로, 부등식 제약이 있는 문제를 내부점 방법(Interior-point, Barrier method)으로 푸는 전체 알고리즘을 KKT·로그 베리어 관점에서 묶어 주는 강의입니다.​ MATLAB fmincon 같은 실제 라이브러리 기본 알고리즘이 바로 이 계열이라는 점도 함께 언급합니다.​

 

 

기본 아이디어: KKT를 변형해 푸는 알고리즘

부등식·등식 제약을 가진 컨벡스 문제에서 KKT 조건에 등장하는 부등식 승수 μ i ≥ 0 μ i ≥0와 complementary slackness μ i g i ( x ) = 0 μ i g i (x)=0을 ** μ i g i ( x ) = 1 / t μ i g i (x)=1/t**와 같은 형태로 완화해 “버터드 KKT” 시스템을 만든 뒤, 그 방정식을 뉴턴법으로 푸는 게 핵심입니다.​

t → ∞ t→∞로 보내면 이 수정된 조건이 원래 KKT로 수렴하므로, t t를 점점 키우면서 연속적으로 해를 추적하면 최적해로 접근하는 경로(central path)를 따르게 됩니다.​

 

 

로그 베리어 함수와 Barrier method

이 수정은 라그랑지안에 **로그 베리어(log barrier)**를 추가한 문제

min ⁡ x f ( x ) − 1 t ∑ i log ⁡ ( − g i ( x ) ) s.t. A x = b x min f(x)− t 1 i ∑ log(−g i (x))s.t. Ax=b

를 푸는 것과 동치로 볼 수 있습니다.​

− log ⁡ ( − g i ( x ) ) −log(−g i (x))는 제약 경계 g i ( x ) = 0 g i (x)=0로 갈수록 값이 무한대로 치솟는 장벽을 만들기 때문에, 해가 항상 제약 내부에 머물도록 강제하면서 미분 가능성을 유지해 뉴턴법을 그대로 쓸 수 있게 합니다.​

 

 

알고리즘 구조: t 업데이트 + 뉴턴 이너 루프

Barrier IPM의 전형적인 흐름은 다음과 같습니다.​

- Phase II 초기

-- t 0 > 0 t 0 >0, strictly feasible x 0 x 0 선택

-- 반복:

    1. 고정된 t t에서 위의 “베리어가 포함된” 문제를 등식 제약 뉴턴법으로 충분히 푼다.

    2. t ← μ t t←μt (예: μ > 1 μ>1)로 키우고, 방금 얻은 해를 다음 뉴턴 이터레이션의 시작점으로 사용.

    3. duality gap ≈ m / t ≈m/t가 충분히 작아질 때까지 반복.

 

- Phase I

-- 처음 strictly feasible 포인트를 찾기 위해, slack 변수 s s를 도입한 보조 문제를 하나 더 풀어 feasibility를 확보하는 절차를 사용.​

 

영상에서는 이 과정을 2D 예제로 시각화하면서, **analytic center에서 시작해 경계 쪽 최적해까지 내부를 따라가는 경로(central path)**와 각 단계에서의 뉴턴 스텝을 애니메이션으로 보여 줍니다.​

 

 

Interior-point / Barrier라는 이름의 의미

“Interior-point”는 알고리즘이 항상 제약 집합의 **내부(strict interior)**에서만 움직이기 때문에 붙은 이름입니다.​

“Barrier method”는 제약을 위반하려고 하면 비용이 폭증하도록 만드는 장벽 함수를 이용해, 제약을 만족하는 영역 안에서만 최적화를 수행하는 접근이라는 뜻입니다.​

 

 

실전 연결: Primal-Dual IPM로 확장

마지막 부분에서는 이 barrier-only 방식이 개념적으로는 단순하지만, 높은 정확도나 효율 측면에서 primal-dual interior-point method에 비해 느릴 수 있다는 점을 언급하며, 다음 강의(6-5강)에서 primal-dual IPM을 다룰 것을 예고합니다.​​

Primal-dual IPM은 프라이멀 변수와 듀얼 변수, barrier 파라미터를 동시에 업데이트하며 수정된 KKT 시스템에 직접 뉴턴법을 적용하는 형태로 더 빠른 수렴 특성을 보입니다.​

 

 

 

[최적화] 6-5강. Primal-Dual Interior point method | 부등식 제약 조건 (Inequality constraints) 문제

이 강의는 혁펜하임 “탄탄한 컨벡스 최적화” 6-5강으로, 부등식 제약 문제를 푸는 Primal-Dual Interior-Point Method(IPM)를, KKT 방정식에 뉴턴법을 직접 적용하는 관점에서 설명하는 영상입니다.​ 

6-4강의 barrier(IPM)와 달리, 프라이멀 변수와 듀얼 변수(라그랑주 승수)를 한꺼번에 업데이트해서 더 빠르고 실용적인 알고리즘을 만드는 것이 핵심입니다.​ 

 

 

 

Barrier IPM vs Primal-Dual IPM 

Barrier method는 “ t t 고정 → 베리어 문제가 수렴할 때까지 여러 번 뉴턴 → t t 갱신” 식으로 바깥 루프(t), 안쪽 루프(Newton) 두 겹 구조를 가집니다.​

 Primal-Dual IPM은 KKT의 perturbed 시스템을 만들고, 이 전체를 한 번에 뉴턴 스텝으로 푸는 방식이라, 보통 **한 겹 루프(한 번 뉴턴 스텝만)**으로 같은 수준의 정확도에 더 빨리 도달합니다.​ 

 

 

 

Perturbed KKT와 뉴턴 시스템 

일반 부등식/등식 제약 문제에서 KKT는 

- stationarity, primal feasibility, dual feasibility, complementary slackness로 이루어집니다.​ 

 

Primal-Dual IPM에서는 complementary slackness μ i g i ( x ) = 0 μ i g i (x)=0를 

  μ i g i ( x ) = σ τ μ i g i (x)=στ

같은 형태로 완화한 perturbed KKT를 잡고, 이를 0으로 만드는 ( x , μ , λ ) (x,μ,λ)의 뿌리를 찾는 문제로 바꿉니다.​

잔차 벡터(dual 잔차, primal 잔차, centrality 잔차)를 정의한 뒤, 이 잔차 = 0 조건에 뉴턴법을 적용하면, ( Δ x , Δ μ , Δ λ ) (Δx,Δμ,Δλ)에 대한 큰 블록 선형 시스템(프라이멀-듀얼 뉴턴 시스템)을 얻게 됩니다.​

 

 

 

알고리즘 한 줄 요약

Primal-Dual IPM의 전형적인 루프는 다음 구조를 가집니다.​

1. 현재 ( x k , μ k , λ k ) (x k ,μ k ,λ k )에서 KKT 잔차를 계산

2. 그에 대한 프라이멀-듀얼 뉴턴 스텝 ( Δ x , Δ μ , Δ λ ) (Δx,Δμ,Δλ)을 선형 시스템 풀어서 구함

3. backtracking line search로 step size를 골라 양수성( μ > 0 μ>0, 제약 내부 유지)을 보장하면서 업데이트

4. 잔차와 surrogate duality gap이 충분히 작아질 때까지 반복

 

Barrier method는 “항상 feasible 중심에서 시작해서 t를 바꾸며 접근”하는 느낌이라면, Primal-Dual IPM은 feasible을 잠시 깨뜨려도 허용하고, 잔차 전체를 동시에 줄이는 방향으로 진입하는 것이 특징입니다.​

 

 

 

 

장점과 쓰임새

Primal-Dual IPM은 LP, QP, SOCP, SDP 같은 구조화된 컨벡스 문제에서 barrier method보다 이터레이션 수·실제 시간 모두 훨씬 효율적인 것으로 널리 알려져 있습니다.​

그래서 실전 최적화 패키지(예: 많은 선형/이차 계획 솔버)에서 기본 알고리즘으로 채택되는 경우가 많고, 이 강의는 그런 구현들을 이해하기 위한 수학적 뼈대를 제공해 줍니다.

 

 

 

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

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