04단원에서 최소를 찾는 알고리즘을 세웠습니다. 그 전제는 하나였습니다.
제약이 있으면 이 조건이 성립하지 않습니다.
최소점이 제약곡선 위에 갇혀 있으므로, 자유롭게 움직일 수 있었다면 더 내려갔을 자리에 멈춰 섭니다. 그 점에서 기울기가 일 이유가 없습니다.
그럼 무엇이 최적성 조건인가를 물어야 합니다.
답이 이미 95강에 있습니다. 문제 4에서 기울기가 등고선에 수직임을 증명했고, 심화 4에서 이 사실이 라그랑주 승수법의 근거라고 예고했습니다.
제약곡선 은 의 등위집합입니다. 그 위를 움직여도 가 늘지 않아야 하고, 움직일 수 있는 방향은 에 수직인 방향뿐입니다.
같은 방향에 수직인 두 벡터는 평행합니다.
이 강의는 이 조건을 정식화하고, 승수 가 무엇을 뜻하는지를 밝힙니다.
문제. 를 원 위에서 최적화합니다.
(1) 를 구하고 이 되는 점이 있는지 보세요.
(2) 원 위에서 의 최댓값과 최솟값을 수치로 구하세요.
(3) 두 결과가 모순인지 판정하세요.
생각의 실마리. 제약 없는 문제라면 는 최소도 최대도 없습니다. 원 위로 갇히면 이야기가 달라집니다.
풀이. (1) 이며 어디서도 이 아닙니다.
(2) 원을 로 매개화하면 입니다. 검산에서 각도를 만 개로 훑으면
| 항목 | 값 | 각 |
|---|---|---|
| 최댓값 | ||
| 최솟값 |
이론값 와 일치합니다.
(3) 모순이 아닙니다. 제약이 있으면 최적성 조건이 다릅니다.
이 문제에서 배우는 것: 제약 최적화의 최적성 조건.
왜 그런지를 정확히 봅니다. 42강의 페르마 정리는 "극값이면 모든 방향의 방향도함수가 "에서 나왔습니다. 제약이 있으면 모든 방향으로 움직일 수 없습니다.
| 상황 | 움직일 수 있는 방향 | 조건 |
|---|---|---|
| 제약 없음 | 전부 | \nabla f=\mathbf |
| 제약 | 에 수직인 것만 | 그 방향으로만 |
둘째 줄이 훨씬 약한 조건입니다. 허용된 방향에서만 변화율이 이면 되고, 금지된 방향에서는 얼마든지 클 수 있습니다.
제약곡선의 접선 방향을 접공간이라 합니다. 95강 문제 4에 의해
이며 이 위에서만 최적성을 요구합니다.
바로 확인 1.
확인 1-1. 제약이 있으면 이 최적성 조건입니까?
답. 아닙니다. 움직일 수 있는 방향이 제한되기 때문입니다.
확인 1-2. 제약곡선의 접공간을 쓰세요.
답. 에 수직인 벡터들의 집합입니다.
확인 1-3. 최적점에서 요구되는 조건을 쓰세요.
답. 접공간의 모든 방향에서 방향도함수가 입니다.
문제. 같은 문제를 봅니다.
(1) 원 위 여러 점에서 를 구하세요.
(2) 와 의 외적을 계산하세요.
(3) 외적이 인 점과 최적점을 비교하세요.
생각의 실마리. 평면에서 두 벡터가 평행할 조건은 **외적이 **입니다. 65강에서 다뤘습니다.
풀이. (1)과 (2) 이므로 입니다. 검산에서
| 각 | 점 | ||
|---|---|---|---|
(3) 외적이 인 두 점이 정확히 최적점입니다.
이 문제에서 배우는 것: 기울기의 평행 조건.
라그랑주 조건(필요조건). 가 제약 아래 의 극값이고 이면, 어떤 가 있어
입니다.
증명이 95강 문제 4에서 두 줄로 나옵니다.
제약곡선 위의 곡선 로 를 지나게 잡습니다. 이므로 97강의 연쇄법칙으로
한편 에서 가 극값이므로
두 벡터가 같은 에 수직이고, 평면에서 한 벡터에 수직인 방향은 하나뿐이므로 둘이 평행합니다.
기하적으로는 두 등위집합이 접합니다. 의 등고선과 제약곡선이 교차하면 그 점을 따라 움직여 를 줄일 수 있으므로 최적일 수 없고, 접해야만 더 줄일 수 없습니다.
| 상황 | 최적인가 |
|---|---|
| 등고선이 제약곡선을 가로지릅니다 | 아닙니다 |
| 등고선이 제약곡선에 접합니다 | 후보입니다 |
필요조건일 뿐입니다. 조건을 만족하는 점이 최대일 수도 최소일 수도 안장일 수도 있으며, 검산에서 두 점이 각각 최대와 최소였습니다.
바로 확인 2.
확인 2-1. 라그랑주 조건을 쓰세요.
답. 입니다.
확인 2-2. 그 증명의 핵심 두 줄을 쓰세요.
답. 제약 위의 곡선에 대해 이고 입니다.
확인 2-3. 기하적으로 무엇을 뜻합니까?
답. 의 등고선과 제약곡선이 접합니다.
문제. 같은 문제를 라그랑주 조건으로 풉니다.
(1) 라그랑주 함수를 세우세요.
(2) 정류 조건을 쓰고 연립방정식을 푸세요.
(3) 각 해의 와 값을 구하세요.
생각의 실마리. 조건이 와 입니다. 미지수가 셋이고 방정식도 셋이라 풀 수 있습니다.
풀이. (1) 라그랑주 함수를 정의합니다.
(2) 을 세 변수 모두에 대해 쓰면
셋째 식이 제약 자체입니다. 앞의 두 식에서 이므로 이고, 제약에 넣으면 입니다.
(3) 검산에서
이 문제에서 배우는 것: 라그랑주 함수.
라그랑주 함수. 제약 아래 를 최적화할 때
를 라그랑주 함수라 하고, 을 정류 조건이라 합니다.
제약 문제를 제약 없는 문제로 바꿉니다.
로 미분하면 제약이 저절로 나오므로, 제약을 따로 챙길 필요가 없습니다. 이것이 이 형식의 값어치입니다.
| 원래 문제 | 라그랑주 형식 |
|---|---|
| 변수, 제약 개 | 변수, 제약 없음 |
| 최소화 | 정류점 찾기 |
둘째 줄에 주의해야 합니다. 의 정류점은 최소가 아닙니다. 방향으로는 이 선형이라 최소도 최대도 없고, 실제로 안장점입니다. 115강의 쌍대 문제가 이 구조를 정면으로 다룹니다.
부호 규약이 여럿 있습니다. 와 가 모두 쓰이며, 의 부호만 뒤집힙니다. 등식 제약에서는 문제가 되지 않지만 부등식 제약에서는 부호가 중요해지며 114강에서 다룹니다.
바로 확인 3.
확인 3-1. 라그랑주 함수를 쓰세요.
답. 입니다.
확인 3-2. 로 미분하면 무엇이 나옵니까?
답. 제약 입니다.
확인 3-3. 의 정류점은 최소입니까?
답. 아닙니다. 방향으로 선형이라 안장점입니다.
문제. 제약을 로 바꿉니다.
(1) 최적값 를 구하세요.
(2) 를 수치로 구하세요.
(3) 각 에서의 와 비교하세요.
생각의 실마리. 가 계산 과정에서 나온 보조변수처럼 보이는데, 실은 뜻이 있습니다.
풀이. (1) 이므로 입니다.
(2)와 (3) 검산에서
| 최적 f^ | 수치 | 이론 \lambda^ | |
|---|---|---|---|
정확히 같습니다.
이 문제에서 배우는 것: 승수는 잠재가격입니다.
포락선 정리. 제약을 로 두고 최적값을 라 하면
입니다.
증명이 짧습니다. 최적해를 라 하면 이므로 97강의 연쇄법칙으로
한편 를 로 미분하면
**두 식을 합치면 **입니다.
이 해석이 실무에서 핵심입니다.
| 분야 | 의 뜻 |
|---|---|
| 경제학 | 자원 한 단위의 잠재가격 |
| 물리 | 구속력의 크기 |
| 기계학습 | 정규화 강도의 역할 |
| 강화학습 | 제약 위반의 벌점 |
둘째 줄이 이름의 유래입니다. 라그랑주가 역학에서 구속조건을 다루며 도입했고, 가 실제로 구속력에 해당합니다.
의 크기가 알려 주는 것을 정리합니다.
| 뜻 | |
|---|---|
| 크다 | 제약이 강하게 묶고 있습니다 |
| 에 가깝다 | 제약이 거의 무의미합니다 |
| 부호 | 완화가 이득인지 손해인지 |
셋째 줄이 114강에서 중요해집니다. 부등식 제약에서는 이 요구되며, 그 부호가 "어느 쪽으로 완화해야 이득인지"를 말합니다.
바로 확인 4.
확인 4-1. 포락선 정리를 쓰세요.
답. 입니다.
확인 4-2. 의 경제학적 이름을 쓰세요.
답. 잠재가격입니다.
확인 4-3. 이면 무엇을 뜻합니까?
답. 제약을 완화해도 이득이 없다는 뜻입니다.
문제. 을 이고 인 조건에서 최소화합니다.
(1) 라그랑주 조건을 세우세요.
(2) 연립방정식을 풀어 해와 승수를 구하세요.
(3) 방법이 깨지는 조건을 말하세요.
생각의 실마리. 제약이 둘이면 움직일 수 있는 방향이 더 좁아집니다. 두 기울기 모두에 수직인 방향만 남습니다.
풀이. (1) 제약이 과 이므로
두 기울기의 선형결합입니다. 행렬로 쓰면 일 때
(2) 검산에서 이 선형계를 풀면
제약 확인에서 이고
정확히 맞습니다.
(3) 검산에서 제약 기울기가 일차종속인 예를 봅니다. 의 계수가 이며 정상이면 여야 합니다.
이 문제에서 배우는 것: 여러 제약과 제약자격.
일반 라그랑주 조건. 제약 아래 의 극값 에서, 가 일차독립이면
입니다.
"일차독립"이 조건이며 이를 제약자격이라 합니다.
왜 필요한지는 74강의 언어로 설명됩니다. 조건의 뜻은 가 의 생성공간에 있다는 것인데, 그 공간이 제대로 된 차원을 가져야 합니다.
| 제약 수 | 접공간 차원 | 조건 |
|---|---|---|
| 개 독립 | 정상 | |
| 개 종속 | 보다 큼 | 깨짐 |
깨지는 예를 봅니다. 를 이고 에서 최소화하면 실행가능점이 원점 하나입니다. 그런데 원점에서
두 기울기가 같아 일차종속이고, 이 그 생성공간에 없어 라그랑주 조건을 만족하는 가 없습니다.
이 나온 것도 볼 만합니다. 검산에서 둘째 제약의 승수가 인데, 이는 그 제약이 최적점에서 활성이지만 최적값에 영향을 주지 않는다는 뜻입니다. 문제 4의 해석으로 읽으면 를 완화해도 이득이 없습니다.
실제로 만 걸고 풀면 대칭성으로 이 나오며, 둘째 제약 가 저절로 만족됩니다.
바로 확인 5.
확인 5-1. 제약이 개일 때 라그랑주 조건을 쓰세요.
답. 입니다.
확인 5-2. 제약자격이 무엇입니까?
답. 제약 기울기들이 일차독립인 것입니다.
확인 5-3. 이면 무엇을 뜻합니까?
답. 그 제약을 완화해도 최적값이 변하지 않습니다.
| 개념 | 내용 |
|---|---|
| 문제 | subject to |
| 라그랑주 함수 | |
| 조건 | , |
| 기하 | 두 등위집합이 접합니다 |
| 승수 | , 잠재가격 |
| 여러 제약 | 내용 |
|---|---|
| 조건 | \nabla f=\sum\lambda_{i}\nabla g_ |
| 제약자격 | 가 일차독립 |
| 접공간 | 모두에 수직인 방향 |
| 차원 |
| 풀이 절차 | |
|---|---|
| 를 세웁니다 | |
| 모든 변수로 편미분해 으로 둡니다 | |
| 개 방정식을 풉니다 | |
| 후보들의 를 비교합니다 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 을 찾습니다 | 제약이 있으면 조건이 다릅니다 |
| 제약을 빠뜨립니다 | 로 미분하면 나옵니다 |
| 필요조건을 충분조건으로 봅니다 | 후보를 비교해야 합니다 |
| 제약자격을 확인하지 않습니다 | 종속이면 깨집니다 |
| 을 최소화하려 합니다 | 안장점입니다 |
문제 6. 를 에서 최대화하세요.
답. 에서 이고 최댓값 입니다.
문제 7. 을 에서 최소화하세요.
답. 에서 , 제약에 넣으면 , , 최솟값 입니다.
문제 8. 문제 7의 를 구하고 뜻을 쓰세요.
답. 이므로 입니다. 우변을 늘리면 최솟값이 약 늘어납니다.
문제 9. 라그랑주 함수를 로 미분하면 무엇이 나옵니까?
답. 제약식입니다.
문제 10. 원 위에서 의 최댓값을 구하세요.
답. 에서 또는 이며, 에서 최댓값 입니다.
문제 11. 포락선 정리를 쓰세요.
답. 입니다.
문제 12. 인 제약의 뜻을 쓰세요.
답. 완화해도 최적값이 변하지 않는다는 뜻입니다.
문제 13. 제약자격을 쓰세요.
답. 제약 기울기들이 최적점에서 일차독립인 것입니다.
문제 14. 제약이 개면 접공간의 차원을 쓰세요.
답. 제약자격이 성립하면 입니다.
문제 15. 라그랑주 조건이 필요조건입니까 충분조건입니까?
답. 필요조건이며 후보를 비교해야 합니다.
문제 16. 직육면체의 겉넓이가 일정할 때 부피를 최대화하면 어떤 모양입니까?
답. 정육면체입니다. 대칭성에서 세 변이 같아집니다.
문제 17. 에서 를 최대화하면 무엇이 나옵니까?
답. 이므로 고유값 문제이며 최댓값이 입니다.
문제 18. 문제 17이 86강의 무엇과 같습니까?
답. 레일리 몫의 최대화입니다.
심화 1. 라그랑주 조건을 접공간의 언어로 정확히 증명하세요.
문제 2의 증명은 평면에서만 통합니다. 일반 차원에서 다시 합니다.
가 제약 () 아래 극값이고 제약자격이 성립한다고 둡니다.
실행가능 곡선을 잡습니다. 접공간
의 임의의 에 대해, 이고 이며 인 곡선이 존재합니다. 제약자격이 이 존재를 보장하며, 93강 심화 1의 음함수 정리가 근거입니다.
극값 조건을 씁니다. 가 에서 극값이므로
가 임의였으므로
이제 74강을 씁니다. 는 가 생성하는 공간의 직교여공간이므로
따라서 이고, 곧
74강의 네 부분공간이 여기서 쓰입니다. 를 제약 기울기를 행으로 갖는 행렬이라 하면 이고 입니다.
74강 문제 1의 정리 그대로입니다. 라그랑주 승수법이 선형대수의 직교분해에서 나옵니다.
제약자격이 필요한 자리가 분명합니다. 곡선의 존재를 보장하는 데 쓰였고, 종속이면 접공간이 예상보다 커져 논증이 무너집니다.
심화 2. 이계 조건을 세우세요.
라그랑주 조건은 필요조건입니다. 최소인지 최대인지 안장인지 가르려면 02단원의 도구가 필요합니다.
제약 위에서의 헤세를 봐야 합니다. 라그랑주 함수의 헤세를
라 하면, 접공간으로 제한한 이차형식의 부호가 판정합니다.
이계 충분조건. 라그랑주 조건이 성립하고 모든 , 에 대해
이면 는 엄밀한 국소 최소입니다.
101강의 판정과 두 곳이 다릅니다.
| 항목 | 제약 없음 | 제약 있음 |
|---|---|---|
| 헤세 | \nabla^{2}f-\sum\lambda_{i}\nabla^{2}g_ | |
| 방향 | 모든 \mathbf | 안의 만 |
둘 다 조건을 약하게 만듭니다. 전체 공간에서 부정부호여도 접공간에서 양정치이면 최소일 수 있습니다.
문제 1의 예로 확인합니다. 이므로 이고, 이므로 입니다.
인 점에서 이라 음정치이므로 최대이고, 인 점에서는 양정치라 최소입니다. 검산의 값과 맞습니다.
계산하는 방법으로 테두리 헤세가 있습니다.
의 선행 주소행렬식 부호로 판정하며, 87강 실베스터 판정법의 제약판입니다.
심화 3. 고유값 문제가 라그랑주 문제임을 보이세요.
문제 17에서 예고한 것을 정식으로 봅니다.
**제약이 **입니다. 라그랑주 조건을 세우면
이므로
고유값 방정식입니다. 그리고 제약을 쓰면
목적값이 곧 고유값입니다. 따라서 최댓값이 이고 최적해가 그 고유벡터입니다.
여러 곳에서 되돌아옵니다.
| 정리 | 라그랑주 형태 |
|---|---|
| 86강 레일리 몫 | s.t. |
| 88강 특이값 | s.t. |
| 89강 주성분 | 분산 최대화 s.t. 정규직교 |
| 90강 유도 노름 | s.t. |
넷이 모두 같은 구조이며, 승수가 고유값입니다. 문제 4의 해석으로 읽으면 **"단위구의 반지름을 늘렸을 때 목적값이 얼마나 늘어나는가"**가 고유값입니다.
89강의 주성분분석이 특히 그렇습니다. 첫 주성분 다음을 구할 때 "이전 성분들과 직교"라는 제약을 추가하는데, 그 승수들이 앞선 고유값들에 대응합니다.
심화 4. 등식 제약 문제를 수치적으로 푸는 방법을 논하세요.
라그랑주 조건은 비선형 연립방정식입니다. 손으로 풀리는 경우가 드뭅니다.
112강의 뉴턴법을 적용할 수 있습니다. 야코비가
이며 KKT 행렬이라 부릅니다. 이 선형계를 풀어 걸음을 정합니다.
특징이 둘 있습니다.
| 특징 | 내용 |
|---|---|
| 대칭이지만 부정부호 | 안장점 구조입니다 |
| 블록 구조 | 특수한 풀이법이 있습니다 |
첫째 줄 때문에 콜레스키를 쓸 수 없고 LDL 분해나 반복법을 씁니다. 문제 3에서 의 정류점이 안장이라 했는데, 그것이 행렬 수준에서 나타난 것입니다.
다른 접근들도 있습니다.
| 방법 | 내용 |
|---|---|
| 벌점법 | 을 최소화합니다 |
| 확장 라그랑주 | 벌점과 승수를 함께 씁니다 |
| 사영 경사법 | 제약면 위로 사영합니다 |
| 축소 공간법 | 접공간의 좌표로 문제를 줄입니다 |
벌점법이 가장 단순합니다. 제약 위반에 벌점을 물려 제약 없는 문제로 바꾸고, 를 키워 갑니다.
문제는 조건수입니다. 가 크면 헤세의 조건수가 에 비례해 커지고, 110강에서 본 대로 수렴이 느려집니다.
확장 라그랑주가 이를 고칩니다.
승수를 갱신하면 를 무한대로 보내지 않아도 정확한 해에 수렴합니다. ADMM이 이 계열이며 제약이 분리 가능할 때 널리 쓰입니다.
심화 5. 라그랑주 승수가 물리와 경제에서 무엇인지 정리하세요.
물리에서 승수는 구속력입니다.
진자를 생각합니다. 질점이 길이 인 줄에 매달려 있으면
이 제약이고, 라그랑주 방정식에서 나오는 가 줄의 장력입니다.
제약이 없으면 물체는 자유낙하하고, 제약이 있으면 그것을 막는 힘이 필요합니다. 그 힘의 크기가 입니다.
경제에서 승수는 잠재가격입니다. 예산 제약 아래 효용을 최대화하면
에서 이며 소득 한 단위의 한계효용입니다.
| 상황 | |
|---|---|
| 예산이 빡빡합니다 | 큽니다 |
| 예산이 남습니다 | 작습니다 |
| 예산이 무의미합니다 | 입니다 |
기계학습에서도 같은 해석이 통합니다. 116강에서 정규화를 제약으로 읽을 때
의 승수가 정규화 계수 가 되며, **"복잡도 예산을 한 단위 늘렸을 때 손실이 얼마나 주는가"**를 뜻합니다.
강화학습의 제약 정책 최적화도 그렇습니다. 289강의 PPO가 KL 제약을 다루는데, 그 승수가 벌점 계수가 되고 **"정책을 얼마나 크게 바꿔도 되는가"**의 가격입니다.
심화 6. 114강으로 어떻게 이어지는지 정리하세요.
이 강의는 등식 제약만 다뤘습니다. 실무의 제약은 대개 부등식입니다.
결정적인 차이가 있습니다. 등식 제약은 언제나 경계에 붙어 있지만, 부등식 제약은 붙을 수도 안 붙을 수도 있습니다.
| 상황 | 이름 | 최적성 조건 |
|---|---|---|
| 활성 | 등식처럼 다룹니다 | |
| 비활성 | 없는 것처럼 다룹니다 |
어느 쪽인지 미리 모릅니다. 풀어 봐야 압니다.
114강이 이를 하나의 조건으로 묶습니다.
셋째 식이 상보성이며, "둘 중 하나는 "이라는 뜻입니다. 제약이 비활성이면 승수가 이고, 승수가 양수면 제약이 활성입니다.
**부호 조건 **도 새로 생깁니다. 등식에서는 부호가 자유로웠는데, 부등식에서는 한 방향으로만 완화할 수 있으므로 부호가 정해집니다.
115강이 쌍대 문제로 갑니다. 라그랑주 함수를 에 대해 최소화한 것을 의 함수로 보면, 원래 문제와 짝을 이루는 다른 최적화 문제가 나옵니다.
순서를 바꿀 수 있는지가 강쌍대성이며, 볼록이면 대개 성립합니다. 107강 심화 4의 분리 초평면 정리가 그 증명 도구입니다.
116강이 이 단원을 기계학습으로 잇습니다. 정규화가 왜 제약인지, 이 왜 희소해를 주는지가 답을 얻습니다.
import numpy as np
# --- 문제 1: 제약이 있으면 grad f = 0 이 아니다 -------------------------
# max/min f = x + y on x^2 + y^2 = 1
f = lambda x, y: x + y
gf = np.array([1.0, 1.0])
print(" f = x + y 를 원 x^2+y^2=1 위에서 최적화")
print(" grad f = (1, 1) 이라 어디서도 0 이 아닙니다")
th = np.linspace(0, 2*np.pi, 2000001)
vals = np.cos(th) + np.sin(th)
i0, i1 = vals.argmax(), vals.argmin()
print(" 수치 최댓값 %.10f (각 %.6f), 최솟값 %.10f (각 %.6f)"
% (vals[i0], th[i0], vals[i1], th[i1]))
print(" 이론 최대 sqrt(2) = %.10f, 최소 -sqrt(2) = %.10f" % (np.sqrt(2), -np.sqrt(2)))
# f = x + y 를 원 x^2+y^2=1 위에서 최적화
# grad f = (1, 1) 이라 어디서도 0 이 아닙니다
# 수치 최댓값 1.4142135624 (각 0.785398), 최솟값 -1.4142135624 (각 3.926991)
# 이론 최대 sqrt(2) = 1.4142135624, 최소 -sqrt(2) = -1.4142135624
# --- 문제 2: 두 기울기가 평행하다 ---------------------------------------
print(" 최적점에서 grad f 와 grad g 가 평행한지 봅니다")
print(" 각 점 grad g grad f x grad g")
for t in [np.pi/4, 5*np.pi/4, 0.0, 1.0]:
p = np.array([np.cos(t), np.sin(t)]); gg = 2*p
cross = gf[0]*gg[1] - gf[1]*gg[0]
print(" %7.4f (%+.4f,%+.4f) (%+.4f,%+.4f) %+12.8f" % (t, p[0], p[1], gg[0], gg[1], cross))
print(" 외적이 0 인 곳이 최적점입니다 (pi/4 와 5pi/4)")
# 최적점에서 grad f 와 grad g 가 평행한지 봅니다
# 각 점 grad g grad f x grad g
# 0.7854 (+0.7071,+0.7071) (+1.4142,+1.4142) -0.00000000
# 3.9270 (-0.7071,-0.7071) (-1.4142,-1.4142) +0.00000000
# 0.0000 (+1.0000,+0.0000) (+2.0000,+0.0000) -2.00000000
# 1.0000 (+0.5403,+0.8415) (+1.0806,+1.6829) +0.60233736
# 외적이 0 인 곳이 최적점입니다 (pi/4 와 5pi/4)
# --- 문제 3: 라그랑주 방정식을 푼다 -------------------------------------
print(" L = f - lam g 의 정류점: grad f = lam grad g, g = 0")
print(" 1 = 2 lam x, 1 = 2 lam y -> x = y")
print(" x^2 + y^2 = 1 -> x = y = +-1/sqrt(2) = %+.10f" % (1/np.sqrt(2)))
for s in [1, -1]:
x = s/np.sqrt(2); lam = 1/(2*x)
print(" x=y=%+.6f lam=%+.6f f=%+.10f" % (x, lam, 2*x))
# L = f - lam g 의 정류점: grad f = lam grad g, g = 0
# 1 = 2 lam x, 1 = 2 lam y -> x = y
# x^2 + y^2 = 1 -> x = y = +-1/sqrt(2) = +0.7071067812
# x=y=+0.707107 lam=+0.707107 f=+1.4142135624
# x=y=-0.707107 lam=-0.707107 f=-1.4142135624
# --- 문제 4: 승수의 뜻 (제약을 흔들면) ----------------------------------
print(" 제약을 x^2+y^2 = c 로 바꾸면 최적값이 어떻게 변하는가")
print(" c 최적 f 수치 df*/dc 이론 lam*")
for c in [0.5, 1.0, 2.0, 4.0]:
h = 1e-6
v0 = np.sqrt(2*c); vp = np.sqrt(2*(c+h)); vm = np.sqrt(2*(c-h))
num = (vp - vm)/(2*h)
lam = 1/(2*np.sqrt(c/2)) # grad f = lam grad g 에서 lam = 1/(2x), x = sqrt(c/2)
print(" %6.1f %12.8f %14.8f %14.8f" % (c, v0, num, lam))
# 제약을 x^2+y^2 = c 로 바꾸면 최적값이 어떻게 변하는가
# c 최적 f 수치 df*/dc 이론 lam*
# 0.5 1.00000000 1.00000000 1.00000000
# 1.0 1.41421356 0.70710678 0.70710678
# 2.0 2.00000000 0.50000000 0.50000000
# 4.0 2.82842712 0.35355339 0.35355339
# lam 이 정확히 df*/dc 입니다. 승수는 제약 완화의 잠재가격입니다.
# --- 문제 5: 여러 제약과 실패 조건 --------------------------------------
print(" 제약이 둘이면 grad f 가 두 기울기의 선형결합입니다")
# min x^2+y^2+z^2 s.t. x+y+z=1, x-y=0
A = np.array([[1.0,1.0,1.0],[1.0,-1.0,0.0]]); b = np.array([1.0, 0.0])
# KKT: 2x = A^T lam, A x = b
M = np.block([[2*np.eye(3), -A.T],[A, np.zeros((2,2))]])
rhs = np.concatenate([np.zeros(3), b])
sol = np.linalg.solve(M, rhs)
xs, lams = sol[:3], sol[3:]
print(" 해 x = %s, lam = %s" % (np.round(xs,6), np.round(lams,6)))
print(" 제약 확인 A x - b = %s" % np.round(A @ xs - b, 12))
print(" grad f = %s, A^T lam = %s" % (np.round(2*xs,6), np.round(A.T @ lams,6)))
print(" 제약 기울기가 일차종속이면 방법이 깨집니다")
B = np.array([[1.0,1.0],[2.0,2.0]]) # 두 제약이 같은 직선
print(" B = [[1,1],[2,2]] 의 계수 = %d (정상이면 2)" % np.linalg.matrix_rank(B))
# 제약이 둘이면 grad f 가 두 기울기의 선형결합입니다
# 해 x = [0.333333 0.333333 0.333333], lam = [0.666667 0. ]
# 제약 확인 A x - b = [0. 0.]
# grad f = [0.666667 0.666667 0.666667], A^T lam = [0.666667 0.666667 0.666667]
# 제약 기울기가 일차종속이면 방법이 깨집니다
# B = [[1,1],[2,2]] 의 계수 = 1 (정상이면 2)
# lam_2 = 0 은 둘째 제약이 최적값에 영향을 주지 않는다는 뜻입니다.
문제 4의 표가 이 강의의 핵심입니다. 계산 과정의 보조변수처럼 보이던 가 **정확히 **입니다.
114강에서 부등식 제약으로 넓힙니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| \mathcal | 라그랑주 함수 | 입니다 |
| 라그랑주 승수 | 제약의 잠재가격입니다 | |
| 접공간 | 움직일 수 있는 방향입니다 | |
| 제약자격 | constraint qualification | 기울기의 일차독립성입니다 |
| 포락선 정리 | envelope theorem | 입니다 |
| 잠재가격 | shadow price | 경제학의 이름입니다 |
| KKT 행렬 | KKT matrix | 뉴턴법의 야코비입니다 |
| 벌점법 | penalty method | 제약 위반에 벌점을 물립니다 |
| 확장 라그랑주 | augmented Lagrangian | 벌점과 승수를 함께 씁니다 |
다음 114강에서는 부등식 제약과 KKT 조건을 다룹니다. 부등식은 활성일 수도 비활성일 수도 있어 미리 알 수 없으며, 그 둘을 하나로 묶는 것이 상보성 조건 입니다. 승수의 부호 조건 도 새로 생기며, 그 근거가 문제 4의 잠재가격 해석에 있습니다.