02단원에서 무엇이 최소인가에 답했습니다. 헤세의 고유값 부호로 극소와 극대와 안장을 갈랐습니다.
그런데 101강 심화 2에서 남긴 문제가 있습니다.
판정법은 한 점 주변만 봅니다. 그 점이 근방에서 가장 낮다고 말할 뿐, 멀리 더 낮은 곳이 있는지는 아무 말도 하지 않습니다. 최적화의 목표는 전역 최소인데 도구는 국소적입니다.
이 간극을 메우는 성질이 하나 있습니다.
볼록성이 국소를 전역으로 승격시킵니다. 그러면 임계점을 하나만 찾아도 그것이 답이고, 어디서 출발하든 같은 곳에 도착합니다.
이 강의는 볼록집합과 볼록함수를 정의하고, 왜 그 승격이 일어나는지를 증명합니다. 그리고 볼록성이 없으면 무슨 일이 생기는지를 수치로 봅니다.
문제. 다음 집합에서 두 점을 무작위로 뽑아 잇는 선분이 집합 안에 있는지 봅니다.
(1) 원판, 반평면, 정사각형
(2) 고리
(3) 떨어진 두 원판의 합집합
생각의 실마리. "볼록하다"는 말을 선분으로 정의합니다. 집합 안의 어떤 두 점을 이어도 그 선분이 집합을 벗어나지 않으면 볼록합니다.
풀이. 검산에서 각 집합에서 두 점을 뽑아 그 사이의 무작위 점이 집합 안에 있는 비율을 셉니다.
| 집합 | 비율 |
|---|---|
| 원판 | |
| 고리 | |
| 반평면 | |
| 두 원판의 합집합 | |
| 정사각형 |
세 집합은 언제나 이고 두 집합은 그렇지 않습니다.
고리는 안쪽 구멍을 가로지르는 선분이 빠져나가고, 두 원판은 사이의 빈 곳을 지납니다.
이 문제에서 배우는 것: 볼록집합.
볼록집합. 집합 이 볼록하다 함은 모든 와 에 대해
인 것입니다.
를 두 점의 볼록결합이라 하며, 가 에서 로 갈 때 에서 까지의 선분을 훑습니다.
대표적인 볼록집합을 정리합니다.
| 집합 | 볼록 |
|---|---|
| 초평면 | 예 |
| 반공간 | 예 |
| 공 | 예 |
| 부분공간과 아핀공간 | 예 |
| 다면체 A\mathbf{x}\le\mathbf | 예 |
| 구면 | 아니오 |
| 정수 격자 | 아니오 |
연산이 볼록성을 보존하는지가 실무에서 더 중요합니다.
| 연산 | 보존 |
|---|---|
| 교집합 | 보존합니다 |
| 합집합 | 보존하지 않습니다 |
| 아핀상 A C+\mathbf | 보존합니다 |
| 데카르트 곱 | 보존합니다 |
교집합이 보존되는 것이 핵심입니다. 반공간이 볼록하고 교집합이 볼록하므로, 부등식 여러 개로 정의된 영역이 자동으로 볼록합니다. 선형계획법의 실행가능영역이 그것이며, 113강부터 다룰 제약 최적화의 무대입니다.
합집합이 보존되지 않는 것은 검산의 다섯째 줄이 보였습니다. 두 볼록집합의 합집합은 대개 볼록하지 않습니다.
바로 확인 1.
확인 1-1. 볼록집합의 정의를 쓰세요.
답. 안의 두 점을 잇는 선분이 언제나 집합 안에 있는 것입니다.
확인 1-2. 볼록집합의 교집합은 볼록합니까?
답. 볼록합니다.
확인 1-3. 합집합은 어떻습니까?
답. 대개 볼록하지 않습니다.
문제. 다음 함수들이 를 만족하는지 확인하세요.
(1) , ,
(2) , ,
(3) 위반 횟수로 판정하세요.
생각의 실마리. 부등식을 그림으로 읽으면 뜻이 분명합니다. 왼쪽은 두 점 사이의 함숫값이고 오른쪽은 두 점을 이은 현 위의 값입니다.
풀이. 검산에서 무작위 를 번 뽑아 위반 횟수를 셉니다.
| 함수 | 위반 횟수 |
|---|---|
| x^ | |
| e^ | |
| x^ | |
앞의 셋은 한 번도 어기지 않고 뒤의 셋은 절반쯤 어깁니다.
과 가 약 번, 즉 절반인 것은 구간의 절반에서 아래로 볼록하고 절반에서 위로 볼록하기 때문입니다.
이 문제에서 배우는 것: 볼록함수.
볼록함수. 볼록집합 에서 정의된 가 볼록하다 함은 모든 와 에 대해
인 것입니다. 부등호가 이고 에서 엄격하면 엄밀볼록이라 합니다.
정의역이 볼록해야 한다는 조건을 잊기 쉽습니다. 왼쪽의 가 정의역 안에 있어야 식이 말이 되기 때문입니다.
두 가지 동치 관점이 있습니다.
| 관점 | 진술 |
|---|---|
| 부등식 | 현이 함수 위에 있습니다 |
| 집합 | 상위그래프가 볼록집합입니다 |
상위그래프.
둘째 관점이 이론적으로 편합니다. 함수의 볼록성을 집합의 볼록성으로 바꾸면 문제 1의 도구가 그대로 쓰입니다. 예를 들어 볼록함수들의 상한이 볼록한 것은 상위그래프의 교집합이 볼록하기 때문입니다.
볼록성을 보존하는 연산을 정리합니다.
| 연산 | 보존 |
|---|---|
| 양수 배 | 보존합니다 |
| 합 | 보존합니다 |
| 최대 | 보존합니다 |
| 아핀 합성 | 보존합니다 |
| 최소 | 보존하지 않습니다 |
| 곱 | 보존하지 않습니다 |
이 표가 실무의 도구입니다. 손실함수가 볼록한지 확인할 때 처음부터 정의로 돌아가지 않고, 볼록한 조각들이 보존 연산으로 조립되었는지를 봅니다.
최소제곱은 아핀 합성이고 은 볼록함수의 합이며 둘의 합이라 볼록합니다. 116강의 라소가 볼록 문제인 근거가 이것입니다.
바로 확인 2.
확인 2-1. 볼록함수의 정의를 쓰세요.
답. 함숫값이 언제나 현보다 아래에 있는 것입니다.
확인 2-2. 상위그래프로 표현하세요.
답. 가 볼록집합인 것입니다.
확인 2-3. 는 볼록합니까?
답. 대개 아닙니다.
문제. 과 점 을 봅니다.
(1) 에서의 접선을 구하세요.
(2) 여러 에서 와 접선의 값을 비교하세요.
(3) 일반적인 판정 조건을 추측하세요.
생각의 실마리. 문제 2에서 현이 위에 있으면 볼록이라 했습니다. 미분가능하면 접선이 아래에 있을 것입니다.
풀이. (1) , 이므로 접선은 입니다.
(2) 검산에서
| 접선 | 접선 | ||
|---|---|---|---|
어디서나 접선이고 접점에서만 같습니다.
(3) 일반적으로
이 문제에서 배우는 것: 일차 조건.
일차 조건. 가 볼록집합 에서 미분가능하면
입니다.
**"일차 근사가 언제나 과소평가한다"**는 뜻입니다. 95강에서 접평면이 국소적으로만 좋은 근사라 했는데, 볼록함수에서는 그 접평면이 전역적인 하한이 됩니다.
이것이 볼록성의 힘입니다. 한 점에서 기울기를 재면 함수 전체에 대한 부등식을 얻습니다.
곧바로 따름정리가 나옵니다.
따름정리. 가 볼록이고 이면 는 전역 최소입니다.
증명. 일차 조건에 을 넣으면 모든 에 대해
입니다.
한 줄입니다. 101강에서 임계점을 찾은 뒤 분류가 필요했는데, 볼록함수에서는 분류가 필요 없습니다. 임계점이면 곧 전역 최소입니다.
바로 확인 3.
확인 3-1. 일차 조건을 쓰세요.
답. 입니다.
확인 3-2. 그 기하적 뜻을 쓰세요.
답. 접평면이 언제나 함수 아래에 있습니다.
확인 3-3. 볼록함수의 임계점은 무엇입니까?
답. 전역 최소입니다.
문제. 다음 함수들의 헤세를 구하고 고유값으로 볼록성을 판정하세요.
(1)
(2)
(3)
(4)
생각의 실마리. 99강에서 가 방향별 휘어짐이라 했습니다. 모든 방향으로 위로 휘면 볼록할 것입니다.
풀이. 검산에서
| 함수 | 헤세 | 고유값 | 볼록 |
|---|---|---|---|
| x^{2}+y^ | 예 | ||
| x^{2}-y^ | 아니오 | ||
| x^{2}+2xy+y^ | 예 | ||
| 예 |
셋째 줄이 흥미롭습니다. 고유값에 이 있어 준정치인데 볼록합니다. 실제로 이며, 직선 위에서 값이 으로 평평합니다.
이 문제에서 배우는 것: 이차 조건.
이차 조건. 가 열린 볼록집합에서 이면
입니다. 여기서 은 준정치, 즉 모든 고유값이 음이 아님을 뜻합니다.
101강의 판정과 비교하면 차이가 분명합니다.
| 판정 | 어디서 | 조건 |
|---|---|---|
| 극값 (101강) | 한 점 | 그 점에서 정치 |
| 볼록 (107강) | 모든 점 | 어디서나 준정치 |
"모든 점"이 결정적입니다. 한 점에서만 양정치이면 그 점 근방에서만 그릇 모양이고, 멀리 가면 다시 내려갈 수 있습니다. 어디서나 준정치이면 그런 일이 없습니다.
정치와 준정치의 구별도 짚어 둡니다.
| 헤세 | 함수 |
|---|---|
| 어디서나 (정치) | 엄밀볼록 |
| 어디서나 (준정치) | 볼록 |
| 어디서나 () | -강볼록 |
셋째 줄이 108강의 주제이며, 110강의 수렴 속도를 정합니다. 101강 문제 2에서 얻은 부등식
이 그 형태였습니다.
주의할 점이 하나 있습니다. 이차 조건은 일 때만 쓸 수 있습니다. 는 볼록한데 원점에서 미분불가능이라 헤세가 없습니다. 볼록성은 미분가능성보다 약한 조건이며, 정의(문제 2)가 가장 넓게 적용됩니다.
바로 확인 4.
확인 4-1. 이차 조건을 쓰세요.
답. 모든 점에서 헤세가 준정치인 것입니다.
확인 4-2. 101강의 극값 판정과 무엇이 다릅니까?
답. 한 점이 아니라 모든 점에서의 조건입니다.
확인 4-3. 에 이차 조건을 쓸 수 있습니까?
답. 없습니다. 원점에서 미분불가능이라 헤세가 정의되지 않습니다.
문제. 여러 시작점에서 경사하강법을 돌립니다.
(1) 볼록함수 에서 세 시작점을 씁니다.
(2) 비볼록함수 에서 세 시작점을 씁니다.
(3) 결과를 비교하세요.
생각의 실마리. 볼록이면 어디서 출발하든 같은 곳에 도착해야 합니다.
풀이. (1) 검산에서
| 시작 | 도달 |
|---|---|
모두 원점에 도착합니다.
(2) 검산에서
| 시작 | 도달 | |
|---|---|---|
두 곳으로 갈라지고 값도 다릅니다.
(3) 볼록이면 시작점이 결과를 바꾸지 않고, 비볼록이면 바꿉니다.
이 문제에서 배우는 것: 국소 최소가 전역 최소입니다.
정리. 가 볼록집합 에서 볼록이면 모든 국소 최소가 전역 최소입니다.
증명. 가 국소 최소라 하고 어떤 에 대해 라 가정합니다. 에 대해 볼록결합을 잡으면 가 볼록하므로
이고 볼록성에서
를 아무리 작게 해도 이 부등식이 성립합니다. 이면 이므로, 의 아무리 작은 근방에도 가 더 작은 점이 있습니다. 이는 가 국소 최소라는 가정에 어긋납니다.
증명의 핵심이 "를 작게 해도"에 있습니다. 더 낮은 점이 아무리 멀리 있어도, 그쪽으로 조금만 가면 이미 값이 낮아집니다. 볼록성이 먼 곳의 정보를 가까이로 끌어옵니다.
비볼록함수에서 무슨 일이 생기는지를 검산이 보입니다. 의 두 극소는
| 위치 | 성격 | |
|---|---|---|
| 전역 최소 | ||
| 국소 최소 |
에서 출발하면 나쁜 쪽으로 갑니다. 값이 만큼 나쁘고, 그 사실을 알 방법이 없습니다. 도달한 점만 보면 기울기가 이고 헤세가 양정치라 완벽한 최소로 보입니다.
실무의 대응을 정리합니다.
| 상황 | 대응 |
|---|---|
| 볼록입니다 | 아무 데서나 시작합니다 |
| 비볼록이고 작습니다 | 여러 시작점에서 반복합니다 |
| 비볼록이고 큽니다 | 좋은 국소 최소로 만족합니다 |
셋째 줄이 신경망입니다. 손실이 볼록하지 않고 파라미터가 수백만 개라 전역 최소를 목표로 삼지 않습니다. 다만 101강 문제 5에서 본 대로 고차원에서는 대부분의 국소 최소가 비슷하게 좋다는 관찰이 있어, 실무적으로는 큰 문제가 되지 않습니다.
바로 확인 5.
확인 5-1. 볼록함수의 국소 최소는 무엇입니까?
답. 전역 최소입니다.
확인 5-2. 증명의 핵심 발상을 쓰세요.
답. 더 낮은 점 쪽으로 조금만 가도 값이 낮아지므로 국소 최소일 수 없습니다.
확인 5-3. 비볼록에서 시작점이 왜 중요합니까?
답. 어느 국소 최소로 갈지가 정해지고 값이 다를 수 있기 때문입니다.
| 개념 | 정의 |
|---|---|
| 볼록집합 | 두 점을 잇는 선분이 안에 있습니다 |
| 볼록함수 | |
| 상위그래프 | 가 볼록집합입니다 |
| 일차 조건 | 접평면이 아래에 있습니다 |
| 이차 조건 | 모든 점에서 입니다 |
| 보존하는 연산 | 집합 | 함수 |
|---|---|---|
| 교집합 | 보존 | |
| 합집합 | 보존 안 함 | |
| 아핀상 | 보존 | |
| 양수 배와 합 | 보존 | |
| 최대 | 보존 | |
| 최소와 곱 | 보존 안 함 |
| 볼록성의 결과 | |
|---|---|
| 국소 최소 | 전역 최소입니다 |
| \nabla f=\mathbf | 최적성의 필요충분조건 |
| 최소점의 집합 | 볼록집합입니다 |
| 엄밀볼록 | 최소가 많아야 하나입니다 |
| 자주 하는 실수 | 바로잡기 |
|---|---|
| 정의역의 볼록성을 잊습니다 | 조건에 포함됩니다 |
| 한 점의 헤세로 판정합니다 | 모든 점에서 봐야 합니다 |
| 미분가능해야 볼록이라 봅니다 | 가 반례입니다 |
| 합집합을 볼록이라 봅니다 | 교집합만 보존합니다 |
문제 6. 반공간 가 볼록임을 보이세요.
답. 입니다.
문제 7. 로 정의된 집합이 볼록한 이유를 쓰세요.
답. 반공간들의 교집합이고 교집합이 볼록성을 보존하기 때문입니다.
문제 8. 구면이 볼록하지 않은 이유를 쓰세요.
답. 두 점을 잇는 선분이 내부를 지나 구면을 벗어나기 때문입니다.
문제 9. 가 볼록임을 이차 조건으로 보이세요.
답. 이므로 볼록이며 엄밀볼록입니다.
문제 10. 이 에서 볼록합니까?
답. 아닙니다. 가 음수인 구간이 있습니다. 에서는 볼록합니다.
문제 11. 가 볼록임을 삼각부등식으로 보이세요.
답. 이며 삼각부등식과 동차성에서 나옵니다.
문제 12. 이 볼록임을 보이세요.
답. 헤세가 이므로 볼록합니다.
문제 13. 가 볼록이면 도 볼록합니까?
답. 아닙니다. 두 직선의 최소를 생각하면 꺾인 위로 볼록한 함수가 됩니다.
문제 14. 볼록함수의 최소점 집합은 어떤 집합입니까?
답. 볼록집합입니다. 최솟값의 하위준위집합이기 때문입니다.
문제 15. 엄밀볼록이면 최소가 몇 개입니까?
답. 많아야 하나입니다.
문제 16. 의 최소점 집합을 구하세요.
답. 이므로 직선 전체입니다.
문제 17. 볼록함수의 하위준위집합 는 볼록합니까?
답. 볼록합니다. 정의에서 바로 나옵니다.
문제 18. 하위준위집합이 모두 볼록하면 함수가 볼록합니까?
답. 아닙니다. 그런 함수를 준볼록이라 하며 가 예입니다.
심화 1. 일차 조건을 증명하세요.
() 볼록이면 접평면이 아래에 있습니다.
볼록성의 정의를 다시 씁니다. 에 대해
좌변에서 를 빼고 로 나누면
왼쪽이 방향도함수의 차분비입니다. 을 취하면 96강의 결과로
이며 정리하면 일차 조건입니다.
() 접평면이 아래에 있으면 볼록입니다.
라 두고 를 기준점으로 삼아 조건을 두 번 씁니다.
첫 식에 를, 둘째에 를 곱해 더하면
**괄호 안이 정확히 **입니다. 의 정의가 그것이기 때문입니다. 따라서
역방향 증명의 요령이 기준점 선택에 있습니다. 두 끝점이 아니라 가운데 점을 기준으로 잡아야 마지막에 상쇄가 일어납니다.
이차 조건도 같은 방식으로 일차 조건에서 유도됩니다. 100강의 테일러 정리로
이므로, 이면 마지막 항이 음이 아니어서 일차 조건이 성립합니다. 역방향은 가 어떤 점에서 부정부호이면 그 방향으로 일차 조건이 깨짐을 보입니다.
심화 2. 젠센 부등식을 세우고 쓰임을 보이세요.
볼록성의 정의는 두 점에 대한 것입니다. 여러 점으로 확장됩니다.
젠센 부등식(유한형). 가 볼록이고 , 이면
증명은 귀납법입니다. 가 정의이고, 개에서 개로 갈 때 앞의 개를 하나로 묶습니다.
확률로 쓰면 더 강력합니다.
젠센 부등식(확률형). 가 볼록이고 가 적분가능하면
증명이 일차 조건에서 한 줄입니다. 로 두면
양변에 기댓값을 취하면 오른쪽 둘째 항이 이 되어
**"평균의 함숫값이 함숫값의 평균보다 작다"**는 뜻이며, 이 부등식이 여러 곳에서 결정적입니다.
| 쓰임 | 형태 | 강의 |
|---|---|---|
| 산술-기하 평균 | \sqrt[n]{\prod x_{i}}\le\frac1n\sum x_ | 13강 |
| KL 발산이 음이 아님 | 가 볼록 | 203강 |
| 변분 하한 | 262강 | |
| 정보 부등식 | 상호정보량이 음이 아님 | 202강 |
셋째 줄이 생성모형의 핵심입니다. 로그가능도를 직접 계산할 수 없을 때
가 오목이라 부등호가 이 방향이고, 오른쪽을 증거 하한(ELBO)이라 합니다. 262강의 변분오토인코더와 268강의 확산 손실이 모두 이 하한을 최대화합니다.
심화 3. 볼록성이 실무에서 어디까지 성립하는지 정리하세요.
볼록인 문제들을 먼저 봅니다.
| 문제 | 볼록인 이유 |
|---|---|
| 최소제곱 | 헤세 |
| 능형회귀 | 볼록 + 볼록 |
| 라소 | 볼록 + \ell^ |
| 로지스틱 회귀 | 로그가능도가 오목 |
| 서포트 벡터 머신 | 힌지 손실이 볼록 |
| 선형계획법 | 선형 목적, 다면체 제약 |
여섯 문제가 모두 볼록이고, 전역 최적해를 보장할 수 있습니다. 153강과 214강에서 다룹니다.
비볼록인 문제들은 이렇습니다.
| 문제 | 비볼록인 이유 |
|---|---|
| 신경망 학습 | 층의 합성이 볼록성을 깨뜨립니다 |
| 행렬 인수분해 | 가 곱이라 비볼록 |
| 군집화 | 이산적 배정이 섞입니다 |
| 강화학습 | 정책과 가치가 얽힙니다 |
첫째 줄의 이유가 중요합니다. 볼록함수의 합성이 볼록일 조건은
신경망은 이 조건을 만족하지 않습니다. 활성화 함수가 비감소여도 가중치가 음수일 수 있고, 그러면 가 볼록이어도 가 되어 오목해집니다. 층을 하나만 쌓아도 볼록성이 깨집니다.
그런데 실무는 비볼록으로도 잘 작동합니다. 이유가 몇 가지 제시됩니다.
| 관찰 | 내용 |
|---|---|
| 고차원에서 안장이 많습니다 | 나쁜 극소가 드뭅니다(101강) |
| 과다 파라미터화 | 많은 최소가 비슷하게 좋습니다 |
| 국소적으로는 볼록 | 최소 근처에서 이차 근사가 통합니다 |
셋째 줄이 이 단원의 실용적 근거입니다. 전역적으로 볼록하지 않아도 최소 근처에서는 볼록처럼 행동하므로, 볼록 최적화의 수렴 이론이 국소적으로 적용됩니다. 110강의 수렴 해석이 그런 형태입니다.
심화 4. 볼록집합의 분리 정리를 소개하고 쓰임을 예고하세요.
볼록집합의 가장 중요한 성질 중 하나입니다.
분리 초평면 정리. 와 가 서로소인 볼록집합이면, 이들을 분리하는 초평면이 존재합니다. 즉 과 가 있어
입니다.
볼록성이 필수입니다. 두 집합 중 하나라도 볼록하지 않으면 성립하지 않습니다. 예를 들어 원과 그 중심점은 서로소이지만 직선으로 분리되지 않습니다.
따름정리가 실용적입니다.
지지 초평면 정리. 볼록집합의 경계점마다 그 점에서 집합을 한쪽에 두는 초평면이 있습니다.
일차 조건이 이 정리의 함수판입니다. 상위그래프의 경계점 에서 지지 초평면을 잡으면 그것이 접평면이고, 집합이 한쪽에 있다는 말이 곧 접평면입니다.
뒤에서 쓰이는 자리를 적어 둡니다.
| 쓰임 | 내용 | 강의 |
|---|---|---|
| 쌍대성 | 강쌍대성의 증명 도구 | 115 |
| KKT 조건 | 제약 최적화의 최적성 | 114 |
| 서포트 벡터 머신 | 최대 여백 분리 | 214 |
| 열등경사 | 미분불가능한 곳의 기울기 | 111 |
셋째 줄이 이름의 유래입니다. 두 부류의 데이터가 선형분리 가능하면 분리 초평면이 존재하고, 그중 여백이 최대인 것을 고르는 것이 서포트 벡터 머신입니다.
넷째 줄도 중요합니다. 처럼 꺾인 볼록함수는 원점에서 접선이 없지만 지지 직선은 여럿 있습니다. 기울기가 인 모든 직선이 아래에 놓입니다.
이 집합을 열등미분이라 하고 원소를 열등경사라 합니다. 미분가능하면 하나뿐이고, 꺾인 곳에서는 집합이 됩니다. 116강의 라소가 때문에 꺾이므로 이 도구가 필요합니다.
심화 5. 볼록성과 강볼록성의 정량적 차이를 미리 보세요.
문제 4에서 세 단계를 표로 봤습니다. 각각이 무엇을 보장하는지 정리합니다.
| 조건 | 부등식 | 보장 |
|---|---|---|
| 볼록 | f(\mathbf{x})\ge f(\mathbf{a})+\nabla f\cdot\mathbf | 국소가 전역 |
| 엄밀볼록 | 위 부등식이 엄격 | 최소가 유일 |
| -강볼록 | \ge f(\mathbf{a})+\nabla f\cdot\mathbf{h}+\frac\mu2\lVert\mathbf{h}\rVert^ | 수렴 속도 |
셋째 줄이 정량적입니다. 단순히 "아래에 있다"가 아니라 얼마나 아래에 있는지를 말합니다.
이 부등식에서 두 가지가 곧바로 나옵니다.
첫째, 최적성 간격의 상한입니다. 에서 최소점 까지의 거리가
101강 심화 5에서 본 식이며, 기울기의 크기로 최적점과의 거리를 잽니다.
둘째, 수렴 속도입니다. -강볼록이고 헤세가 -유계이면 경사하강법이 선형 수렴하고 그 비율이
조건수가 다시 나타납니다. 93강 심화 5부터 예고해 온 식이며 110강에서 정식으로 유도합니다.
108강이 이 두 상수를 정확히 정의하고 부등식을 세웁니다.
가 없으면 어떻게 되는지도 짚어 둡니다. 볼록이지만 강볼록이 아니면 골짜기가 평평할 수 있고, 그러면 기울기가 작아도 최소가 멀 수 있습니다. 문제 4의 이 그런 예로, 직선 위에서 완전히 평평합니다.
| 함수 | 볼록 | 강볼록 | 최소 |
|---|---|---|---|
| x^{2}+y^ | 예 | 예 | 유일 |
| (x+y)^ | 예 | 아니오 | 직선 전체 |
| e^ | 예 | 아니오 | 없습니다 |
셋째 줄이 중요합니다. 볼록이어도 최소가 존재하지 않을 수 있습니다. 는 아래로 유계이지만 하한 에 도달하지 못합니다.
심화 6. 04단원의 구조를 예고하세요.
이 강의에서 볼록성을 정의하고 국소가 전역이 되는 이유를 밝혔습니다. 04단원의 나머지가 하는 일을 정리합니다.
| 강의 | 하는 일 | 이 강의와의 관계 |
|---|---|---|
| 108 | 판정법과 부등식을 세웁니다 | 정량화 |
| 109 | 경사하강법을 세웁니다 | 알고리즘 |
| 110 | 수렴 속도를 유도합니다 | 108의 부등식 사용 |
| 111 | 모멘텀과 적응적 방법 | 110의 한계 극복 |
| 112 | 뉴턴법과 이차 방법 | 02단원의 헤세 사용 |
108강이 상수 둘을 정합니다.
**아래에서 받치는 와 위에서 누르는 **이며, 이 둘이 110강의 수렴 정리를 만듭니다. 99강 심화 5에서 이미 본 대로 가 학습률의 상한을 정하고, 가 속도를 정합니다.
109강이 알고리즘을 세웁니다. 96강에서 가 최급강하 방향임을 증명했고, 109강이 그것을 반복합니다.
110강이 이 반복이 왜 수렴하는지 증명합니다. 이 단원의 이론적 정점이며, 108강의 부등식 두 개가 정확히 필요한 재료입니다.
111강과 112강이 개선합니다. 96강 심화 3에서 예고한 대로, 가 순간적으로는 최선이어도 목적지를 향하지 않습니다. 조건수가 크면 지그재그로 갑니다.
| 방법 | 어떻게 고치나 |
|---|---|
| 모멘텀 | 과거 방향을 누적합니다 |
| Adam | 성분마다 척도를 조정합니다 |
| 뉴턴법 | 헤세로 좌표를 바꿉니다 |
세 방법이 96강 심화 3의 틀에서 같은 것입니다. 어떤 노름으로 "가장 가파름"을 재느냐의 선택이며, 그 관점이 04단원 전체를 하나로 묶습니다.
import numpy as np
# --- 문제 1: 볼록집합인지 판정 ------------------------------------------
def seg_in(S, n=200000, rng=None):
"""S 안의 두 점을 무작위로 뽑아 선분이 S 안에 있는지 확인"""
rng = rng or np.random.default_rng(20260809)
cnt = 0; tot = 0
while tot < n:
P = rng.uniform(-2, 2, (4096, 2))
ok = S(P)
pts = P[ok]
if len(pts) < 2: continue
k = (len(pts)//2)*2
a, b = pts[:k:2], pts[1:k:2]
t = rng.random((len(a), 1))
mid = t*a + (1-t)*b
cnt += int(S(mid).sum()); tot += len(a)
return cnt/tot
rng = np.random.default_rng(20260809)
sets = [("원판 x^2+y^2<=1 ", lambda P: (P**2).sum(1) <= 1),
("고리 0.5<=r<=1 ", lambda P: (0.25 <= (P**2).sum(1)) & ((P**2).sum(1) <= 1)),
("반평면 x+y<=1 ", lambda P: P.sum(1) <= 1),
("두 원판의 합집합 ", lambda P: (((P-[-1,0])**2).sum(1) <= 0.36) | (((P-[1,0])**2).sum(1) <= 0.36)),
("정사각형 |x|,|y|<=1 ", lambda P: (np.abs(P) <= 1).all(1))]
print(" 집합 선분이 안에 있을 비율")
for name, S in sets:
print(" %s %.4f" % (name, seg_in(S, 100000, rng)))
# 집합 선분이 안에 있을 비율
# 원판 x^2+y^2<=1 1.0000
# 고리 0.5<=r<=1 0.7364
# 반평면 x+y<=1 1.0000
# 두 원판의 합집합 0.7593
# 정사각형 |x|,|y|<=1 1.0000
# 고리는 구멍을 가로지르고 합집합은 사이의 빈 곳을 지납니다.
# --- 문제 2: 볼록함수의 정의 확인 ---------------------------------------
print(" 함수 f(t a+(1-t)b) <= t f(a)+(1-t) f(b) 위반 횟수 / 200000")
fs = [("x^2 ", lambda x: x**2),
("|x| ", lambda x: np.abs(x)),
("e^x ", lambda x: np.exp(x)),
("-log(x) ", lambda x: -np.log(np.abs(x) + 0.1)),
("x^3 ", lambda x: x**3),
("sin(x) ", lambda x: np.sin(x))]
a = rng.uniform(-2, 2, 200000); b = rng.uniform(-2, 2, 200000); t = rng.random(200000)
for name, f in fs:
lhs = f(t*a + (1-t)*b); rhs = t*f(a) + (1-t)*f(b)
print(" %s %8d" % (name, int((lhs > rhs + 1e-12).sum())))
# 함수 f(t a+(1-t)b) <= t f(a)+(1-t) f(b) 위반 횟수 / 200000
# x^2 0
# |x| 0
# e^x 0
# -log(x) 85771
# x^3 100147
# sin(x) 99843
# 뒤의 셋이 절반쯤 위반하는 것은 구간의 절반에서 위로 볼록하기 때문입니다.
# --- 문제 3: 일차 조건 (접선이 아래에 있다) -----------------------------
print(" f = x^2 의 a=1 에서 접선 f(a)+f'(a)(x-a) = 2x-1")
print(" x f(x) 접선 f - 접선")
for x in [-1.0, 0.0, 0.5, 1.0, 2.0]:
print(" %5.1f %8.4f %8.4f %+8.4f" % (x, x**2, 2*x-1, x**2 - (2*x-1)))
# f = x^2 의 a=1 에서 접선 f(a)+f'(a)(x-a) = 2x-1
# x f(x) 접선 f - 접선
# -1.0 1.0000 -3.0000 +4.0000
# 0.0 0.0000 -1.0000 +1.0000
# 0.5 0.2500 0.0000 +0.2500
# 1.0 1.0000 1.0000 +0.0000
# 2.0 4.0000 3.0000 +1.0000
# 어디서나 f >= 접선이고 접점에서만 같습니다.
# --- 문제 4: 이차 조건 (헤세가 준정치) ----------------------------------
print(" 함수 헤세 고유값 볼록")
cases = [("x^2+y^2 ", np.array([[2.,0.],[0.,2.]])),
("x^2-y^2 ", np.array([[2.,0.],[0.,-2.]])),
("x^2+2xy+y^2 ", np.array([[2.,2.],[2.,2.]])),
("(x^2+100y^2)/2", np.array([[1.,0.],[0.,100.]]))]
for name, H in cases:
w = np.linalg.eigvalsh(H)
hs = "[[%g, %g], [%g, %g]]" % (H[0,0], H[0,1], H[1,0], H[1,1])
print(" %s %-20s %-14s %s" % (name, hs, np.array2string(np.round(w, 2)),
"예" if (w >= -1e-12).all() else "아니오"))
# 함수 헤세 고유값 볼록
# x^2+y^2 [[2, 0], [0, 2]] [2. 2.] 예
# x^2-y^2 [[2, 0], [0, -2]] [-2. 2.] 아니오
# x^2+2xy+y^2 [[2, 2], [2, 2]] [0. 4.] 예
# (x^2+100y^2)/2 [[1, 0], [0, 100]] [ 1. 100.] 예
# 셋째는 고유값에 0 이 있어 준정치이며 볼록하되 엄밀볼록은 아닙니다.
# --- 문제 5: 국소 최소가 전역 최소 --------------------------------------
print(" 볼록: f = (x^2+100y^2)/2 를 여러 시작점에서 경사하강")
Hq = np.array([[1.0, 0.0], [0.0, 100.0]])
for x0 in [np.array([5.0, 3.0]), np.array([-2.0, -7.0]), np.array([10.0, 0.1])]:
x = x0.copy()
for _ in range(4000): x = x - 0.019*(Hq @ x)
print(" 시작 %s -> 도달 %s" % (np.round(x0, 1), np.round(x, 6) + 0.0))
print(" 비볼록: f = x^4 - 4x^2 + 0.3x 는 극소가 둘")
fn = lambda x: x**4 - 4*x**2 + 0.3*x
dfn = lambda x: 4*x**3 - 8*x + 0.3
for x0 in [-2.0, 0.5, 2.0]:
x = x0
for _ in range(20000): x = x - 0.005*dfn(x)
print(" 시작 %+.1f -> 도달 %+.6f, f = %+.6f" % (x0, x, fn(x)))
# 볼록: f = (x^2+100y^2)/2 를 여러 시작점에서 경사하강
# 시작 [5. 3.] -> 도달 [0. 0.]
# 시작 [-2. -7.] -> 도달 [0. 0.]
# 시작 [10. 0.1] -> 도달 [0. 0.]
# 비볼록: f = x^4 - 4x^2 + 0.3x 는 극소가 둘
# 시작 -2.0 -> 도달 -1.432603, f = -4.427040
# 시작 +0.5 -> 도달 +1.395077, f = -3.578587
# 시작 +2.0 -> 도달 +1.395077, f = -3.578587
# 볼록이면 시작점이 결과를 바꾸지 않고 비볼록이면 바꿉니다. 값이 0.85 만큼 다릅니다.
문제 5가 이 강의의 요지입니다. 볼록하면 어디서 출발하든 같은 곳에 도착하고, 비볼록하면 시작점이 운명을 가릅니다.
108강에서 이 성질을 정량화합니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| t\mathbf{a}+(1-t)\mathbf | 볼록결합 | 두 점을 잇는 선분입니다 |
| 상위그래프 | 그래프 위쪽 영역입니다 | |
| 준정치 | 모든 고유값이 음이 아닙니다 | |
| 정치 | 모든 고유값이 양수입니다 | |
| 엄밀볼록 | strictly convex | 부등호가 엄격합니다 |
| -강볼록 | strongly convex | 입니다 |
| 젠센 부등식 | Jensen | 입니다 |
| 열등미분 | 지지 기울기의 집합입니다 | |
| 분리 초평면 | separating hyperplane | 서로소 볼록집합을 가릅니다 |
다음 108강에서는 볼록성 판정과 부등식을 다룹니다. 이 강의의 정성적 성질을 정량화해 두 상수 와 을 정하고, 그것이 만드는 부등식들을 세웁니다. **아래에서 받치는 와 위에서 누르는 **이 110강 수렴 정리의 재료가 되며, 그 비 가 93강 심화 5부터 예고해 온 조건수입니다.