113강에서 등식 제약을 다뤘습니다.
실무의 제약은 대개 부등식입니다.
예산은 넘지만 않으면 되고, 확률은 음수가 아니기만 하면 되며, 가중치의 크기는 한도 안이기만 하면 됩니다.
결정적인 차이가 하나 있습니다. 등식 제약은 언제나 경계에 붙어 있지만, 부등식 제약은 붙을 수도 안 붙을 수도 있습니다.
| 상황 | 이름 | 다루는 법 |
|---|---|---|
| 활성 | 등식처럼 | |
| 비활성 | 없는 것처럼 |
어느 쪽인지 미리 알 수 없습니다. 풀어 봐야 압니다.
이 강의는 그 둘을 하나의 조건으로 묶습니다.
**셋째 식이 "둘 중 하나는 "**이라는 뜻이며, 이것이 상보성입니다. 그리고 새로 생긴 부호 조건 의 근거가 113강 문제 4의 잠재가격 해석에 있습니다.
문제. 을 에서 최소화합니다.
(1) 제약 없는 최소를 구하세요.
(2) 그 점이 실행가능한지 에서 확인하세요.
(3) 실제 최소의 위치를 구하세요.
생각의 실마리. 제약 없는 최소가 원판 안에 있으면 제약이 아무 일도 하지 않습니다. 밖에 있으면 경계로 끌려 나옵니다.
풀이. (1) 에서 입니다.
(2)와 (3) 검산에서
| 무제약 최소 | 실행가능 | 실제 최소 | ||
|---|---|---|---|---|
| 실행가능 | ||||
| 실행가능 | ||||
| 실행불가 | ||||
| 실행불가 |
에 따라 상황이 갈립니다.
이 문제에서 배우는 것: 활성과 비활성.
활성 제약. 최적점에서 이면 그 제약이 활성이고, 이면 비활성입니다.
비활성이면 제약이 없는 것과 같습니다. 그 근방에서 여전히 이므로 자유롭게 움직일 수 있고, 최적성 조건이 입니다.
활성이면 등식 제약처럼 다룹니다. 경계에 붙어 있으므로 113강의 논증이 그대로 적용됩니다.
문제는 어느 쪽인지 모른다는 점입니다.
| 접근 | 문제 |
|---|---|
| 모든 조합을 시도 | 제약 개면 가지 |
| 하나의 조건으로 통합 | 문제 2의 KKT |
첫째 줄이 활성집합법이며 제약이 적으면 실용적입니다. 하지만 이 크면 폭발합니다.
이 경계 사례입니다. 제약 없는 최소가 정확히 경계 위에 있어 활성이지만, 제약을 풀어도 답이 같습니다. 문제 2에서 이 경우 승수가 임을 봅니다.
바로 확인 1.
확인 1-1. 활성 제약의 정의를 쓰세요.
답. 최적점에서 등호가 성립하는 제약입니다.
확인 1-2. 비활성 제약은 최적성 조건에 어떻게 기여합니까?
답. 기여하지 않습니다. 없는 것과 같습니다.
확인 1-3. 제약이 개면 활성 조합이 몇 가지입니까?
답. 가지입니다.
문제. 같은 문제를 봅니다.
(1) 각 에서 승수 를 구하세요.
(2) 와 를 계산하세요.
(3) 어떤 규칙이 보이는지 말하세요.
생각의 실마리. 비활성이면 승수가 일 것이고, 활성이면 일 것입니다. **둘 중 하나는 언제나 **입니다.
풀이. (1)과 (2) 검산에서
| x^ | \mu^ | 활성 | |||
|---|---|---|---|---|---|
| 비활성 | |||||
| 활성 | |||||
| 활성 | |||||
| 활성 |
(3) **가 언제나 **입니다.
이 문제에서 배우는 것: KKT 조건.
KKT 조건. subject to , 의 최적점에서 제약자격이 성립하면, 승수 과 가 있어 다음이 성립합니다.
이름 조건 정류성 \nabla f+\sum\mu_{i}\nabla h_{i}+\sum\lambda_{j}\nabla g_{j}=\mathbf 원시 실행가능 , 쌍대 실행가능 상보성
넷째 줄이 이 강의의 핵심입니다.
**"둘 중 하나는 "**이라는 뜻이며, 두 경우를 하나의 방정식으로 묶습니다.
표의 둘째 줄이 미묘합니다. 에서 제약이 활성인데 승수가 입니다. 상보성은 만족하지만 **둘 다 **인 경우이며, 퇴화라 부릅니다.
| 경우 | 이름 | ||
|---|---|---|---|
| 비활성 | 정상 | ||
| 강활성 | 정상 | ||
| 약활성 | 퇴화 |
셋째 줄에서 판정이 애매해집니다. 제약을 지워도 답이 같으므로 실질적으로는 비활성인 셈입니다.
정류성의 부호도 짚어 둡니다. 113강에서 라 썼는데 여기서는 입니다. 이 실행가능 영역이므로 가 영역 안쪽을 향하고, 그 방향으로 가 줄지 않아야 한다는 요구가 부호를 정합니다.
바로 확인 2.
확인 2-1. KKT의 네 조건을 쓰세요.
답. 정류성, 원시 실행가능, 쌍대 실행가능, 상보성입니다.
확인 2-2. 상보성 조건을 쓰고 그 뜻을 쓰세요.
답. 이며 둘 중 하나가 이라는 뜻입니다.
확인 2-3. 퇴화가 무엇입니까?
답. 제약이 활성인데 승수도 인 경우입니다.
문제. 제약을 로 완화합니다().
(1) 여러 에서 최적값을 구하세요.
(2) 를 수치로 구하세요.
(3) 와 비교하세요.
생각의 실마리. 113강 문제 4에서 승수가 였습니다. 부등식에서는 부호가 정해질 것입니다.
풀이. 검산에서 이므로 허용 반지름이 입니다.
| 허용 반지름 | 최적 | 수치 | -\mu^ | |
|---|---|---|---|---|
정확히 일치합니다.
이 문제에서 배우는 것: 부호 조건의 근거.
포락선 정리(부등식). 제약을 로 두면
입니다.
이 요구되는 이유가 여기 있습니다.
영역이 넓어지면 최솟값은 늘어날 수 없습니다. 더 많은 선택지가 생겼으니 나빠질 수 없습니다.
부호 조건이 논리에서 나옵니다. 억지로 붙인 규칙이 아니라, 부등식 제약의 방향이 정하는 것입니다.
등식과 비교하면 차이가 분명합니다.
| 제약 | 완화 방향 | 승수 부호 |
|---|---|---|
| 양쪽 모두 | 자유 | |
| 한쪽만 |
등식은 를 늘리든 줄이든 새 문제가 되고 어느 쪽이 이득인지 정해져 있지 않습니다. 부등식은 늘리는 것만이 완화이므로 방향이 하나입니다.
의 크기가 알려 주는 것도 같습니다.
| 뜻 | |
|---|---|
| 크다 | 제약이 강하게 묶고 있습니다 |
| 작다 | 거의 자유롭습니다 |
| 제약이 무의미합니다 |
검산에서 가 클수록 가 큽니다. 면 , 이면 이며, 목표가 멀수록 제약이 강하게 붙듭니다.
바로 확인 3.
확인 3-1. 부등식의 포락선 정리를 쓰세요.
답. 입니다.
확인 3-2. 의 근거를 쓰세요.
답. 영역을 넓히면 최솟값이 늘 수 없으므로 입니다.
확인 3-3. 등식 제약의 승수 부호는 어떻습니까?
답. 자유입니다. 양쪽으로 완화할 수 있기 때문입니다.
문제. 을 , , 에서 최소화합니다.
(1) 여러 후보의 실행가능성과 를 구하세요.
(2) 최적해를 찾고 활성 제약을 밝히세요.
(3) KKT를 확인하세요.
생각의 실마리. 무제약 최소는 인데 라 실행불가입니다. 경계로 끌려 나옵니다.
풀이. (1) 검산에서
| 후보 | 실행가능 | 활성 제약 | |
|---|---|---|---|
| 예 | |||
| 예 | , | ||
| 예 | , | ||
| 아니오 | 없음 | ||
| 예 | , |
(2) 최적해가 이고 만 활성입니다.
(3) 검산에서 이고 활성 제약 의 기울기가 이므로
KKT를 만족합니다.
이 문제에서 배우는 것: 활성집합.
활성집합. 을 활성집합이라 하며, KKT 조건은 활성 제약만으로 쓸 수 있습니다.
비활성 제약은 이므로 합에서 사라집니다.
기하적 해석이 있습니다. 활성 제약들의 기울기가 이루는 원뿔을 봅니다.
가 그 원뿔 안에 있어야 합니다. 113강에서는 생성공간이었는데, 여기서는 계수가 음이 아닌 결합만 허용되므로 원뿔입니다.
| 제약 | 허용되는 결합 | 기하 |
|---|---|---|
| 등식 | 임의의 실수 계수 | 부분공간 |
| 부등식 | 음이 아닌 계수 | 볼록원뿔 |
이것이 파르카스 보조정리로 이어집니다. 107강 심화 4의 분리 초평면 정리에서 나오며, 115강 쌍대성의 뼈대입니다.
과 가 최적이 아닌 이유도 확인할 만합니다. 에서 활성 제약이 둘이고
인데 를 과 의 음이 아닌 결합으로 쓸 수 없습니다. 에서 이면 이라 부호 조건을 어깁니다.
바로 확인 4.
확인 4-1. 활성집합의 정의를 쓰세요.
답. 등호가 성립하는 제약들의 집합입니다.
확인 4-2. KKT의 기하적 형태를 쓰세요.
답. 가 활성 제약 기울기들의 볼록원뿔 안에 있습니다.
확인 4-3. 등식 제약과 무엇이 다릅니까?
답. 계수가 음이 아니어야 하므로 부분공간이 아니라 원뿔입니다.
문제. 을 에서 풉니다.
(1) 여러 에 대해 해를 구하세요.
(2) 승수를 구하고 상보성을 확인하세요.
(3) KKT 정류 조건이 무엇을 뜻하는지 쓰세요.
생각의 실마리. 109강 심화 4에서 사영 경사법을 봤습니다. 그 사영이 실은 제약 최적화 문제입니다.
풀이. (1)과 (2) 검산에서 로 두면
| \mathbf | 사영 \mathbf | ||||
|---|---|---|---|---|---|
상보성이 모든 경우에 성립합니다.
(3) 정류 조건이
검산에서 이고 이라 **비가 정확히 **입니다.
이 문제에서 배우는 것: 사영의 KKT 해석.
**"사영 벡터와 오차 벡터가 평행"**하다는 뜻이며, 기하적으로 명백합니다. 원점에서 로 가는 직선이 구를 뚫는 점이 사영입니다.
80강의 정사영과 대비하면 구조가 보입니다.
| 대상 | 조건 |
|---|---|
| 부분공간으로의 사영 | 부분공간 |
| 볼록집합으로의 사영 |
둘째 줄이 일반형이며 변분부등식이라 부릅니다. **"에서 집합 안 어느 쪽으로 가도 에 가까워지지 않는다"**는 뜻입니다.
이 관점이 여러 알고리즘의 근거입니다.
| 알고리즘 | 사영의 역할 |
|---|---|
| 사영 경사법 | 매 걸음 실행가능 영역으로 되돌립니다 |
| 근위 경사법 | 사영을 일반화한 근위 연산자 |
| 교대 사영법 | 여러 집합의 교집합을 찾습니다 |
| ADMM | 분리된 문제를 번갈아 풉니다 |
둘째 줄이 116강에서 중요해집니다. 정규화의 근위 연산자가 연성 문턱이며, 그것이 라소의 희소성을 만듭니다.
바로 확인 5.
확인 5-1. 단위공 사영의 KKT 정류 조건을 쓰세요.
답. 입니다.
확인 5-2. 그 기하적 뜻을 쓰세요.
답. 오차 벡터가 사영 벡터와 평행합니다.
확인 5-3. 볼록집합 사영의 일반 조건을 쓰세요.
답. 이며 변분부등식이라 합니다.
| KKT 조건 | 식 |
|---|---|
| 정류성 | \nabla f+\sum\mu_{i}\nabla h_{i}+\sum\lambda_{j}\nabla g_{j}=\mathbf |
| 원시 실행가능 | , |
| 쌍대 실행가능 | |
| 상보성 |
| 제약의 상태 | ||
|---|---|---|
| 비활성 | ||
| 강활성 | ||
| 약활성(퇴화) |
| 해석 | 내용 |
|---|---|
| 완화의 이득 | |
| 넓히면 나빠질 수 없음 | |
| 기하 | 가 활성 기울기의 원뿔 안 |
| 사영 | \mathbf{z}-\mathbf{p}=\mu\mathbf |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 모든 제약을 등식으로 봅니다 | 활성인지 확인합니다 |
| 승수 부호를 잊습니다 | 입니다 |
| 상보성을 빠뜨립니다 | 이 필수입니다 |
| 부호 규약을 섞습니다 | 과 를 짝지웁니다 |
| KKT를 충분조건으로 봅니다 | 볼록일 때만 충분합니다 |
문제 6. KKT의 네 조건 이름을 쓰세요.
답. 정류성, 원시 실행가능, 쌍대 실행가능, 상보성입니다.
문제 7. 상보성 조건을 쓰세요.
답. 입니다.
문제 8. 비활성 제약의 승수는 얼마입니까?
답. 입니다.
문제 9. 의 근거를 쓰세요.
답. 실행가능 영역을 넓히면 최솟값이 늘 수 없기 때문입니다.
문제 10. subject to 의 해와 승수를 구하세요.
답. 이고 , 활성이면 , 입니다.
문제 11. subject to 의 해와 승수를 구하세요.
답. 무제약 최소 이 실행가능하므로 비활성이고 입니다.
문제 12. 활성집합의 정의를 쓰세요.
답. 등호가 성립하는 제약들의 집합입니다.
문제 13. KKT의 기하적 형태를 쓰세요.
답. 가 활성 제약 기울기들의 볼록원뿔 안에 있습니다.
문제 14. 등식과 부등식의 승수 부호를 비교하세요.
답. 등식은 자유이고 부등식은 음이 아니어야 합니다.
문제 15. 퇴화가 무엇입니까?
답. 제약이 활성인데 승수도 인 경우입니다.
문제 16. 단위공 사영의 KKT 조건을 쓰세요.
답. 이며 이면 입니다.
문제 17. 볼록집합 사영의 변분부등식을 쓰세요.
답. 입니다.
문제 18. KKT가 충분조건이 되는 경우를 쓰세요.
답. 와 가 볼록이고 가 아핀일 때입니다.
심화 1. KKT 조건을 유도하세요.
활성집합을 알고 있다면 113강으로 환원됩니다. 문제는 부호 조건입니다.
가 최적이고 활성집합이 라 합니다. 비활성 제약은 근방에서 여전히 이라 무시할 수 있으므로, 활성 제약만 등식으로 보면 113강에서
여기까지는 의 부호가 자유입니다.
부호를 얻으려면 한쪽으로만 움직여 봅니다. 어떤 에 대해 이라 가정하고 모순을 이끕니다.
만 완화하는 방향 를 잡습니다.
제약자격이 이런 의 존재를 보장합니다. 이 방향으로 조금 가면 이 되어 여전히 실행가능하고, 의 변화는
이고 이면 곱이 양수이므로 를 붙이면 음수입니다.
실행가능한 방향으로 가 줄어듭니다. 가 최적이라는 가정에 어긋납니다.
상보성은 정의에서 따라옵니다. 활성이면 이고 비활성이면 으로 두면 되므로, 두 경우 모두 입니다.
엄밀한 증명은 파르카스 보조정리를 씁니다.
파르카스 보조정리. 이고 인 가 없을 필요충분조건은 인 이 있는 것입니다.
둘 중 정확히 하나만 성립하며 택일 정리라 부릅니다. 107강 심화 4의 분리 초평면 정리에서 나오고, 115강 쌍대성의 기초입니다.
심화 2. KKT가 충분조건이 되는 경우를 밝히세요.
KKT는 필요조건입니다. 볼록이면 충분조건이 됩니다.
정리. 와 가 볼록이고 가 아핀이며 가 KKT 조건을 만족하면, 는 전역 최소입니다.
증명. 라그랑주 함수
를 봅니다. 이고 가 볼록이므로 가 볼록이고, 가 아핀이라 도 볼록입니다. 따라서 이 에 대해 볼록입니다.
정류성에서 이므로 107강 문제 3의 따름정리에 의해 가 의 전역 최소입니다.
이제 임의의 실행가능 에 대해
**첫 부등호는 이고 이며 **이기 때문입니다. 그리고 상보성에서
**따라서 **입니다.
세 조건이 각각 한 번씩 쓰였습니다.
| 조건 | 쓰인 곳 |
|---|---|
| 정류성 | 의 최소 |
| 쌍대 실행가능 | 첫 부등호 |
| 상보성 | 마지막 등식 |
이 증명이 115강 약쌍대성의 원형입니다. 거기서 같은 논증을 일반화해 쌍대 함수의 하한 성질을 얻습니다.
비볼록에서는 충분조건이 아닙니다. KKT를 만족하는 점이 최대이거나 안장일 수 있으며, 101강의 상황과 같습니다. 이계 조건을 따로 확인해야 합니다.
심화 3. 선형계획법의 KKT를 살펴보세요.
가장 단순하면서 가장 널리 쓰이는 경우입니다.
KKT를 세웁니다. 과 이므로
상보성은
**둘째 식이 "변수가 양수면 그 여유변수가 "**이라는 뜻입니다.
정리하면 세 묶음입니다.
| 묶음 | 조건 |
|---|---|
| 원시 | , \mathbf{x}\ge\mathbf |
| 쌍대 | , \mathbf{y}\ge\mathbf |
| 상보성 | , |
둘째 줄이 쌍대 문제입니다. 115강에서 정식으로 다루지만, KKT에서 이미 모습을 드러냅니다.
상보성이 두 문제를 잇습니다. 원시 최적해와 쌍대 최적해가 상보성을 만족하고, 그때 목적값이 같습니다.
선형계획법에서는 강쌍대성이 언제나 성립합니다. 실행가능해가 존재하는 한 예외가 없으며, 볼록 문제 중에서도 특히 좋은 성질입니다.
심플렉스법이 이 구조를 씁니다. 꼭짓점을 옮겨 다니며 원시 실행가능성을 유지하고 쌍대 실행가능성을 회복하려 하며, 둘이 함께 성립하면 상보성이 자동으로 따라와 최적입니다.
심화 4. 지지 벡터 머신의 KKT를 미리 보세요.
214강에서 다룰 문제이지만 KKT의 가장 아름다운 예라 미리 봅니다.
목적은 여백을 최대화하는 것이고, 제약은 모든 점이 올바르게 분류되고 여백 밖에 있어야 한다는 것입니다.
KKT를 세우면 정류성에서
가중치가 데이터의 선형결합입니다. 그리고 상보성에서
**여백 밖의 점은 **이므로 에 기여하지 않습니다.
그 점들이 지지 벡터이며 이름의 유래입니다. 데이터가 백만 개여도 지지 벡터가 수십 개면 그것만으로 분류기가 결정됩니다.
| 점의 위치 | \mu_ | 역할 |
|---|---|---|
| 여백 밖 | 없음 | |
| 여백 위 | 지지 벡터 |
상보성 조건 하나가 이 희소성을 만듭니다. 알고리즘을 설계해서 얻은 것이 아니라 최적성 조건에서 저절로 나옵니다.
116강의 라소도 같은 구조입니다. 제약의 KKT에서 대부분의 계수가 정확히 이 되며, 그것이 변수 선택 효과를 만듭니다.
심화 5. 내부점법을 소개하세요.
KKT 조건을 직접 푸는 것이 자연스러운 접근입니다. 문제는 상보성입니다.
이 조건은 비선형이고 비매끄럽습니다. 어느 쪽이 인지에 따라 다른 방정식이 되므로 112강의 뉴턴법을 그대로 쓸 수 없습니다.
내부점법의 발상은 그것을 완화하는 것입니다.
대신 작은 음수로 두면 매끄러운 방정식이 되고 뉴턴법을 쓸 수 있습니다. 그리고 으로 보냅니다.
동등한 관점이 장벽함수입니다. 제약을 목적함수에 녹입니다.
이면 로그가 로 발산하므로 경계에 다가갈 수 없습니다. 실행가능 영역 내부에 머무는 것이 이름의 유래입니다.
| 거동 | |
|---|---|
| 크다 | 중심에 머뭅니다 |
| 작다 | 경계에 다가갑니다 |
| 최적해로 수렴합니다 |
중심경로를 따라간다고 표현하며, 각 의 해가 매끄러운 곡선을 이룹니다.
놀라운 결과가 있습니다. 선형계획법에서 내부점법이 다항시간에 수렴하며, 심플렉스법의 최악 지수시간과 대비됩니다. 큰 문제에서 실용적이며 원뿔계획법과 반정부호계획법으로 확장됩니다.
기계학습에서도 쓰입니다. SVM의 이차계획법을 풀 때 표준 도구이며, 209강의 볼록 최적화 솔버들이 대개 내부점법 기반입니다.
심화 6. 115강으로 어떻게 이어지는지 정리하세요.
이 강의에서 KKT 조건을 세웠습니다. 그 안에 이미 쌍대 문제가 숨어 있습니다.
심화 3의 선형계획법에서 봤듯, KKT의 조건들이 자연스럽게 두 묶음으로 나뉩니다.
| 묶음 | 변수 | 조건 |
|---|---|---|
| 원시 | \mathbf | 실행가능성 |
| 쌍대 | \boldsymbol{\mu},\boldsymbol | 과 정류성 |
115강이 이 대칭을 정면으로 다룹니다.
라그랑주 함수를 에 대해 최소화한 것을 쌍대 함수라 합니다.
심화 2의 증명이 이미 핵심을 보였습니다. 임의의 실행가능 와 에 대해
쌍대 함수가 언제나 원시 최적값의 하한이며 이를 약쌍대성이라 합니다.
둘이 같아지는지가 강쌍대성이며, 볼록이면 대개 성립합니다. 그 조건이 슬레이터 조건이고, 증명 도구가 107강 심화 4의 분리 초평면 정리입니다.
쌍대로 가는 이득이 셋 있습니다.
| 이득 | 내용 |
|---|---|
| 하한을 줍니다 | 최적값의 보증 |
| 제약이 단순해집니다 | 만 남습니다 |
| 구조가 드러납니다 | SVM의 커널 기법 |
셋째 줄이 실무에서 큽니다. SVM의 쌍대 문제에서 데이터가 내적으로만 나타나고, 그것을 커널로 바꾸면 비선형 분류가 됩니다. 214강에서 다룹니다.
116강이 05단원을 닫습니다. 정규화를 제약으로 읽으며, 이 단원의 승수가 정규화 계수임을 확인합니다.
import numpy as np
# --- 문제 1: 제약이 붙을 수도 안 붙을 수도 있다 -------------------------
# min (x-a)^2 + y^2 s.t. x^2+y^2 <= 1
print(" min (x-a)^2 + y^2 s.t. x^2+y^2 <= 1")
print(" a 무제약 최소 실행가능? 실제 최소 위치 h(x*)")
for a in [0.5, 1.0, 2.0, 3.0]:
if abs(a) <= 1: xs, ys = a, 0.0
else: xs, ys = np.sign(a)*1.0, 0.0
print(" %6.1f (%.1f, 0.0) %-9s (%+.4f, %+.4f) %+8.4f"
% (a, a, "실행가능" if abs(a) <= 1 else "실행불가", xs, ys, xs**2+ys**2-1))
# min (x-a)^2 + y^2 s.t. x^2+y^2 <= 1
# a 무제약 최소 실행가능? 실제 최소 위치 h(x*)
# 0.5 (0.5, 0.0) 실행가능 (+0.5000, +0.0000) -0.7500
# 1.0 (1.0, 0.0) 실행가능 (+1.0000, +0.0000) +0.0000
# 2.0 (2.0, 0.0) 실행불가 (+1.0000, +0.0000) +0.0000
# 3.0 (3.0, 0.0) 실행불가 (+1.0000, +0.0000) +0.0000
# --- 문제 2: 상보성 조건 ------------------------------------------------
print(" KKT: grad f = -mu grad h, mu >= 0, h <= 0, mu h = 0")
print(" a x* mu* h(x*) mu*h(x*) 활성?")
for a in [0.5, 1.0, 2.0, 3.0]:
if abs(a) <= 1:
xs = a; mu = 0.0
else:
xs = 1.0; mu = (a - xs)/xs # 2(x-a) + 2 mu x = 0 -> mu = (a-x)/x
h = xs**2 - 1
print(" %6.1f %+.4f %+8.4f %+8.4f %+9.4f %s"
% (a, xs, mu, h, mu*h, "활성" if abs(h) < 1e-12 else "비활성"))
# KKT: grad f = -mu grad h, mu >= 0, h <= 0, mu h = 0
# a x* mu* h(x*) mu*h(x*) 활성?
# 0.5 +0.5000 +0.0000 -0.7500 -0.0000 비활성
# 1.0 +1.0000 +0.0000 +0.0000 +0.0000 활성
# 2.0 +1.0000 +1.0000 +0.0000 +0.0000 활성
# 3.0 +1.0000 +2.0000 +0.0000 +0.0000 활성
# mu*h 가 언제나 0 입니다. a=1 은 둘 다 0 인 퇴화입니다.
# --- 문제 3: 승수의 부호가 왜 정해지는가 --------------------------------
print(" 제약을 h <= t 로 완화하면 최적값이 어떻게 변하는가 (a=2)")
a = 2.0
print(" t 허용 반지름 최적 f 수치 df*/dt -mu*")
for t in [-0.19, 0.0, 0.21, 0.44]:
r = np.sqrt(1+t)
fv = (r - a)**2
hh = 1e-7
fp = (np.sqrt(1+t+hh) - a)**2; fm = (np.sqrt(1+t-hh) - a)**2
num = (fp - fm)/(2*hh)
mu = (a - r)/r
print(" %6.2f %11.6f %12.6f %14.6f %12.6f" % (t, r, fv, num, -mu))
# 제약을 h <= t 로 완화하면 최적값이 어떻게 변하는가 (a=2)
# t 허용 반지름 최적 f 수치 df*/dt -mu*
# -0.19 0.900000 1.210000 -1.222222 -1.222222
# 0.00 1.000000 1.000000 -1.000000 -1.000000
# 0.21 1.100000 0.810000 -0.818182 -0.818182
# 0.44 1.200000 0.640000 -0.666667 -0.666667
# df*/dt = -mu 입니다. 넓히면 나빠질 수 없으므로 mu >= 0 이 나옵니다.
# --- 문제 4: 부등식이 여럿일 때 활성 집합 -------------------------------
print(" min (x-2)^2 + (y-2)^2 s.t. x+y <= 2, x >= 0, y >= 0")
print(" 후보 실행가능 f 활성 제약")
cands = [(1.0,1.0), (2.0,0.0), (0.0,2.0), (2.0,2.0), (0.0,0.0)]
for (x, y) in cands:
feas = (x+y <= 2+1e-12) and (x >= -1e-12) and (y >= -1e-12)
act = []
if abs(x+y-2) < 1e-12: act.append("x+y=2")
if abs(x) < 1e-12: act.append("x=0")
if abs(y) < 1e-12: act.append("y=0")
print(" (%.1f, %.1f) %-8s %6.2f %s"
% (x, y, "예" if feas else "아니오", (x-2)**2+(y-2)**2, ", ".join(act) if act else "없음"))
print(" 최적해는 (1,1) 이며 x+y=2 만 활성입니다")
print(" grad f(1,1) = %s, 활성 제약 기울기 (1,1)" % np.array([-2.0,-2.0]))
print(" grad f = -mu (1,1) 에서 mu = %.1f >= 0 이라 KKT 만족" % 2.0)
# min (x-2)^2 + (y-2)^2 s.t. x+y <= 2, x >= 0, y >= 0
# 후보 실행가능 f 활성 제약
# (1.0, 1.0) 예 2.00 x+y=2
# (2.0, 0.0) 예 4.00 x+y=2, y=0
# (0.0, 2.0) 예 4.00 x+y=2, x=0
# (2.0, 2.0) 아니오 0.00 없음
# (0.0, 0.0) 예 8.00 x=0, y=0
# 최적해는 (1,1) 이며 x+y=2 만 활성입니다
# grad f(1,1) = [-2. -2.], 활성 제약 기울기 (1,1)
# grad f = -mu (1,1) 에서 mu = 2.0 >= 0 이라 KKT 만족
# --- 문제 5: 사영과 KKT ------------------------------------------------
print(" min (1/2)|x-z|^2 s.t. h(x) = |x| - 1 <= 0 의 해는 단위공으로의 사영입니다")
print(" z |z| 사영 p mu = |z|-1 h(p) mu*h(p)")
for z in [np.array([3.0, 4.0]), np.array([0.3, 0.4]), np.array([-6.0, 8.0])]:
n = np.linalg.norm(z)
p = z if n <= 1 else z/n
mu = 0.0 if n <= 1 else (n - 1.0)
hp = np.linalg.norm(p) - 1.0
print(" %-12s %6.2f %-16s %8.4f %+9.4f %+9.4f"
% (np.array2string(np.round(z,1)), n, np.array2string(np.round(p,4)), mu, hp, mu*hp))
print(" KKT 는 (p - z) + mu * p = 0, 즉 z - p = mu p 입니다")
z = np.array([3.0, 4.0]); p = z/np.linalg.norm(z)
print(" z - p = %s, p = %s, 비 = %s (= mu = %.1f)"
% (np.round(z-p,4), np.round(p,4), np.round((z-p)/p,4), np.linalg.norm(z)-1))
# min (1/2)|x-z|^2 s.t. h(x) = |x| - 1 <= 0 의 해는 단위공으로의 사영입니다
# z |z| 사영 p mu = |z|-1 h(p) mu*h(p)
# [3. 4.] 5.00 [0.6 0.8] 4.0000 +0.0000 +0.0000
# [0.3 0.4] 0.50 [0.3 0.4] 0.0000 -0.5000 -0.0000
# [-6. 8.] 10.00 [-0.6 0.8] 9.0000 +0.0000 +0.0000
# KKT 는 (p - z) + mu * p = 0, 즉 z - p = mu p 입니다
# z - p = [2.4 3.2], p = [0.6 0.8], 비 = [4. 4.] (= mu = 4.0)
# 사영은 제약 최적화의 가장 단순한 예이며 오차 벡터가 사영 벡터와 평행합니다.
문제 2의 표가 이 강의의 요지입니다. 활성이든 비활성이든 가 언제나 이며, 그 한 식이 두 경우를 묶습니다.
115강에서 이 조건들이 쌍대 문제를 낳는 것을 봅니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 부등식 제약 | 실행가능 영역을 정합니다 | |
| 부등식 승수 | 음이 아니어야 합니다 | |
| 상보성 | 둘 중 하나가 입니다 | |
| 활성집합 | 등호가 성립하는 제약들입니다 | |
| 퇴화 | degenerate | 활성인데 승수가 입니다 |
| 볼록원뿔 | convex cone | 음이 아닌 결합의 집합입니다 |
| 파르카스 보조정리 | Farkas' lemma | 택일 정리입니다 |
| 슬레이터 조건 | Slater's condition | 강쌍대성의 충분조건입니다 |
| 내부점법 | interior point method | 상보성을 완화해 풉니다 |
| 중심경로 | central path | 에 따른 해의 곡선입니다 |
다음 115강에서는 쌍대 문제를 다룹니다. 이 강의의 KKT 조건 안에 이미 두 묶음이 나뉘어 있었고, 그 대칭을 정면으로 봅니다. 라그랑주 함수를 에 대해 최소화하면 언제나 원시 최적값의 하한을 주며, 볼록이면 둘이 같아집니다. 그 등식이 SVM의 커널 기법을 낳습니다.