O1 · 비용의 곡률, 허용집합과 좌표의 선택#
1. 두 활동의 총량과 불균형을 함께 줄이기#
두 활동의 실행량 \(x_1,x_2\)를 같은 기준량으로 나누어 무차원으로 기록합니다. 총량은 2에 가깝게, 두 활동의 차이는 0에 가깝게 만들고 싶습니다. 불균형에 더 큰 비용을 주는 모형을
로 정합니다. 비용도 정한 기준비용으로 나눴습니다. 계수 9는 관측된 보편 법칙이 아니라 이 문제에서 정한 상대 벌점입니다. 제약이 없으면 두 제곱이 모두 0인 \(c\)가 최소점입니다.
상태 \(x=(2,0)\)에서는 총량은 맞지만 차이가 2여서 비용이 9입니다. \(x=(0,0)\)에서는 총량이 2만큼 부족하지만 불균형은 없어 비용이 1입니다. 두 상태가 \(c\)에서 같은 거리 \(\sqrt2\)에 있어도 비용은 다릅니다. 거리만으로는 선택 기준을 설명할 수 없습니다.
합 방향 \(q_+=(1,1)^T/\sqrt2\), 차 방향 \(q_-=(1,-1)^T/\sqrt2\)에 \(H\)를 곱하면 각각 \(q_+\), \(9q_-\)가 됩니다. \(x-c=z_+q_++z_-q_-\)로 적으면
비용 1인 곡선은 \(z_+^2/2+z_-^2/(2/9)=1\)입니다. 긴 반축은 \(\sqrt2\), 짧은 반축은 \(\sqrt2/3\)이며 그 비는 3입니다. 헤시안의 조건수는 9이므로 축 길이의 비는 조건수의 제곱근입니다.
그림 116 왼쪽 축은 원래 두 활동량이고 오른쪽은 \(x-c=H^{-1/2}y\)로 바꾼 좌표이다. 각 패널은 자체 좌표에서 같은 가로·세로 길이 눈금을 쓴다. 좌표변환 뒤 같은 비용이 원이 되지만 원래 활동량의 의미까지 같아지는 것은 아니다.#
2. 평균을 취했을 때 비용이 증가하는가#
계획 \(x,y\)를 비율 \(1-t,t\)로 섞을 때 \(0\le t\le1\)이면 중간 계획입니다. 이차식을 직접 전개하면
마지막 부등식은 \(H\succ0\)에서 나옵니다. 중간 계획의 비용은 양 끝 비용을 같은 비율로 평균한 값 이하입니다. 이것을 볼록성이라고 합니다. \(x\ne y\), \(0<t<1\)이면 여기서는 엄격한 부등식입니다.
활동량에 총량 제한 \(x_1+x_2\le1\)과 비음수 조건을 추가하면 \(C=\{x\ge0:x_1+x_2\le1\}\)입니다. 허용계획 두 개의 평균은 각 성분이 비음수이고 합이 1 이하이므로 여전히 허용됩니다. 이 집합도 볼록입니다. 다만 제약 없는 최소점 \((1,1)\)은 허용되지 않습니다.
허용되지 않는 계획의 비용을 \(+\infty\)로 정의하면 제약을 함수에 넣을 수 있습니다. \(x\in C\)이면 \(\delta_C(x)=0\), 그 밖에는 \(+\infty\)로 두고 \(F=f+\delta_C\)를 최소화합니다. 유한값을 갖는 집합이 유효정의역입니다. \(+\infty\)는 큰 유한 벌점이 아니라 허용 불가능이라는 표기입니다.
함수 \(F\) 위쪽에 있는 점들의 집합 \(\operatorname{epi}F=\{(x,t):F(x)\le t\}\)를 에피그래프라 부릅니다. 두 점 위쪽의 선분이 계속 위쪽에 남는다는 조건이 함수의 볼록성과 정확히 같습니다. 함수에 허용집합을 합쳐 다룰 이유가 이 표현에 있습니다.
3. 기울기는 어느 쪽에서 지지하는가#
이번 비용의 기울기는 \(\nabla f(x)=H(x-c)\)입니다. 임의의 변화 \(d\)에 대해 정확히
입니다. 오른쪽은 현재점에서의 일차 근사이고 전역적으로 비용의 아래에 있습니다. 예를 들어 \(x=0\)에서는 \(f(0)=1\), \(\nabla f(0)=(-1,-1)^T\)여서 \(f(y)\ge1-y_1-y_2\)입니다.
볼록 미분가능 함수에서 \(\nabla f(x_*)=0\)이면 이 부등식이 모든 \(y\)에 \(f(y)\ge f(x_*)\)를 주므로 전역 최소점입니다. 제약문제에서는 기울기가 0일 필요가 없습니다. 위 삼각형에서는 \(x_*=(1/2,1/2)\)이고 기울기는 \((-1/2,-1/2)\)입니다. 모든 허용 \(y\)에
이므로 더 낮은 허용계획이 없습니다. 이 방식으로 최소성을 증명하면 그림에서 낮아 보인다는 판단에 의존하지 않습니다.
4. 양의 곡률과 강볼록성을 구별하기#
열린 볼록 영역의 \(C^2\) 함수에서 모든 헤시안이 양의 준정부호이면 함수가 볼록이고, 역도 성립합니다. 모든 헤시안이 양의 정부호이면 엄격볼록이지만, 하나의 양수 \(m\)으로 전 영역의 곡률을 아래에서 제한하는 것은 더 강한 조건입니다.
예를 들어 \(e^t\)의 둘째 미분은 모든 실수에서 양수이지만 \(t\to-\infty\)에서 0에 가까워지므로 실수 전체에서 강볼록이 아닙니다. \(t^4\)도 엄격볼록이지만 원점의 둘째 미분은 0입니다. 따라서 엄격볼록이 양의 정부호 헤시안을 필요로 하지도 않습니다. 반대로 \(m\)-강볼록인 \(C^2\) 함수는 반드시 \(\nabla^2f\succeq mI\succ0\)를 만족합니다.
이면 모든 방향의 곡률이 \(m,L\) 사이입니다. 이번 \(H\)에는 \(m=1\), \(L=9\), \(\kappa=L/m=9\)를 사용할 수 있습니다. 강볼록성은
이며, 최소점이 있으면 유일하고 그 점에서는 \(f(x)-f(x_*)\ge m\|x-x_*\|^2/2\)입니다. 실수 공간 전체의 연속 강볼록 함수는 일차 하한과 양의 이차항 때문에 무한대로 갈수록 값이 커져 최소점도 존재합니다. 열린 제한 영역에서는 강볼록성만으로 달성을 보장하지 않습니다. \((0,\infty)\)의 \(t^2\)는 하한 0을 달성하지 않습니다.
그림 117 각 패널은 표시 구간에서의 둘째 미분이다. \(e^t\)의 강볼록성 실패는 표시 구간 밖 \(t\to-\infty\)의 극한으로 판단한다. 그림의 양수만 보고 실수 전체의 양의 하한을 결론내리지 않는다.#
평활성은 기울기의 변화가 \(\|\nabla f(y)-\nabla f(x)\|\le L\|y-x\|\)라는 조건입니다. 일반 \(C^2\) 함수에는 \(\|\nabla^2f\|_2\le L\), 즉 \(-LI\preceq\nabla^2f\preceq LI\)가 대응합니다. 헤시안의 위쪽 상한만으로 충분한 것은 볼록성으로 아래쪽이 0 이상임을 함께 알고 있을 때입니다. \(f(t)=-100t^2\)는 위쪽 이차 부등식을 \(L=1\)로 만족하지만 기울기는 1-Lipschitz가 아닙니다.
5. 같은 문제도 좌표에 따라 조건수가 달라진다#
\(x=c+By\)로 가역 좌표변환하면 새 헤시안은 \(B^THB\)입니다. 이는 닮음이 아닌 합동변환입니다. 양·음·영 고윳값의 개수는 H7의 관성법칙으로 보존되지만 고윳값 자체는 바뀝니다.
이번에는 \(B=H^{-1/2}=q_+q_+^T+\frac13q_-q_-^T\)로 두면 \(B^THB=I\)입니다. 새 비용은 \(\|y\|^2/2\)이고 조건수는 1입니다. 반면 Jacobi 대각 스케일링은 \(\operatorname{diag}(H)=5I\)여서 \(B=I/\sqrt5\), 새 헤시안 \(H/5\)의 조건수는 여전히 9입니다. 대각 스케일링을 했다는 사실만으로 방향의 불균형이 해결되지는 않습니다.
import numpy as np
import scipy.linalg as la
H = np.array([[5.,-4.],[-4.,5.]])
values, Q = la.eigh(H)
B = (Q*(1/np.sqrt(values)))@Q.T
assert np.allclose(B.T@H@B,np.eye(2))
assert np.isclose(np.linalg.cond(H/5),9)
c = np.ones(2); xstar = np.full(2,.5)
assert np.allclose(H@(xstar-c),[-.5,-.5])
print("원래 곡률:",values,"좌표변환 후:",la.eigvalsh(B.T@H@B))
원래 곡률: [1. 9.] 좌표변환 후: [1. 1.]
직사각 \(B\)라면 같은 관성 개수를 주장할 수 없습니다. 예를 들어 음의 방향을 빼고 양의 방향만 남기는 제한은 부정치 행렬을 양의 정부호로 바꿀 수 있습니다. 또한 \(H=X^TX\)인 최소제곱에서는 완전 열계수 아래 \(\kappa_2(H)=\kappa_2(X)^2\)입니다. 설계행렬의 조건수와 비용 곡률의 조건수를 같은 기호라고 무심코 같게 놓지 않습니다.
6. 변수를 하나 제거하면 Schur 보원이 남는다#
두 제어량 중 \(y\)를 매번 최적으로 조정할 수 있다면 \(g(x)=\inf_y f(x,y)\)를 고려합니다. 예를 들어
최적 \(y=-2x/5\)이고 \(g(x)=3x^2/5\)입니다. 블록 헤시안은 \(\begin{pmatrix}2&2\\2&5\end{pmatrix}\)이므로 남은 곡률은 \(2-2\cdot5^{-1}\cdot2=6/5\)입니다. 교차항 \(4xy\)에서 블록 성분은 4가 아니라 2라는 점을 확인합니다.
일반적으로 \(C\succ0\)일 때
완전제곱으로 \(y_*=-C^{-1}B^Tx\)를 얻습니다. 이는 선형계 소거, 양의 정부호 판정과 같은 Schur 보원입니다.
볼록성을 보존하는 다른 연산도 실제로 쓸 수 있습니다. 비음수 가중합은 비용 합산, 아핀 합성은 단위·좌표변환, 점별 상한은 여러 시나리오 중 최악의 비용에 대응합니다. 예를 들어 \(\max\{(x-1)^2,(x+1)^2\}=(|x|+1)^2\)는 볼록하지만 원점에서 미분가능하지 않습니다. 점별 최솟값은 일반적으로 볼록하지 않습니다.
원근함수 \(g(x,t)=t f(x/t)\) (\(t>0\))도 볼록성을 보존합니다. \(f(z)=\|z\|^2\)이면 \(g(x,t)=\|x\|^2/t\)입니다. 처리량 \(t\)에 비해 큰 총변화 \(x\)를 주는 비용으로 읽을 수 있지만 \(t=0\)을 식에 직접 대입하지 않습니다. 필요하면 하반연속 확장값을 따로 정의합니다.
7. 허용집합에 가장 가까운 점#
계획 \(v=(-1,2)\)가 나왔을 때 비음수 활동만 허용한다면 \(\mathbb R_+^2\)에서 가장 가까운 점은 \((0,2)\)입니다. 각 좌표에서 \((x_i-v_i)^2\)를 \(x_i\ge0\) 아래 최소화하면 \(x_i=\max(v_i,0)\)이기 때문입니다. 이 사영은 선형이 아닙니다. \(P(1,0)=(1,0)\)이지만 \(P(-1,0)=(0,0)\ne-P(1,0)\)입니다.
비어 있지 않은 닫힌 볼록집합 \(C\)에서는 모든 \(v\)에 가장 가까운 점 \(z=P_C(v)\)가 하나 존재하며,
로 특성화됩니다. \(v-z\) 방향으로 더 나아가면 허용집합 밖이라는 이차거리의 일차 조건입니다. \(C\)가 부분공간이면 \(y-z\)와 그 음수가 모두 허용되어 부등식이 등식이 되고 H1의 직교사영으로 돌아갑니다.
그림 118 음영은 비음수 활동의 허용집합이다. 점선은 각 입력에서 최근접점까지의 선분이며 원래 입력과 결과를 다른 표식으로 구별했다. 가로·세로 눈금은 같다.#
사영은 입력 차이를 늘리지 않습니다. 더 강하게 \(p=P_C(v)\), \(q=P_C(w)\)이면 \(\|p-q\|^2\le(v-w)^T(p-q)\)입니다. 다음 장의 분리정리와 O4의 근접연산자가 이 부등식을 사용합니다. 반면 닫힘을 빼면 \((0,1)\)에 대한 0의 최근접점이 없고, 볼록성을 빼면 집합 \(\{-1,1\}\)에 대한 0의 최근접점이 두 개입니다.
8. 조건수에서 반복의 속도로#
이차함수의 고정 보폭 경사법은 \(x_{k+1}=x_k-\alpha H(x_k-c)\)입니다. 오차 \(e_k=x_k-c\)를 고유방향별로 적으면 각 성분에 \(1-\alpha\lambda_i\)가 곱해집니다. \(0<\alpha<2/L\)이면 모든 절댓값이 1 미만입니다. \(\alpha=2/(L+m)\)는 구간 양 끝의 절댓값을 같게 하여 최악 수축률 \((L-m)/(L+m)\)를 줍니다. 이번 예에서는 \(\alpha=1/5\), 두 성분 배율은 \(4/5,-4/5\)입니다.
이 비율은 최악 상한이지 모든 함수·초기점·직선탐색의 실험 기울기를 같게 만드는 법칙은 아닙니다. 좌표를 이상적으로 바꾸면 한 단계로 가는 이차 예와, 일반 비선형 함수에서 매번 달라지는 헤시안도 구별합니다. 정확 직선탐색과 Newton·BFGS·근접법은 O4에서 이어집니다.
9. 연습과 전체 풀이#
1. 이번 비용에서 \((0,0)\)와 \((2,0)\)의 중간점 비용을 구하세요.
풀이. 중간점은 \((1,0)\)이고 비용은 \(1/4+9/4=5/2\)입니다. 끝점 비용 평균은 \((1+9)/2=5\)입니다. 차이 \(5/2\)는 \(t=1/2\), \(y-x=(2,0)\)에서 \(t(1-t)d^THd/2=20/8\)과 같습니다.
2. \(H=\operatorname{diag}(1,16)\)의 비용 2 등고선 반축과 조건수를 구하세요.
풀이. \(\frac12(x_1^2+16x_2^2)=2\)이므로 반축은 2와 \(1/2\)입니다. 길이비는 4이고 조건수는 16입니다.
3. \(t^4\)가 엄격볼록이지만 강볼록이 아님을 설명하세요.
풀이. 도함수 \(4t^3\)는 엄격 증가하므로 서로 다른 두 점 사이 현의 기울기가 양 끝 접선기울기 사이에 엄격히 놓입니다. 따라서 중간점 볼록부등식이 엄격합니다. 강볼록이라면 원점에서 \(t^4\ge mt^2/2\)여야 하는데 비영 \(t\to0\)에서 불가능합니다.
4. \(f(x,y)\)의 부분최소화에서 교차 블록을 4로 쓰면 왜 틀리나요?
풀이. 대칭 이차형식의 비대각 성분 \(b\)는 괄호 안에서 \(2bxy\)를 만듭니다. 원래 괄호의 교차항이 \(4xy\)이므로 \(b=2\)입니다. \(b=4\)이면 다른 함수이며 Schur 보원도 \(2-16/5<0\)으로 바뀝니다.
5. \(C=[0,1]\)에 대한 사영 공식을 구하고 비선형임을 보이세요.
풀이. \(v<0\)에서는 거리제곱이 \(x\)와 함께 증가하여 0, \(0\le v\le1\)에서는 \(v\), \(v>1\)에서는 1입니다. 즉 \(P_C(v)=\min(1,\max(0,v))\)입니다. \(P_C(2)=1\ne2P_C(1)=2\)이므로 선형이 아닙니다.
6. \(f(x)=e^x\)의 \([0,1]\)에서의 곡률 하한과 실수 전체에서의 하한을 비교하세요.
풀이. 구간에서는 \(1\le e^x\le e\)여서 강볼록 상수 1을 쓸 수 있습니다. 실수 전체에서는 양의 하한이 없습니다. 함수식만이 아니라 정의역도 조건의 일부입니다.
7. 이번 비용의 이상적 좌표변환에서 제약 \(x_1+x_2\le1\)이 무엇이 되는지 구하세요.
풀이. \(x=c+By\)이고 \((1,1)B=(1,1)\)이므로 \(2+y_1+y_2\le1\), 즉 \(y_1+y_2\le-1\)입니다. 비용이 원형으로 바뀌어도 제약을 원래 식으로 남겨 두면 다른 문제를 풉니다. 비음수 조건도 \(c+By\ge0\)으로 함께 바꿔야 합니다.
10. 지금까지의 내용을 수학의 언어로 정리해 봅시다#
이 장에서는 유한차원 실 공간을 사용합니다. 미분 판정의 영역은 열린 볼록집합이며, 최소점 존재를 말할 때에는 정의역과 닫힘을 별도로 확인합니다.
정의와 정리 1. 볼록성, 에피그래프와 일차 판정#
함수 \(f:\mathbb R^n\to\mathbb R\cup\{+\infty\}\)는 \(f((1-t)x+ty)\le(1-t)f(x)+tf(y)\) (\(0<t<1\))일 때 볼록입니다. 이는 에피그래프의 볼록성과 동치입니다. 열린 볼록집합의 \(C^1\) 함수에서는 볼록성, 일차 지지부등식, 기울기의 단조성 \((\nabla f(y)-\nabla f(x))^T(y-x)\ge0\) 이 서로 동치입니다.
증명. 에피그래프의 두 점 \((x,a),(y,b)\)에서 \(a\ge f(x)\), \(b\ge f(y)\)를 사용하면 함수 부등식으로 선분의 소속이 따릅니다. 역으로 유한 함수값의 두 그래프점을 택하면 함수 부등식을 얻습니다. 무한 함수값이 있는 경우 오른쪽은 \(+\infty\)라 조건에 제약을 더하지 않습니다.
미분가능한 경우 \(g(t)=f(x+t(y-x))\)에 볼록부등식을 적용하면 \((g(t)-g(0))/t\le g(1)-g(0)\)입니다. \(t\downarrow0\)으로 보내 일차 부등식을 얻습니다. 역으로 \(z=(1-t)x+ty\)에서 \(x,y\)를 향한 일차 부등식에 각각 \(1-t,t\)를 곱해 더하면 기울기 항이 소거되어 볼록성이 나옵니다. 일차 부등식을 \(x,y\)에서 서로 바꾸어 더하면 기울기 단조성입니다. 단조성을 가정하면 \(d=y-x\)에 대해 \([\nabla f(x+td)-\nabla f(x)]^Td\ge0\) (\(t>0\))입니다. \(0\le t\le1\)에서 적분하여 \(f(y)-f(x)\ge\nabla f(x)^Td\)를 얻습니다. ∎
정리 2. 이차 판정, 강볼록성과 평활성#
\(C^2\) 함수의 볼록성은 \(\nabla^2f\succeq0\)와 동치입니다. \(m\)-강볼록성은 \(\nabla^2f\succeq mI\)와 동치입니다. 볼록 함수에서는 기울기의 \(L\)-Lipschitz성, 헤시안 상한 \(\nabla^2f\preceq LI\), 위쪽 이차부등식이 동치입니다. 또한 기울기는 \(1/L\)-공강단조입니다.
증명. \(d=y-x\)를 고정하여 두 번 적분하면
헤시안 준정부호이면 정리 1의 일차부등식이 나옵니다. 역으로 볼록성을 \(x\pm hd\)의 중점에 적용하여 \(f(x+hd)-2f(x)+f(x-hd)\ge0\)를 얻고 \(h^2\)로 나눈 극한에서 \(d^T\nabla^2f(x)d\ge0\)입니다. \(f(x)-m\|x\|^2/2\)에 같은 명제를 적용하면 강볼록 동치입니다.
헤시안 상한과 볼록성은 \(\|\nabla^2f\|\le L\)을 주므로 선분에서 기울기를 적분하면 Lipschitz성입니다. 역으로 방향 미분의 극한에서 \(\|\nabla^2f(x)d\|\le L\|d\|\)를 얻습니다. 위 적분식으로 위쪽 이차부등식도 얻고, 그 부등식을 \(y=x+hd\)에 넣어 \(h^2/2\)로 나눈 극한이 헤시안 상한을 줍니다.
마지막으로 \(g=\nabla f(y)-\nabla f(x)=\int_0^1H_t d\,dt\)라 쓰겠습니다. 적분의 Cauchy–Schwarz와 \(H_t^2\preceq LH_t\)에서
이것이 공강단조 부등식입니다. 역으로 이 부등식과 Cauchy–Schwarz를 결합하면 \(\|g\|\le L\|d\|\)입니다. 여기서 \(L>0\)이고, 비미분 헤시안까지 포함하는 일반 Baillon–Haddad 정리 대신 현재 \(C^2\) 조건에서 완전히 증명했습니다. ∎
정리 3. 최소점과 타원체, 합동변환#
볼록 미분가능 함수에서 정지점은 전역 최소점입니다. 강볼록이면 최소점은 유일합니다. \(H\succ0\)인 이차함수의 비용 증가 \(a>0\) 등고선 반축은 \(\sqrt{2a/\lambda_i(H)}\)이며, \(x=By+c\)에서 헤시안은 \(B^THB\)입니다.
증명. 정지점의 일차부등식으로 전역 최소성을 얻습니다. 강볼록 최소점 두 개가 다르면 두 점의 중점에서 양의 거리항만큼 최소값보다 작아져 모순입니다. 직교분해 \(H=Q\Lambda Q^T\)와 \(z=Q^T(x-x_*)\)를 쓰면 \(\sum_i\lambda_i z_i^2/2=a\)이므로 반축이 나옵니다. 연쇄법칙으로 \(\nabla_y f(By+c)=B^T\nabla f(By+c)\)이고 다시 미분하면 합동식입니다. 가역 \(B\)에서만 관성 보존을 적용합니다. ∎
정리 4. 볼록성 보존과 부분최소화#
볼록 함수의 비음수 가중합·아핀 합성·점별 상한·원근함수는 볼록입니다. 공동 볼록 \(f(x,y)\)의 \(g(x)=\inf_yf(x,y)\)도 \(-\infty\)가 생기지 않는 범위에서 볼록이며, \(C\succ0\)인 블록 이차식은 6절의 Schur 보원으로 주어집니다.
증명. 가중합은 각 볼록부등식에 비음수 가중치를 곱해 더합니다. 아핀사상은 선분을 같은 비율의 선분으로 보냅니다. 상한에는 각 지표 \(i\)에 \(f_i((1-t)x+ty)\le(1-t)\sup_jf_j(x)+t\sup_jf_j(y)\)를 쓴 뒤 왼쪽의 상한을 취합니다.
부분최소화에서 \(g(x),g(x')\)가 유한이면 임의 \(\eta>0\)에 \(f(x,y)\le g(x)+\eta\), \(f(x',y')\le g(x')+\eta\)인 점을 고릅니다. 공동 볼록성을 적용하고 중간 \(y\)에 대해 하한을 취하면 \(g((1-t)x+tx')\le(1-t)g(x)+tg(x')+\eta\)입니다. \(\eta\downarrow0\)으로 보냅니다. 값이 \(+\infty\)인 끝점의 부등식은 자동입니다. 최소값의 달성을 가정할 필요가 없지만 부분최소화 결과의 닫힘까지 자동으로 얻지는 않습니다.
원근함수에는 \(r=(1-\theta)t+\theta s>0\)라 놓습니다. \(( (1-\theta)x+\theta y)/r\)는 \(x/t,y/s\)를 가중치 \((1-\theta)t/r,\theta s/r\)로 섞은 것입니다. 볼록부등식에 \(r\)을 곱하면 원근함수의 볼록성이 나옵니다. 마지막 Schur 식은 \(\frac12(y+C^{-1}B^Tx)^TC(y+C^{-1}B^Tx)+\frac12x^T(A-BC^{-1}B^T)x\)로 전개하여 첫 항을 0으로 만듭니다. ∎
정리 5. 닫힌 볼록집합 사영#
비어 있지 않은 닫힌 볼록집합의 유클리드 사영은 존재·유일하며 7절의 변분부등식과 강한 비확장 부등식을 만족합니다. 사영이 선형일 필요충분조건은 집합이 부분공간인 것입니다.
증명. 집합 안의 기준점 \(y_0\)를 택하면 최소화에는 \(\|v-y\|\le\|v-y_0\|+1\)인 점만 고려하면 됩니다. 이 제한의 닫힘·유계성과 유한차원 컴팩트성으로 연속 거리함수가 최소를 달성합니다. 두 다른 최소점이 있으면 거리제곱의 중점 항등식에서 중점은 두 거리제곱 평균보다 두 점 거리제곱의 \(1/4\)만큼 작아 모순입니다.
최소점 \(z\)와 임의 \(y\in C\)에 대해 \(z+t(y-z)\in C\)입니다. 거리제곱의 오른쪽 도함수는 \(-2(v-z)^T(y-z)\)여서 비음수입니다. 역으로 이 부등식이 있으면 \(\|v-y\|^2=\|v-z\|^2+\|y-z\|^2-2(v-z)^T(y-z)\ge\|v-z\|^2\)이므로 최소점입니다.
\(p=P_C(v),q=P_C(w)\)의 두 변분부등식을 더하면 \(\|p-q\|^2\le(v-w)^T(p-q)\)입니다. Cauchy–Schwarz 후 \(\|p-q\|\)로 나누어 비확장성을 얻습니다. 두 점이 같으면 이미 성립합니다. 부분공간일 때는 H1의 선형 직교사영입니다. 역으로 사영이 선형이면 그 상이 부분공간인데, \(y\in C\)이면 \(P_C(y)=y\)라는 사실과 항상 \(P_C(v)\in C\)에서 그 상은 정확히 \(C\)입니다. ∎
앞의 선택 문제 |
수학적 표현 |
|---|---|
두 계획을 섞어도 비용이 평균을 넘지 않는다 |
볼록성 |
모든 방향에 같은 양의 곡률 하한이 있다 |
강볼록성 |
다른 변수를 최적으로 맞춘 뒤 남는 비용 |
부분최소화와 Schur 보원 |
허용계획 중 입력에 가장 가까운 점 |
볼록 사영과 변분부등식 |
볼록성과 사영은 최소점의 존재·유일성과 일차 조건을 연결합니다. 다음 장에서는 해가 없는 경우에도 그 불가능성을 설명하는 분리벡터와 쌍대 조건을 구합니다. O2로 이어 읽기.