114강의 KKT 조건을 다시 봅니다.
| 묶음 | 변수 | 조건 |
|---|---|---|
| 원시 | \mathbf | , |
| 쌍대 | \boldsymbol{\mu},\boldsymbol | 과 정류성 |
두 묶음이 대칭적으로 나뉩니다. 우연이 아닙니다.
라그랑주 함수를 세울 때 변수를 둘로 나눴습니다.
로 최소화하고 승수로 최대화하면 원래 문제가 됩니다. 그런데 순서를 바꿀 수도 있습니다.
뒤쪽이 쌍대 문제입니다. 이 강의는 두 가지를 밝힙니다.
| 질문 | 답 |
|---|---|
| 쌍대는 원시와 어떤 관계인가 | 언제나 하한입니다 |
| 언제 같아지는가 | 볼록이면 대개 같습니다 |
하한이라는 사실만으로도 값어치가 큽니다. 원시 문제를 못 풀어도 쌍대를 풀면 "적어도 이만큼은 된다"를 알 수 있습니다.
그리고 쌍대로 가면 구조가 드러납니다. SVM의 쌍대에서 데이터가 내적으로만 나타나고, 그것이 커널 기법의 문을 엽니다.
문제. subject to 을 봅니다.
(1) 라그랑주 함수를 세우고 에 대해 최소화하세요.
(2) 여러 에서 그 값을 구하세요.
(3) 원시 최적값과 비교하세요.
생각의 실마리. 제약을 으로 쓰고 라그랑주 함수를 세웁니다. 를 고정하면 의 이차함수라 최소를 손으로 구할 수 있습니다.
풀이. (1)
로 미분해 으로 두면 이라 이고
(2)와 (3) 원시 최적값은 에서 입니다. 검산에서
| p^ | q\le p^ | ||
|---|---|---|---|
| 예 | |||
| 예 | |||
| 예 | |||
| 예 | |||
| 예 |
언제나 이고 에서 등호입니다.
이 문제에서 배우는 것: 쌍대 함수와 약쌍대성.
쌍대 함수.
약쌍대성. 모든 과 에 대해
입니다.
증명이 두 줄입니다. 임의의 실행가능 에 대해 이고 이므로
따라서 이고, 실행가능한 전체에 대해 최소를 취하면 입니다.
114강 심화 2의 증명과 같은 논증이며, 그때는 KKT의 충분성을 보이는 데 썼습니다.
쌍대 문제를 정의합니다.
쌍대 문제. 이며 그 최적값을 라 합니다. 약쌍대성에서 입니다.
쌍대 문제는 언제나 볼록입니다. 가 아핀함수들의 하한이므로 오목이고, 오목함수의 최대화는 볼록 문제입니다. 원시가 비볼록이어도 쌍대는 볼록입니다.
바로 확인 1.
확인 1-1. 쌍대 함수의 정의를 쓰세요.
답. 라그랑주 함수를 에 대해 최소화한 것입니다.
확인 1-2. 약쌍대성을 쓰세요.
답. 가 언제나 성립합니다.
확인 1-3. 쌍대 문제는 볼록입니까?
답. 원시가 비볼록이어도 쌍대는 언제나 볼록입니다.
문제. subject to , 을 봅니다.
(1) 실행가능점을 모두 찾고 를 구하세요.
(2) 여러 에서 를 구하세요.
(3) 를 구하고 와 비교하세요.
생각의 실마리. 제약이 이라 실행가능집합이 이산입니다. 문제 1처럼 매끈하지 않습니다.
풀이. (1) 검산에서 실행가능점이 , , 이고
은 이라 실행불가입니다.
(2) 정수 조건은 그대로 두고 부등식만 완화합니다.
검산에서
(3) 검산에서 ()이고
이 문제에서 배우는 것: 쌍대 간극.
쌍대 간극. 을 쌍대 간극이라 합니다. 이면 강쌍대성이 성립한다고 합니다.
문제 1에서는 간극이 없었고 여기서는 입니다. 차이가 무엇인지 봅니다.
| 문제 | 실행가능집합 | 목적 | 간극 |
|---|---|---|---|
| 문제 1 | , 볼록 | 볼록 | |
| 문제 2 | , 이산 | 선형 |
에서 인 것이 사정을 말해 줍니다. 예산을 무시하면 을 골라 를 얻는데, 실제로는 예산 때문에 그럴 수 없습니다. 승수를 아무리 조절해도 이산 제약이 만드는 손실을 정확히 표현하지 못합니다.
선형계획 완화와 비교하면 이해가 깊어집니다. 로 완화하면
쌍대 최적값 와 같습니다. 우연이 아니며, 라그랑주 완화의 값이 선형계획 완화의 값과 같다는 정리가 있습니다.
이 간극이 정수계획법의 핵심 난점입니다. 하한 와 참값 사이를 좁히려면 분기와 절단이 필요하며, 그것이 분기한정법입니다.
볼록이면 대개 간극이 없습니다.
슬레이터 조건. 원시 문제가 볼록이고 어떤 실행가능점 가 있어 모든 비아핀 부등식에서 이면 강쌍대성이 성립합니다.
**"내부점이 존재한다"**는 뜻이며, 107강 심화 4의 분리 초평면 정리로 증명합니다.
바로 확인 2.
확인 2-1. 쌍대 간극의 정의를 쓰세요.
답. 이며 언제나 음이 아닙니다.
확인 2-2. 간극이 생기는 원인을 쓰세요.
답. 볼록성이 깨지는 것이며 이산 제약이 대표적입니다.
확인 2-3. 슬레이터 조건을 쓰세요.
답. 볼록이고 부등식 제약을 엄격히 만족하는 내부점이 있으면 강쌍대성이 성립합니다.
문제. subject to 를 봅니다(, , ).
(1) 쌍대 함수를 명시적으로 구하세요.
(2) 쌍대를 최대화하세요.
(3) 원시 최적값과 비교하세요.
생각의 실마리. 이차함수의 최소는 손으로 구해집니다. 를 소거해 만의 함수로 만듭니다.
풀이. (1) 를 로 미분하면
대입하면
변수가 개에서 개로 줄었습니다.
(2) 가 오목한 이차함수이므로 최대는 에서 달성됩니다. 검산에서
(3) 검산에서 이고 이라 **간극이 **입니다.
이 문제에서 배우는 것: 쌍대가 문제를 줄입니다.
이면 큰 이득입니다. 제약이 적고 변수가 많은 문제에서 쌍대가 훨씬 작습니다.
| 문제 | 원시 | 쌍대 |
|---|---|---|
| 변수 | ||
| 제약 | 만 |
이 나타난 것도 볼 만합니다. 이 행렬을 슈어 여집합이라 하며, 82강의 정규방정식과 같은 구조입니다.
113강 문제 5와 비교하면 같은 답을 다른 길로 얻은 것입니다. 그때는 KKT 행렬을 통째로 풀었고, 여기서는 를 먼저 소거했습니다.
| 방법 | 푸는 것 |
|---|---|
| KKT 직접 | 연립 |
| 쌍대 | 연립 |
둘째 줄이 대개 낫습니다. 특히 가 대각이거나 역행렬이 쉬우면 그렇습니다.
바로 확인 3.
확인 3-1. 이차계획 쌍대의 형태를 쓰세요.
답. 입니다.
확인 3-2. 쌍대의 변수 개수를 쓰세요.
답. 제약의 개수 입니다.
확인 3-3. 언제 쌍대가 유리합니까?
답. 제약이 변수보다 적을 때입니다.
문제. 를 봅니다.
(1) 을 수치로 구하세요.
(2) 을 구하세요.
(3) 최적점 근처에서 두 방향의 거동을 보세요.
생각의 실마리. 안쪽 최대화가 무엇을 하는지 봅니다. **이면 를 키워 **가 되고, 이면 이 최선입니다.
안쪽 최대화가 제약을 강제합니다.
풀이. (1)과 (2) 검산에서
| 순서 | 값 |
|---|---|
| (원시) | |
| (쌍대) |
**차가 **이라 강쌍대성입니다.
(3) 검산에서 근처를 보면
| 방향 ( 고정) | 방향 ( 고정) |
|---|---|
방향으로는 최소이고 방향으로는 평평합니다.
이 문제에서 배우는 것: 안장점과 최소최대 정리.
안장점. 가 안장점이라 함은
가 모든 와 에서 성립하는 것입니다.
정리. 안장점이 존재할 필요충분조건은 강쌍대성이 성립하고 두 최적해가 달성되는 것입니다.
방향으로 평평한 것이 상보성입니다. 왼쪽 부등식이
인데, 모든 에서 성립하려면 이고 이어야 합니다.
114강에서 따로 요구한 조건이 여기서 자동으로 나옵니다.
최소최대 부등식은 언제나 성립합니다.
**"먼저 움직이는 쪽이 불리하다"**는 뜻이며, 이것이 약쌍대성의 다른 표현입니다. 를 먼저 고르면 상대가 그것을 보고 를 고르므로 불리합니다.
게임이론의 언어로 읽으면 자연스럽습니다.
| 관점 | 해석 |
|---|---|
| 원시 | 가 먼저 움직입니다 |
| 쌍대 | 가 먼저 움직입니다 |
| 강쌍대성 | 순서가 무관합니다 |
| 안장점 | 내시 균형입니다 |
272강의 GAN이 이 구조입니다. 생성자와 판별자가 최소최대 게임을 하며, 순서 교환이 성립하는지가 학습 안정성과 직결됩니다.
바로 확인 4.
확인 4-1. 최소최대 부등식을 쓰세요.
답. 입니다.
확인 4-2. 안장점 조건에서 무엇이 나옵니까?
답. 상보성 조건이 자동으로 나옵니다.
확인 4-3. 안장점이 게임이론에서 무엇에 해당합니까?
답. 내시 균형입니다.
문제. 세 점으로 된 SVM을 봅니다. , ; , ; , .
(1) 그람 행렬 을 구하세요.
(2) 쌍대해 와 를 구하세요.
(3) 각 점의 여백과 를 비교하세요.
생각의 실마리. 114강 심화 4에서 예고했습니다. 상보성이 대부분의 를 으로 만듭니다.
풀이. (1) 검산에서
(2) 쌍대 문제는
검산에서 이고
(3) 검산에서
| 점 | 역할 | ||
|---|---|---|---|
| 지지 벡터 | |||
| 지지 벡터 | |||
| 무관 |
**여백이 정확히 인 점만 **입니다.
이 문제에서 배우는 것: 쌍대가 구조를 드러냅니다.
첫째, 희소성이 상보성에서 나옵니다.
**여백이 보다 크면 괄호가 양수이므로 **입니다. 검산에서 이 여백 이라 이고, 에 전혀 기여하지 않습니다.
설계로 넣은 성질이 아니라 최적성 조건에서 저절로 나옵니다.
둘째, 데이터가 내적으로만 나타납니다. 쌍대 목적함수에 가 직접 등장하지 않고 로만 들어갑니다.
이것이 커널 기법의 문입니다. 내적을 다른 함수로 바꾸면 명시적으로 고차원으로 옮기지 않고도 비선형 분류가 됩니다.
| 커널 | 형태 |
|---|---|
| 선형 | \mathbf{x}\cdot\mathbf |
| 다항 | (\mathbf{x}\cdot\mathbf{z}+c)^ |
| 가우스 |
셋째 줄은 무한차원 특징공간에 대응하는데, 쌍대에서는 유한한 행렬만 다루면 됩니다. 214강에서 정면으로 봅니다.
셋째, 값이 맞습니다. 검산에서 쌍대 목적값이 이고 로 같습니다. 강쌍대성이 성립합니다.
바로 확인 5.
확인 5-1. SVM에서 인 점의 여백을 쓰세요.
답. 보다 큽니다.
확인 5-2. 희소성이 어디서 나옵니까?
답. 상보성 조건에서 나옵니다.
확인 5-3. 쌍대에서 데이터가 어떻게 나타납니까?
답. 내적으로만 나타나며 이것이 커널 기법의 근거입니다.
| 개념 | 내용 |
|---|---|
| 라그랑주 함수 | \mathcal{L}=f+\sum\mu_{i}h_{i}+\sum\lambda_{j}g_ |
| 쌍대 함수 | q=\inf_{\mathbf{x}}\mathcal |
| 쌍대 문제 | |
| 약쌍대성 | , 언제나 성립 |
| 강쌍대성 | , 볼록 + 슬레이터 |
| 쌍대 간극 |
| 성질 | 내용 |
|---|---|
| 쌍대는 언제나 볼록 | 가 아핀의 하한이라 오목 |
| 변수 수 | 원시 , 쌍대 |
| 최소최대 | |
| 안장점 | 강쌍대성 + 달성 |
| 상보성 | 안장점 조건에서 나옴 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 간극이 없다고 가정합니다 | 볼록성을 확인합니다 |
| 을 빠뜨립니다 | 약쌍대성의 근거입니다 |
| 쌍대가 비볼록일 수 있다고 봅니다 | 언제나 볼록입니다 |
| 순서 교환을 당연시합니다 | 강쌍대성이 필요합니다 |
문제 6. 쌍대 함수의 정의를 쓰세요.
답. 입니다.
문제 7. 약쌍대성을 쓰고 증명의 핵심을 쓰세요.
답. 이며 과 에서 이기 때문입니다.
문제 8. 쌍대 문제가 언제나 볼록인 이유를 쓰세요.
답. 가 아핀함수들의 하한이라 오목이기 때문입니다.
문제 9. s.t. 의 쌍대 함수를 구하세요.
답. 입니다.
문제 10. 문제 9의 와 를 구하세요.
답. 이고 입니다.
문제 11. 쌍대 간극의 정의를 쓰세요.
답. 이며 음이 아닙니다.
문제 12. 간극이 생기는 대표적 원인을 쓰세요.
답. 이산 제약처럼 볼록성이 깨지는 경우입니다.
문제 13. 슬레이터 조건을 쓰세요.
답. 볼록이고 부등식을 엄격히 만족하는 실행가능점이 있으면 강쌍대성이 성립합니다.
문제 14. 이차계획 s.t. 의 쌍대를 쓰세요.
답. 입니다.
문제 15. 최소최대 부등식을 쓰세요.
답. 입니다.
문제 16. 안장점 조건에서 자동으로 따라오는 KKT 조건을 쓰세요.
답. 상보성입니다.
문제 17. SVM 쌍대에서 인 점을 무엇이라 합니까?
답. 지지 벡터이며 여백이 정확히 입니다.
문제 18. 커널 기법이 가능한 이유를 쓰세요.
답. 쌍대에서 데이터가 내적으로만 나타나기 때문입니다.
심화 1. 강쌍대성을 분리 초평면으로 증명하는 발상을 설명하세요.
증명의 뼈대를 봅니다. 원시 문제의 값 집합을 정의합니다.
는 제약 위반의 여유이고 는 목적값입니다. 는 일 때의 최소 입니다.
가 볼록임을 보입니다. 와 가 볼록이면 두 점의 볼록결합이 다시 에 있습니다. 107강 문제 2의 정의를 그대로 쓰면 됩니다.
이제 점 가 의 경계에 있습니다. 그보다 작은 로는 을 만족할 수 없기 때문입니다.
107강 심화 4의 지지 초평면 정리를 적용합니다. 그 경계점에서 를 한쪽에 두는 초평면이 있어
**과 **임을 보일 수 있습니다. 가 와 방향으로 위쪽이 열려 있기 때문입니다.
슬레이터 조건이 을 보장합니다. 내부점이 있으면 초평면이 수직일 수 없습니다. 그러면 로 나눠
이고 의 정의에서 임의의 에 대해 이므로
**왼쪽이 **이므로 에 대해 최소를 취하면
약쌍대성과 합치면 등호입니다.
슬레이터 조건이 쓰인 자리가 정확히 하나입니다. 을 보장해 나눌 수 있게 하는 것이며, 내부점이 없으면 수직 초평면이 생겨 증명이 무너집니다.
문제 2의 이산 예에서는 가 볼록하지 않습니다. 실행가능집합이 네 점뿐이라 값 집합이 뭉쳐 있고, 지지 초평면이 에 닿지 못해 간극이 생깁니다.
심화 2. 선형계획법의 쌍대를 유도하세요.
114강 심화 3에서 KKT로 봤습니다. 쌍대 함수로 다시 유도합니다.
라그랑주 함수를 세웁니다.
에 대해 선형이므로 계수가 이 아니면 하한이 입니다.
를 피하는 조건이 쌍대 제약이 됩니다. 을 소거하면
대칭이 아름답습니다.
| 항목 | 원시 | 쌍대 |
|---|---|---|
| 방향 | 최소화 | 최대화 |
| 변수 | ||
| 제약 | A\mathbf{x}\ge\mathbf | A^{\top}\mathbf{y}\le\mathbf |
| 목적 | \mathbf{c}^{\top}\mathbf | \mathbf{b}^{\top}\mathbf |
| 크기 | 변수 제약 | 변수 제약 |
쌍대의 쌍대가 원시입니다. 위 표에서 원시와 쌍대를 바꿔도 같은 구조입니다.
선형계획법은 강쌍대성이 언제나 성립합니다. 실행가능해가 존재하면 예외가 없으며, 슬레이터 조건이 필요 없습니다. 제약이 모두 아핀이기 때문입니다.
경제학적 해석이 유명합니다. 원시가 "자원으로 이익을 최대화"라면 쌍대는 "자원의 가격을 매겨 비용을 최소화"이며, 113강 문제 4의 잠재가격이 쌍대변수입니다.
심화 3. 쌍대 문제를 실제로 푸는 방법을 논하세요.
언제 쌍대로 가는지부터 정리합니다.
| 상황 | 쌍대가 유리 |
|---|---|
| 제약이 변수보다 적습니다 | 문제가 작아집니다 |
| 원시 제약이 복잡합니다 | 쌍대는 뿐 |
| 구조가 드러납니다 | SVM의 커널 |
| 하한이 필요합니다 | 분기한정법 |
넷째 줄이 정수계획법의 표준 기법입니다. 문제 2에서 가 의 하한이었는데, 이런 하한으로 탐색 가지를 쳐 냅니다.
쌍대 문제를 푸는 방법은 여럿입니다.
첫째, 명시적으로 풀립니다. 문제 3처럼 가 손으로 구해지면 쌍대가 명시적 최적화 문제가 됩니다.
둘째, 열등경사법을 씁니다. 가 여러 최소의 하한이라 미분불가능할 수 있습니다. 107강 심화 4의 열등경사가 필요하며
에서의 최소해 의 제약 위반이 열등경사입니다. 직관적입니다. 제약을 어기면 그 승수를 키웁니다.
셋째, 원시와 쌍대를 함께 갱신합니다.
원시는 내려가고 쌍대는 올라갑니다. 안장점을 찾는 자연스러운 방법이며 원시-쌍대 방법이라 부릅니다.
가 을 강제하며, 114강 문제 5에서 본 사영입니다.
GAN의 학습이 같은 구조입니다. 생성자가 최소화하고 판별자가 최대화하며 번갈아 갱신합니다. 안장점을 찾는 일이라 수렴이 까다롭고, 272강에서 그 어려움을 다룹니다.
심화 4. 켤레함수와 쌍대의 관계를 소개하세요.
쌍대 함수를 계산할 때 반복되는 형태가 있습니다.
이 양에 이름이 있습니다.
켤레함수(르장드르-펜첼 변환).
는 언제나 볼록입니다. 아핀함수들의 상한이기 때문이며, 쌍대가 언제나 볼록인 것과 같은 이유입니다.
기하적 뜻이 있습니다. 를 기울기로 하는 직선을 아래로 밀어 넣었을 때의 절편이 입니다.
예를 봅니다.
| f^ | |
|---|---|
| \tfrac12\lVert\mathbf{x}\rVert^ | \tfrac12\lVert\mathbf{y}\rVert^ |
| \tfrac12\mathbf{x}^{\top}Q\mathbf | \tfrac12\mathbf{y}^{\top}Q^{-1}\mathbf |
| e^ | |
| if , else |
둘째 줄이 문제 3에 나타났습니다. 쌍대 함수에 이 등장한 것이 켤레함수 때문입니다.
넷째 줄이 90강과 이어집니다. 노름의 켤레가 쌍대 노름의 지시함수이며, 그때 다룬 과 의 쌍대 관계가 여기서 다시 나옵니다.
볼록이고 닫힌 함수는 이중 켤레가 자기 자신입니다.
이것이 강쌍대성의 다른 표현입니다. 함수를 접선의 모임으로 봤다가 되돌렸을 때 잃는 것이 없다는 뜻이며, 비볼록이면 가 의 볼록 포락이 되어 간극이 생깁니다.
203강의 KL 발산과 262강의 변분추론에서 켤레함수가 다시 나옵니다. 로그분배함수와 엔트로피가 서로 켤레이며, 그 관계가 지수족의 이론을 떠받칩니다.
심화 5. 쌍대성이 나타나는 다른 자리들을 정리하세요.
최적화 밖에서도 같은 구조가 반복됩니다.
첫째, 선형대수의 쌍대공간입니다. 74강에서 행공간과 열공간을 다뤘고, 가 113강 심화 1의 증명이었습니다.
둘째, 노름의 쌍대입니다. 90강에서
를 다뤘고, 과 가 짝이며 는 자기 자신입니다.
셋째, 확률과 정보입니다. 203강의 KL 발산이 켤레 쌍을 이루며, 변분 표현
이 쌍대 형식입니다. GAN의 -발산 관점이 여기서 나오며 272강에서 씁니다.
넷째, 게임이론입니다. 문제 4에서 본 최소최대가 영합게임의 값이며, 폰 노이만의 최소최대 정리가 강쌍대성의 특수한 경우입니다.
다섯째, 물리의 르장드르 변환입니다. 라그랑지언과 해밀토니언이 켤레 쌍이고, 위치와 운동량이 짝을 이룹니다.
| 분야 | 원시 | 쌍대 |
|---|---|---|
| 최적화 | 변수 | 승수 |
| 선형대수 | 열공간 | 행공간 |
| 노름 | \ell^ | \ell^ |
| 정보 | 분포 | 로그분배함수 |
| 게임 | 최소화자 | 최대화자 |
| 물리 | 속도 | 운동량 |
여섯 줄이 같은 수학입니다. 볼록함수를 접선으로 바꿔 보는 하나의 변환이며, 분야마다 다른 이름을 얻었습니다.
심화 6. 116강으로 어떻게 이어지는지 정리하세요.
05단원의 마지막 강의는 이 단원을 기계학습으로 잇습니다.
정규화된 손실을 봅니다.
가 왜 하필 승수의 기호인지가 116강의 질문입니다. 답은 이것이 제약 문제와 같기 때문입니다.
두 문제가 같은 해를 줍니다. 라그랑주 함수를 세우면 첫 형태가 그대로 나오고, 113강 문제 4의 해석으로 가 **"복잡도 예산의 가격"**입니다.
| 뜻 | ||
|---|---|---|
| 크다 | 작다 | 강한 정규화 |
| 작다 | 크다 | 약한 정규화 |
| 정규화 없음 |
116강이 답할 것을 정리합니다.
첫째, 이 왜 희소해를 주는가입니다. 90강 문제 1에서 단위구가 마름모이고 꼭짓점이 축 위에 있다고 했습니다. 등고선이 그 꼭짓점에 닿기 쉬우므로 **해의 성분이 정확히 **이 됩니다.
둘째, KKT가 그것을 어떻게 말하는가입니다. 은 원점에서 미분불가능하므로 열등경사를 써야 하고, 그 조건에서 연성 문턱이 나옵니다.
작은 계수가 정확히 으로 잘립니다.
셋째, 능형과 라소의 차이입니다. 두 정규화의 기하가 다르고, 그 차이가 해의 성질을 가릅니다.
05단원이 116강으로 닫히고 06단원에서 미분방정식으로 넘어갑니다. 그곳에서 최적화를 시간에 따라 흐르는 연속 과정으로 다시 보며, 119강의 경사흐름이 109강의 경사하강법을 미분방정식으로 옮긴 것입니다.
import numpy as np
import itertools
# --- 문제 1: 쌍대 함수는 하한을 준다 ------------------------------------
print(" min x^2 s.t. x >= 1. L(x,mu) = x^2 + mu(1-x)")
print(" q(mu) = inf_x L = mu - mu^2/4")
print(" mu q(mu) 원시 최적값 p* q <= p* ?")
for mu in [0.0, 1.0, 2.0, 3.0, 4.0]:
q = mu - mu**2/4
print(" %7.2f %9.4f %12.1f %s" % (mu, q, 1.0, "예" if q <= 1.0 + 1e-12 else "아니오"))
print(" q 를 최대화하면 mu* = 2, q(2) = %.1f = p* 이라 간극이 없습니다" % (2 - 1.0))
# min x^2 s.t. x >= 1. L(x,mu) = x^2 + mu(1-x)
# q(mu) = inf_x L = mu - mu^2/4
# mu q(mu) 원시 최적값 p* q <= p* ?
# 0.00 0.0000 1.0 예
# 1.00 0.7500 1.0 예
# 2.00 1.0000 1.0 예
# 3.00 0.7500 1.0 예
# 4.00 0.0000 1.0 예
# q 를 최대화하면 mu* = 2, q(2) = 1.0 = p* 이라 간극이 없습니다
# --- 문제 2: 간극이 생기는 예 -------------------------------------------
print(" 이산 제약이 있으면 간극이 생깁니다")
print(" min -(3x1+2x2) s.t. 2x1+2x2 <= 3, x in {0,1}^2")
c = np.array([-3.0, -2.0]); a = np.array([2.0, 2.0]); b = 3.0
pts = list(itertools.product([0, 1], [0, 1]))
feas = [p for p in pts if a @ np.array(p) <= b]
p_star = min(c @ np.array(p) for p in feas)
print(" 실행가능점 %s, p* = %.1f" % (feas, p_star))
print(" mu q(mu) = min over {0,1}^2 of c.x + mu(a.x - b)")
best = -np.inf; bm = None
for mu in [0.0, 0.5, 1.0, 1.5, 2.0]:
q = min(c @ np.array(p) + mu*(a @ np.array(p) - b) for p in pts)
print(" %7.2f %14.4f" % (mu, q))
for mu in np.linspace(0, 3, 3001):
q = min(c @ np.array(p) + mu*(a @ np.array(p) - b) for p in pts)
if q > best: best, bm = q, mu
print(" d* = %.4f (mu* = %.3f), p* = %.1f, 쌍대 간극 = %.4f" % (best, bm, p_star, p_star - best))
# 이산 제약이 있으면 간극이 생깁니다
# min -(3x1+2x2) s.t. 2x1+2x2 <= 3, x in {0,1}^2
# 실행가능점 [(0, 0), (0, 1), (1, 0)], p* = -3.0
# mu q(mu) = min over {0,1}^2 of c.x + mu(a.x - b)
# 0.00 -5.0000
# 0.50 -4.5000
# 1.00 -4.0000
# 1.50 -4.5000
# 2.00 -6.0000
# d* = -4.0000 (mu* = 1.000), p* = -3.0, 쌍대 간극 = 1.0000
# 승수를 아무리 조절해도 이산 제약이 만드는 손실을 표현하지 못합니다.
# --- 문제 3: 이차계획법의 쌍대 ------------------------------------------
print(" min (1/2)x^T Q x s.t. A x = b 의 쌍대")
Q = np.array([[2.0, 0.0], [0.0, 4.0]]); A = np.array([[1.0, 1.0]]); b2 = np.array([2.0])
Qi = np.linalg.inv(Q)
S = A @ Qi @ A.T
lam = np.linalg.solve(S, b2)
x = Qi @ A.T @ lam
print(" Q = diag(2,4), A = [1,1], b = 2")
print(" lam* = %s, x* = %s" % (np.round(lam, 6), np.round(x, 6)))
print(" 원시 최적값 p* = %.8f" % (0.5*(x @ Q @ x)))
print(" 쌍대 q(lam) = -(1/2) lam^T (A Qi A^T) lam + b^T lam")
for l in [0.0, 1.0, 2.0, lam[0], 3.0]:
print(" lam=%7.4f q=%12.8f" % (l, -0.5*l*S[0,0]*l + b2[0]*l))
d3 = -0.5*lam[0]*S[0,0]*lam[0] + b2[0]*lam[0]
print(" d* = %.8f, 간극 %.3e" % (d3, abs(0.5*(x @ Q @ x) - d3)))
# min (1/2)x^T Q x s.t. A x = b 의 쌍대
# Q = diag(2,4), A = [1,1], b = 2
# lam* = [2.666667], x* = [1.333333 0.666667]
# 원시 최적값 p* = 2.66666667
# 쌍대 q(lam) = -(1/2) lam^T (A Qi A^T) lam + b^T lam
# lam= 0.0000 q= 0.00000000
# lam= 1.0000 q= 1.62500000
# lam= 2.0000 q= 2.50000000
# lam= 2.6667 q= 2.66666667
# lam= 3.0000 q= 2.62500000
# d* = 2.66666667, 간극 0.000e+00
# 변수가 2 개에서 1 개로 줄었습니다.
# --- 문제 4: 안장점과 최소최대 교환 -------------------------------------
print(" L(x,mu) = x^2 + mu(1-x) 에서 순서를 바꿔 봅니다")
xg = np.linspace(-1.0, 3.0, 4001); mg = np.linspace(0.0, 6.0, 6001)
X, M = np.meshgrid(xg, mg, indexing='ij')
L = X**2 + M*(1 - X)
print(" min_x max_mu L = %.6f (원시)" % L.max(axis=1).min())
print(" max_mu min_x L = %.6f (쌍대)" % L.min(axis=0).max())
print(" 차 = %.3e 이라 강쌍대성입니다" % abs(L.max(axis=1).min() - L.min(axis=0).max()))
print(" 안장점 (x*, mu*) = (1, 2) 근처를 봅니다")
print(" x 를 흔들면 (mu=2 고정) mu 를 흔들면 (x=1 고정)")
for d in [-0.2, 0.0, 0.2]:
xv = 1 + d; mv = 2 + 5*d
print(" x=%.1f -> L=%.4f mu=%.1f -> L=%.4f"
% (xv, xv**2 + 2*(1-xv), mv, 1.0 + mv*(1-1.0)))
print(" mu 방향으로 평평합니다. h(x*) = 0 이기 때문이며 이것이 상보성입니다")
# L(x,mu) = x^2 + mu(1-x) 에서 순서를 바꿔 봅니다
# min_x max_mu L = 1.000000 (원시)
# max_mu min_x L = 1.000000 (쌍대)
# 차 = 0.000e+00 이라 강쌍대성입니다
# 안장점 (x*, mu*) = (1, 2) 근처를 봅니다
# x 를 흔들면 (mu=2 고정) mu 를 흔들면 (x=1 고정)
# x=0.8 -> L=1.0400 mu=1.0 -> L=1.0000
# x=1.0 -> L=1.0000 mu=2.0 -> L=1.0000
# x=1.2 -> L=1.0400 mu=3.0 -> L=1.0000
# mu 방향으로 평평합니다. h(x*) = 0 이기 때문이며 이것이 상보성입니다
# --- 문제 5: SVM 쌍대에서 지지 벡터만 남는다 ----------------------------
print(" SVM 쌍대: 자료 세 개로 정확히 풀어 봅니다")
Xd = np.array([[1.0, 1.0], [-1.0, -1.0], [3.0, 3.0]])
y = np.array([1.0, -1.0, 1.0])
K = Xd @ Xd.T
print(" 그람 행렬 K = X X^T =\n", K)
al = np.array([0.25, 0.25, 0.0]) # 손으로 푼 해
w = (al*y) @ Xd
print(" alpha* = %s -> w = sum a_i y_i x_i = %s" % (al, w))
print(" 점 y(w.x) alpha 역할")
for i in range(3):
m = y[i]*(Xd[i] @ w)
print(" %-10s %8.4f %8.4f %s"
% (np.array2string(Xd[i]), m, al[i], "지지 벡터" if al[i] > 1e-9 else "무관"))
print(" sum a_i y_i = %.1f (제약 만족), ||w||^2 = %.4f" % (al @ y, w @ w))
print(" 쌍대 목적 sum(a) - (1/2) a^T (yy^T o K) a = %.4f = (1/2)||w||^2 = %.4f"
% (al.sum() - 0.5*(al @ (np.outer(y,y)*K) @ al), 0.5*(w @ w)))
# SVM 쌍대: 자료 세 개로 정확히 풀어 봅니다
# 그람 행렬 K = X X^T =
# [[ 2. -2. 6.]
# [-2. 2. -6.]
# [ 6. -6. 18.]]
# alpha* = [0.25 0.25 0. ] -> w = sum a_i y_i x_i = [0.5 0.5]
# 점 y(w.x) alpha 역할
# [1. 1.] 1.0000 0.2500 지지 벡터
# [-1. -1.] 1.0000 0.2500 지지 벡터
# [3. 3.] 3.0000 0.0000 무관
# sum a_i y_i = 0.0 (제약 만족), ||w||^2 = 0.5000
# 쌍대 목적 sum(a) - (1/2) a^T (yy^T o K) a = 0.2500 = (1/2)||w||^2 = 0.2500
# 여백이 1 보다 큰 점은 alpha 가 0 이라 w 에 기여하지 않습니다.
문제 2의 간극 이 이 강의의 요지입니다. 쌍대는 언제나 하한이지만, 볼록성이 깨지면 그 하한이 참값에 닿지 못합니다.
116강에서 정규화가 제약임을 봅니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 쌍대 함수 | 입니다 | |
| p^ | 원시 최적값 | 원래 문제의 답입니다 |
| d^ | 쌍대 최적값 | 입니다 |
| p^{*}-d^ | 쌍대 간극 | 음이 아닙니다 |
| 약쌍대성 | weak duality | 언제나 성립합니다 |
| 강쌍대성 | strong duality | 간극이 입니다 |
| 슬레이터 조건 | Slater's condition | 내부점의 존재입니다 |
| 안장점 | saddle point | 최소최대의 균형입니다 |
| f^ | 켤레함수 | 르장드르-펜첼 변환입니다 |
| 그람 행렬 | Gram matrix | 내적들의 행렬입니다 |
| 지지 벡터 | support vector | 인 자료점입니다 |
다음 116강에서는 정규화를 제약으로 읽습니다. 능형회귀와 라소가 왜 그런 모양인지, 이 왜 희소해를 주는지가 이 단원의 기하에서 답을 얻습니다. 90강 문제 1에서 본 단위구의 마름모 꼭짓점이 그 근거이며, 이것으로 05단원이 끝납니다.