이 강의의 목표는 가장 좋은 값을 찾는 문제에서 볼록성과 제약조건을 읽는 법을 아주 기초부터 이해하는 것입니다.
먼저 오늘의 핵심 식을 봅니다.
∇f(x)+λ∇g(x)=0
이 식을 외우기 전에, 식 안의 말과 기호를 먼저 하나씩 풀어야 합니다.
| 기호 |
읽는 법 |
뜻 |
| f(x) |
목적함수 f |
가장 작게(또는 크게) 만들고 싶은 함수 |
| g(x)=0 |
제약함수 g |
답이 반드시 지켜야 하는 조건 |
| ∇f |
f의 그래디언트 |
f가 가장 빨리 커지는 방향을 가리키는 벡터 |
| λ |
람다 |
제약의 영향을 나타내는 라그랑주 승수(숫자) |
| λ∇g |
람다 곱하기 ∇g |
제약이 답을 미는 방향과 세기 |
수학에서 어려운 부분은 계산보다 읽기입니다. 뜻을 모르고 계산하면 공식이 암호처럼 보입니다.
그릇 모양의 산이라면 아래로 내려가면 바닥 하나에 도착합니다. 하지만 울퉁불퉁한 지형에서는 작은 골짜기에 갇힐 수 있습니다. 볼록성은 지형을 하나의 그릇으로 만들어 최적화를 쉽게 만드는 성질입니다.
핵심 식을 다시 봅니다.
∇f(x)+λ∇g(x)=0
이 식은 제약 g(x)=0을 지키면서 f(x)를 가장 작게 만드는 점에서 성립합니다. 기호를 하나씩 대입해 읽어 봅니다.
- ∇f(x): 지금 위치에서 f가 가장 빨리 커지는 방향입니다. 우리는 f를 줄이고 싶으므로, 줄이는 방향은 그 반대인 −∇f(x)입니다.
- ∇g(x): 제약면 g(x)=0에 수직인 방향입니다. 이 방향으로 움직이면 제약을 벗어납니다. 반대로 이 방향에 직각인 방향으로 움직이면 제약면 위에 그대로 남습니다.
- 식을 옮기면 ∇f(x)=−λ∇g(x)입니다. 이것은 "f가 커지는 방향이 제약면의 수직 방향과 나란하다"는 뜻입니다.
- λ는 두 벡터의 길이를 맞춰 주는 비례 상수입니다. f의 기울기가 세면 λ도 커집니다.
즉 이 식은 "제약면 위에서는 더 이상 f를 줄일 방향이 남아 있지 않다"는 상태를 기호로 적은 것입니다.
제약이 없는 문제에서는 답을 찾기 쉽습니다. 기울기가 0인 곳, 즉 ∇f(x)=0인 곳이 후보입니다. 바닥이 평평한 지점이기 때문입니다.
그런데 현실 문제에는 조건이 붙습니다. "예산은 100을 넘지 마라", "확률의 합은 1이어야 한다" 같은 제약입니다. 이때는 ∇f=0인 진짜 바닥이 허용 범위 밖에 있을 수 있습니다. 그러면 답은 허용 범위의 경계, 즉 제약면 위에서 f가 가장 작아지는 점이 됩니다.
경계 위에서는 기울기가 0이 아닐 수 있습니다. 대신 다른 조건이 필요합니다. 제약면을 따라 어느 쪽으로 움직여도 f가 더 줄지 않아야 합니다. 이 조건을 정리한 것이 바로 라그랑주 정상조건입니다. 그래서 라그랑주 승수는 제약이 있는 최적화를 다루기 위한 필수 도구입니다.
제약면 g(x)=0 위의 어떤 점에 서 있다고 합시다. 이 점이 제약을 지키는 최소점이 되려면, 제약면을 따라 살짝 움직였을 때 f가 줄지 않아야 합니다.
제약면을 따라 움직이는 방향을 d라고 하면, d는 제약을 유지해야 하므로 ∇g와 직각입니다.
∇g(x)Td=0
이 방향으로 조금 움직였을 때 f의 변화는 1차 근사로 다음과 같습니다.
f(x+d)−f(x)≈∇f(x)Td
최소점이라면 어느 방향 d로 가도 f가 줄지 않아야 하므로
∇f(x)Td=0
이어야 합니다. 정리하면, ∇g와 직각인 모든 방향 d에 대해 ∇f도 직각입니다. 두 벡터가 같은 방향들과 모두 직각이라는 말은, ∇f가 ∇g와 나란하다는 뜻입니다. 따라서 어떤 숫자 λ에 대해
∇f(x)=−λ∇g(x)
가 성립하고, 이것을 옮기면 핵심 식
∇f(x)+λ∇g(x)=0
이 됩니다. 이것이 제약 하 정류점에서 라그랑주 조건이 나오는 이유입니다.
볼록함수는 그릇처럼 아래로 오목한 함수입니다. 정확한 정의는 다음과 같습니다. 임의의 두 점 x, y와 0≤λ≤1에 대해
f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)
가 성립하면 f는 볼록함수입니다. 왼쪽은 두 점을 이은 선분 위의 한 점에서 함수값이고, 오른쪽은 그 자리에서 두 함수값을 직선으로 이은 높이입니다. 즉 "함수 그래프가 두 점을 잇는 직선보다 아래에 있다"는 뜻입니다.
예를 들어 f(x)=x2, x=0, y=2, λ=21로 확인해 봅니다.
f(21⋅0+21⋅2)=f(1)=1
21f(0)+21f(2)=21⋅0+21⋅4=2
1≤2이므로 부등식이 성립합니다.
이 성질이 있으면 지역최소가 곧 전역최소가 됩니다. 이유는 이렇습니다. 어떤 점 x⋆가 지역최소인데 전역최소가 아니라고 가정해 봅니다. 그러면 더 낮은 점 y가 어딘가 있어 f(y)<f(x⋆)입니다. 두 점을 잇는 선분 위의 점 z=λx⋆+(1−λ)y를 보면, 볼록성에 의해
f(z)≤λf(x⋆)+(1−λ)f(y)<f(x⋆)
입니다. λ를 1에 가깝게 잡으면 z는 x⋆ 바로 옆인데도 함수값이 x⋆보다 낮습니다. 이것은 x⋆가 지역최소라는 가정과 모순입니다. 따라서 볼록함수에서는 지역최소가 반드시 전역최소입니다. 그래서 볼록 문제는 골짜기에 갇힐 걱정이 없습니다.
문제: 다음을 최소화하라.
f(x1,x2)=x12+x22단g(x1,x2)=x1+x2−1=0
말로 풀면 "x1+x2=1이라는 직선 위에서 원점에 가장 가까운 점을 찾아라"입니다.
먼저 그래디언트를 구합니다.
∇f=[2x12x2],∇g=[11]
라그랑주 조건 ∇f+λ∇g=0을 성분으로 적습니다.
2x1+λ=0,2x2+λ=0
이 두 식에서 x1=−2λ, x2=−2λ이므로 x1=x2입니다. 이제 제약 x1+x2=1에 넣습니다.
x1+x2=2x1=1⇒x1=21,x2=21
따라서 최소점은 (21,21)이고, λ=−2x1=−1입니다. 이때 목적함수 값은
f(21,21)=(21)2+(21)2=41+41=21
입니다. 직선 위에서 원점에 가장 가까운 점이 직선의 정중앙이라는 기하 직관과 정확히 일치합니다.
제약이 없다면 f(x1,x2)=x12+x22의 최소는 원점 (0,0)이고 값은 0입니다. 그러나 x1+x2=1을 지켜야 하면 원점은 허용되지 않고, 답은 (21,21)로 밀려나며 값도 21로 커집니다.
일변수 예로도 확인됩니다. 가장 낮은 곳이 x=2인데 허용 범위가 x≤1이라면, 실제 답은 경계인 x=1입니다. 이렇게 제약조건은 답을 바꿀 수 있고, 그 바뀐 답을 찾는 도구가 라그랑주 조건입니다.
- 볼록함수는 f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)를 만족하는, 그릇 모양 함수입니다.
- 볼록함수에서는 지역최소가 곧 전역최소이므로 골짜기에 갇히지 않습니다.
- 제약이 없으면 ∇f=0인 점을 찾습니다.
- 제약이 있으면 제약면을 따라 f를 더 줄일 수 없다는 조건이 필요합니다.
- 그 조건은 ∇f가 ∇g와 나란해지는 것, 곧 ∇f+λ∇g=0입니다.
- 라그랑주 승수 λ는 제약이 답을 미는 세기를 나타냅니다.
∇f(x)+λ∇g(x)=0
- 볼록함수의 정의 부등식을 쓰고, f(x)=x2로 한 번 확인할 수 있는가?
- 볼록이면 왜 지역최소가 전역최소인지 모순을 이용해 설명할 수 있는가?
- 제약면을 따라가는 방향 d가 왜 ∇g와 직각인지 말할 수 있는가?
- ∇f+λ∇g=0이 왜 "더 줄일 방향이 없다"는 뜻인지 설명할 수 있는가?
- f=x12+x22, x1+x2=1 문제를 직접 풀어 (21,21)을 얻을 수 있는가?