O2 · 불가능성의 증명서에서 쌍대성과 가격까지

1. 자원이 충분하지 않다는 사실을 한 줄로 증명하기

두 생산활동의 자원 사용량을 같은 기준단위로 나누어 기록합니다. 활동 1은 첫 자원만 1단위 사용하고, 활동 2는 두 자원을 각각 1단위 사용합니다. 비음수 활동량 \(x\)의 총사용량은

\[\begin{split} Ax=\begin{pmatrix}1&1\\0&1\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix},\qquad x_1,x_2\ge0. \end{split}\]

총사용량을 \(b=(1,2)^T\)로 맞출 수 있을까요? 둘째 식은 \(x_2=2\), 첫째 식은 \(x_1+2=1\)이므로 \(x_1=-1\)입니다. 실수 연립방정식은 풀리지만 허용계획은 없습니다.

해를 구하지 않고도 확인할 수 있습니다. 자원 가중치 \(y=(1,-1)^T\)를 주면 \(A^Ty=(1,0)^T\ge0\)입니다. 어떤 비음수 활동을 해도 이 가중합은 음수가 될 수 없습니다. 그런데 목표는 \(b^Ty=1-2=-1<0\)입니다. 따라서 목표를 만드는 비음수 활동량은 존재하지 않습니다. 이 \(y\)가 불가능성의 증명서입니다. 여기서 \(y\)는 생산자원에 붙인 검산 가중치이며, 모든 성분이 양수인 시장가격이라고 해석하지 않습니다.

가능한 총사용량의 집합은 \(K=\{(s,t):s\ge t\ge0\}\)입니다. \(b\)에 가장 가까운 점은 \(p=(3/2,3/2)\)이며 \(p-b=(1/2,-1/2)\)는 앞 증명서의 절반입니다. O1의 최근접점이 부등식 증명서를 만들어 줍니다.

그림 119 축은 각 자원의 기준단위 사용량이다. 음영은 실제로 만들 수 있는 전체 원뿔의 표시 범위이며 점선은 \(y^Tz=0\)이다. 목표에서 최근접점으로 향하는 선분이 증명서 방향과 평행하다.

2. 등식의 직교여공간에서 부등식의 쌍대원뿔로

열공간에서는 어떤 방향과 그 음의 방향을 모두 사용할 수 있습니다. 그래서 \(b\in\operatorname{col}A\)의 조건은 \(A^Ty=0\)인 모든 \(y\)에 \(b^Ty=0\)인 것입니다. 비음수 계수만 허용하면 0이라는 등식이 방향성 있는 부등식으로 바뀝니다.

\[ \exists x\ge0:Ax=b \quad\Longleftrightarrow\quad b^Ty\ge0\ \text{for every }y\text{ with }A^Ty\ge0. \]

오른쪽의 가중치 집합 \(K^*=\{y:y^Tz\ge0\text{ for all }z\in K\}\)를 쌍대원뿔이라 합니다. 이 책의 별표는 비음수 내적 규약입니다. 내적이 비양수인 집합 \(K^\circ=-K^*\)는 극원뿔로 구별합니다. O4의 Moreau 분해에서 이 부호가 필요합니다.

Farkas 보조정리는 비음수 해와 엄격히 음수인 증명서 중 정확히 하나가 존재한다고 말합니다. 둘이 동시에 있으면 \(b^Ty=x^TA^Ty\ge0\)과 모순입니다. 어려운 방향은 해가 없을 때 증명서가 항상 나온다는 것입니다. 마지막 절에서 사영·폐쇄성으로 한 번, 변수 소거로 한 번 증명합니다.

닫힘은 단순한 기술조건이 아닙니다. \(K=\{(s,t):t>0\}\cup\{0\}\)는 볼록원뿔이지만 닫혀 있지 않습니다. \(b=(1,0)\)은 그 안에 없는데 어떤 \(y\in K^*\)에도 \(b^Ty<0\)가 불가능합니다. 실제로 \(K^*=\{(0,a):a\ge0\}\)입니다. 유한 개 열이 생성하는 원뿔이 닫혀 있다는 정리를 먼저 확보해야 하는 이유입니다.

3. 선형 가격을 빼고 남는 최댓값

비용 \(f(x)\)에 대해 \(u\)를 단위 활동에 대한 보상으로 생각하면 순보상은 \(u^Tx-f(x)\)입니다. 그 최댓값

\[ f^*(u)=\sup_x\{u^Tx-f(x)\} \]

을 Fenchel 켤레라고 합니다. \(f(x)=\frac12x^THx\), \(H\succ0\)이면

\[ u^Tx-\tfrac12x^THx =\tfrac12u^TH^{-1}u-\tfrac12(x-H^{-1}u)^TH(x-H^{-1}u), \]

따라서 \(f^*(u)=u^TH^{-1}u/2\)이고 최대점은 \(H^{-1}u\)입니다. 함수값의 비용 단위와 \(u^Tx\)의 단위를 맞춰야 이 해석을 사용할 수 있습니다.

허용집합의 지시함수 \(\delta_C\)의 켤레는 \(\sigma_C(u)=\sup_{x\in C}u^Tx\), 즉 지지함수입니다. \(C=[-1,1]^n\)에서는 각 성분의 부호를 \(u_i\)에 맞추어 \(\sigma_C(u)=\sum_i|u_i|\)입니다. 일반 노름의 단위공에서는 지지함수가 쌍대노름입니다. 이와 달리 노름 자체의 켤레는 쌍대 단위공의 지시함수입니다. 함수와 그 단위공의 지시함수를 혼동하지 않습니다.

정의에서 모든 \(x,u\)에 \(f(x)+f^*(u)\ge u^Tx\)입니다. Fenchel–Young 부등식의 등호는 \(u\)가 \(x\)에서 아래로 지지하는 기울기라는 뜻입니다. 미분이 없어도

\[ u\in\partial f(x)\quad\Longleftrightarrow\quad f(z)\ge f(x)+u^T(z-x)\ \text{for all }z \]

로 준미분을 정의합니다. 예를 들어 \(|x|\)의 원점에서는 \(|z|\ge uz\)가 모든 \(z\)에서 성립할 조건이 \(-1\le u\le1\)이므로 \(\partial|0|=[-1,1]\)입니다. \(0\in\partial f(x_*)\)는 모든 점의 함수값이 \(f(x_*)\) 이상이라는 최소점 조건 자체입니다.

4. 아래에서 지지하는 모든 아핀함수를 모으면

이중켤레는 \(f^{**}(x)=\sup_u\{u^Tx-f^*(u)\}\)입니다. 각 중괄호는 \(f\) 아래에 있는 아핀함수입니다. 진정한 함수라는 뜻의 proper는 유한값인 점이 하나 이상이고 \(-\infty\) 값을 갖지 않는다는 뜻입니다. proper·하반연속·볼록이면 \(f^{**}=f\)입니다. 하반연속은 에피그래프가 닫혀 있다는 조건과 같습니다.

비볼록 함수에서는 아핀 하한들을 모아 가장 큰 닫힌 볼록 하한을 만듭니다. 다만 아핀 하한 자체가 없는 함수까지 proper인 볼록포락이 생긴다고 말해서는 안 됩니다. 여기서는 아핀 하한이 존재하는 함수들을 대상으로 합니다.

구체적으로 \(f(t)=(t^2-1)^2\)의 닫힌 볼록포락은

\[\begin{split} g(t)=\begin{cases}0,&|t|\le1,\\(t^2-1)^2,&|t|\ge1.\end{cases} \end{split}\]

바깥 구간의 둘째 미분은 \(12t^2-4>0\)이고 경계에서 도함수가 0이라 \(g\)의 기울기가 전체에서 비감소합니다. 따라서 \(g\)는 볼록입니다. 어떤 볼록 하한도 두 점 \((-1,0),(1,0)\) 사이에서는 0을 넘을 수 없고, 바깥에서는 \(f\)를 넘을 수 없습니다. 따라서 이 \(g\)보다 큰 볼록 하한은 없습니다.

그림 120 가로축은 무차원 선택변수이고 세로축은 비용이다. 볼록포락의 평평한 구간은 원래 함수의 그래프가 아니라 아래에서 지지하는 함수들이 만드는 값이다.

행렬에서도 비슷한 일이 일어납니다. \(\|X\|_2\le1\)로 제한하면 모든 특이값이 \([0,1]\)에 있어 \(\|X\|_*:=\sum_i\sigma_i(X)\le\operatorname{rank}X\)입니다. 핵노름은 이 영역에서 rank의 가장 큰 볼록 하한입니다. 증명은 특이값 각각을 0 또는 1로 만든 행렬들의 가중평균으로 \(X\)를 표현하는 것입니다. 제한을 빼면 rank는 크기에 따라 증가하지 않아 같은 결론이 틀립니다. 스칼라에서 \(|2|=2>\operatorname{rank}[2]=1\)입니다.

5. 행렬의 준미분을 실제로 읽기

대칭행렬 \(X\)의 최대 고윳값은 \(\lambda_{\max}(X)=\max_{\|q\|=1}\langle qq^T,X\rangle\)입니다. 여기서 행렬 내적은 \(\langle Y,X\rangle=\operatorname{tr}(Y^TX)\)입니다. 최대 고유공간의 단위벡터 \(q\)에 대해 \(qq^T\)는 준기울기입니다. 최대 고윳값이 여러 개면 그 사영들의 모든 볼록결합이 가능합니다.

예를 들어 \(X=\operatorname{diag}(2,1)\)에서는 준미분이 \(\{\operatorname{diag}(1,0)\}\)이고 \(X=2I_2\)에서는 \(\{G\succeq0:\operatorname{tr}G=1\}\)입니다. 중복 고윳값에서는 하나의 미분행렬을 고르는 것이 전부가 아닙니다.

얇은 SVD \(X=U\Sigma V^T\)의 비영 특이값 수를 \(r\)라 하면

\[ \partial\|X\|_*= \{UV^T+W:U^TW=0,\ WV=0,\ \|W\|_2\le1\}. \]

이미 사용한 특이방향의 기울기는 \(UV^T\)로 고정되고, 영 특이값 방향에는 노름 1 이하의 자유도가 남습니다. 예를 들어 \(X=\operatorname{diag}(2,0)\)에서는 \(\operatorname{diag}(1,w)\), \(|w|\le1\)입니다. 마지막 절에서 노름의 지지함수 표현과 등호 조건으로 두 공식을 증명합니다.

6. 세 가지 자기쌍대 원뿔과 행렬 부등식

비음수 사분면은 자기쌍대입니다. 음수 성분을 가진 \(y\)에는 해당 좌표벡터가 음의 내적을 만들고, 모든 성분이 비음수면 모든 비음수 벡터와 내적이 비음수입니다.

Lorentz 원뿔 \(L=\{(t,x):t\ge\|x\|_2\}\)도 자기쌍대입니다. 두 원소의 내적은 \(ts+x^Ty\ge ts-\|x\|\|y\|\ge0\)입니다. \((s,y)\notin L\)이고 \(y\ne0\)이면 \((1,-y/\|y\|)\in L\)과의 내적 \(s-\|y\|<0\)가 증명서입니다. \(y=0,s<0\)이면 \((1,0)\)을 씁니다.

대칭 양의 준정부호 원뿔 역시 자기쌍대입니다. \(X,Y\succeq0\)에서 \(\operatorname{tr}(XY)=\operatorname{tr}(X^{1/2}YX^{1/2})\ge0\)입니다. \(Y\)에 음의 이차방향 \(v\)가 있으면 \(X=vv^T\succeq0\)에 내적이 \(v^TYv<0\)입니다.

이 원뿔을 사용하면 \(t\ge\|x\|\)나 행렬 준정부호성을 제약으로 쓸 수 있습니다. 예를 들어 \(C\succ0\)일 때 \(A-BC^{-1}B^T\succeq0\)는 \(\begin{pmatrix}A&B\\B^T&C\end{pmatrix}\succeq0\)와 같습니다. 이는 H7의 Schur 보원 및 O1의 완전제곱식으로 이미 증명한 결과입니다. \(C\)가 특이하면 역행렬식을 그대로 쓸 수 없고 범위 조건과 유사역행렬이 필요합니다.

7. 제약의 가격과 강쌍대성

볼록 비용 \(f\)에 \(Ax\le b\)를 부과하면, 비음수 승수 \(\lambda\)로

\[ L(x,\lambda)=f(x)+\lambda^T(Ax-b),\quad d(\lambda)=\inf_xL(x,\lambda) =-b^T\lambda-f^*(-A^T\lambda) \]

를 만듭니다. 허용 \(x\)에서는 \(\lambda^T(Ax-b)\le0\)이므로 \(d(\lambda)\le f(x)\)입니다. 모든 쌍대 허용점이 원래 최솟값의 하한을 준다는 약쌍대성입니다.

예를 들어 \(\min\frac12x^2\) s.t. \(x\ge1\)에서 \(L=\frac12x^2+\lambda(1-x)\)이고, \(x\)를 최소화하면 \(d(\lambda)=\lambda-\lambda^2/2\)입니다. \(\lambda\ge0\)에서 최대는 \(\lambda=1\)이고 값 \(1/2\)로 원문제 \(x=1\)과 같습니다. \(x=2\)가 제약을 엄격히 만족하므로 Slater 조건도 있습니다.

그림 121 왼쪽은 허용구간에서 비용을 최소화하고 오른쪽은 승수에 따른 하한을 최대화한다. 두 패널의 세로축은 같은 비용 눈금이다. 원변수와 승수는 다른 변수이므로 가로축의 의미도 다르다.

유한값인 \(C^1\) 볼록 \(f,g_i\)와 아핀 등식제약을 갖는 문제에서 엄격 부등식을 만족하는 등식 허용점이 있고 유한 최적값을 달성하면, 쌍대 최적 승수가 존재하고 값의 간극이 없습니다. 아래에서는 이 범위의 Slater 정리를 등식 매개화와 분리로 증명하고 상보성 \(\lambda_i g_i(x_*)=0\)도 얻습니다. 원문제 달성을 요구하지 않는 값의 정리와 비매끄러운 확장은 별도의 일반화입니다.

8. 게임과 유한 상태의 가격에 적용하기

행 플레이어가 보상을 크게 하고 열 플레이어가 작게 하는 게임에서

\[\begin{split} M=\begin{pmatrix}2&0\\0&1\end{pmatrix} \end{split}\]

라 합시다. 행 1을 확률 \(p\)로 고르면 열의 두 순수 선택에 대한 기대보상은 \(2p\)와 \(1-p\)입니다. 작은 값을 최대화하려면 둘을 같게 하여 \(p=1/3\), 값 \(2/3\)입니다. 열 플레이어도 첫 열 확률 \(q=1/3\)에서 두 행 보상을 같게 합니다. 보상 단위는 양쪽에서 같습니다.

일반 유한 게임에서는 \(\max_{p\ge0,\,\mathbf1^Tp=1}t\) s.t. \(M^Tp\ge t\mathbf1\)와 그 LP 쌍대가 열 플레이어의 문제입니다. 엄격히 양수인 \(p\)와 충분히 작은 \(t\)로 엄격 실행가능성을 만들 수 있어 위 강쌍대성으로 minimax 등식을 얻습니다. 정확한 행렬 데이터 없이 게임의 균형이 유일하다고까지 주장하지 않습니다.

유한 상태 자산에는 현재 가격도 반드시 포함해야 합니다. 지급행렬 \(D\in\mathbb R^{s\times n}\)와 현재 가격 \(p\in\mathbb R^n\)에서 차익거래는 \(p^T\theta\le0\), \(D\theta\ge0\)이고 현재 또는 미래 중 적어도 하나가 엄격한 이익인 포트폴리오입니다. 모든 상태를 가능하다고 간주하고 자유로운 공매도를 허용하는 모형입니다. \(B=[-p^T;D]\)라 놓으면 이는 \(B\theta\ge0\), \(B\theta\ne0\)입니다.

Stiemke 택일정리에 의해 차익거래가 없을 필요충분조건은 \(B^Ty=0\)인 엄격 양수 \(y=(y_0,\psi)\)의 존재입니다. \(y_0\)로 나누면 \(D^T(\psi/y_0)=p\)인 엄격 양수 상태가격을 얻습니다. 지급행렬만 적고 현재 가격을 누락하면 다른 명제가 됩니다.

예를 들어 두 상태에서 채권 \((1,1)\)의 가격이 1, 상태별 지급 \((1,2)\)의 가격이 \(3/2\)이면 \(\psi_1+\psi_2=1\), \(\psi_1+2\psi_2=3/2\)에서 \(\psi=(1/2,1/2)\)입니다. 둘째 자산 가격이 \(11/5\)라면 그 자산을 1개 팔고 채권 2개를 사면 현재 \(1/5\)를 받고 미래 지급은 \((1,0)\)이므로 차익거래입니다. 이것은 이 유한 모형의 수학적 계산입니다.

import numpy as np
from scipy.optimize import linprog
A = np.array([[1.,1.],[0.,1.]])
b = np.array([1.,2.]); certificate = np.array([1.,-1.])
assert np.all(A.T@certificate >= 0) and b@certificate < 0
game = np.diag([2.,1.]); prob = np.array([1/3,2/3])
assert np.allclose(prob@game,[2/3,2/3])
# 변수는 p1,p2,t. t는 확률이 아니므로 부호 제한을 두지 않는다.
fit = linprog([0,0,-1],A_ub=np.c_[-game.T,np.ones(2)],b_ub=np.zeros(2),
              A_eq=[[1,1,0]],b_eq=[1],bounds=[(0,None),(0,None),(None,None)],method='highs')
assert fit.success and np.isclose(fit.x[-1],2/3)
print("불가능성 증명서와 게임값:",certificate,fit.x[-1])

불가능성 증명서와 게임값: [ 1. -1.] 0.6666666666666666

Gordan 택일은 엄격 감소방향과 비음수 기울기 의존성을 비교하여 다음 장의 Fritz John 조건에 연결됩니다. 혼합 엄격·비엄격 부등식의 Motzkin 정리, 일반 다면체의 Minkowski–Weyl 표현, P-행렬 LCP의 모든 우변에 대한 유일성, 경제 균형의 전역 지표정리는 추가 조망입니다. 특히 Walras 법칙과 동차성 때문에 전체 가격 Jacobian은 균형에서 특이할 수 있으므로 그 행렬식 부호를 곧바로 균형 지표라고 쓰지 않습니다. 정규화된 가격공간, 경계조건과 정칙성 등 위상적 가정이 필요합니다.

9. 연습과 전체 풀이

1. 첫 생산행렬에서 목표 \((3,1)\)의 허용해를 구하세요.

풀이. 둘째 식에서 \(x_2=1\), 첫째에서 \(x_1=2\)입니다. 어떤 \(y\)가 \(A^Ty\ge0\)를 만족하면 \(b^Ty=2(A^Ty)_1+(A^Ty)_2\ge0\)이므로 엄격 음수 증명서는 없습니다.

2. \(K=\{x_1\ge x_2\ge x_3\ge0\}\)의 쌍대원뿔을 구하세요.

풀이. \(x=a(1,0,0)+b(1,1,0)+c(1,1,1)\)이고 \(a=x_1-x_2\), \(b=x_2-x_3\), \(c=x_3\)가 모두 비음수입니다. 따라서 쌍대는 \(y_1\ge0\), \(y_1+y_2\ge0\), \(y_1+y_2+y_3\ge0\)입니다. \((1,-1,0)\)은 쌍대에 있지만 \(K\)에 없으므로 자기쌍대가 아닙니다.

3. \(f(x)=|x|\)의 켤레를 구하세요.

풀이. \(|u|\le1\)이면 \(ux-|x|\le0\)이고 \(x=0\)에서 0입니다. \(|u|>1\)이면 \(x\)를 \(u\)와 같은 부호로 무한히 늘려 값이 무한대로 갑니다. 따라서 \(f^*(u)=\delta_{[-1,1]}(u)\)입니다.

4. \(X=\operatorname{diag}(3,-1)\)이 PSD가 아니라는 원뿔 증명서를 구하세요.

풀이. \(Y=e_2e_2^T\succeq0\)에서 \(\operatorname{tr}(YX)=-1\)입니다. 자기쌍대성에 필요한 모든 PSD 행렬과의 비음수 내적을 위반합니다.

5. \(X=\operatorname{diag}(1/2,1/4)\)를 0·1 특이값 행렬의 볼록결합으로 쓰세요.

풀이. \(\operatorname{diag}(0,0),(1,0),(0,1),(1,1)\)에 각각 \(3/8,3/8,1/8,1/8\)의 가중치를 줍니다. 성분 평균은 \((1/2,1/4)\)이고 rank 평균은 \(3/8+1/8+2/8=3/4=\|X\|_*\)입니다. 이것이 rank를 볼록화할 때 핵노름보다 큰 하한을 만들 수 없는 이유입니다.

6. \(x\ge a>0\) 아래 \(x^2/2\) 최소화의 최적 승수를 구하세요.

풀이. 쌍대함수는 \(a\lambda-\lambda^2/2\)입니다. 미분하면 \(a-\lambda=0\)에서 \(\lambda=a>0\)이고 값은 \(a^2/2\)입니다. 최적점 \(x=a\)의 제약은 활성이고 상보성도 성립합니다.

7. 상태가격 \((1/2,1/2)\)에서 지급 \((0,2)\)의 가격을 구하세요.

풀이. 상태가격 내적은 1입니다. 기존 두 자산으로 \(-2(1,1)+2(1,2)=(0,2)\)를 복제할 수 있고 현재 비용도 \(-2+2(3/2)=1\)입니다. 상태가격과 복제 계산이 일치합니다.

8. 열공간의 직교여공간과 쌍대원뿔은 왜 다르나요?

풀이. 첫 \(A\)는 가역이므로 \(\ker A^T=\{0\}\)입니다. 그러나 \(A^Ty\ge0\)에는 \((1,-1)\) 같은 비영 벡터가 있습니다. 실수 계수의 해 존재를 검사하는 직교여공간에는 비음수 계수라는 추가 제약 정보가 없습니다.

10. 지금까지의 내용을 수학의 언어로 정리해 봅시다

유한차원 실 공간에서 내적을 사용합니다. 행렬 공간은 Frobenius 내적을 사용하고, 함수의 닫힘은 에피그래프의 닫힘을 뜻합니다.

정리 1. 사영에 의한 분리와 지지

비어 있지 않은 닫힌 볼록집합 \(C\) 밖의 \(b\)에는 \(a^Tb>\alpha> a^Tx\) for all \(x\in C\)인 \(a\ne0,\alpha\)가 존재합니다. 닫힌 볼록집합의 경계점에는 비영 지지법선이 존재합니다.

증명. \(p=P_C(b)\), \(a=b-p\)라 놓으면 O1의 변분부등식에서 \(a^Tx\le a^Tp\)입니다. \(a^Tb-a^Tp=\|b-p\|^2>0\)이므로 두 값의 중간을 \(\alpha\)로 잡습니다. 경계점 \(z\)에는 집합 밖 \(b_j\to z\)를 고르고 사영 \(p_j\)를 잡습니다. \(\|p_j-b_j\|\le\|z-b_j\|\)이므로 \(p_j\to z\)입니다. 단위법선 \(a_j=(b_j-p_j)/\|b_j-p_j\|\)의 수렴 부분수열을 택해 \(a_j^T(x-p_j)\le0\)의 극한을 취하면 \(a^T(x-z)\le0\), \(\|a\|=1\)입니다.

열린 볼록집합에도 그 폐포를 사용하여 바깥 점과 약분리할 수 있습니다. 점이 폐포 밖이면 첫 부분을, 경계면 둘째 부분을 씁니다. 열린 집합의 폐포 내부가 원래 집합과 같다는 사실은 작은 단체를 집합 안에서 골라 근처점을 그 단체 내부의 볼록결합으로 표현하여 확인합니다. 따라서 집합 밖 점이 폐포의 내부로 들어가는 경우는 없습니다. 두 서로소 볼록집합 중 하나가 컴팩트이고 다른 하나가 닫혔으면 차집합은 닫힌 볼록집합이고 0을 포함하지 않습니다. 첫 부분을 0과 차집합에 적용하여 강분리를 얻습니다. ∎

정리 2. 유한 원뿔의 닫힘과 Farkas의 첫 증명

유한 개 벡터가 생성하는 원뿔은 닫혀 있습니다. 따라서 2절의 Farkas 택일이 성립합니다.

증명. 양의 계수로 쓰인 생성벡터들이 종속이면 \(\sum c_i a_i=0\)인 비영 관계를 고릅니다. 필요하면 부호를 바꾸어 양의 \(c_i\)가 있게 합니다. 현재 계수 \(t_i>0\)에 \(\tau=\min_{c_i>0}t_i/c_i\)를 두고 \(t_i\leftarrow t_i-\tau c_i\)로 바꾸면 모두 비음수이고 한 계수 이상이 0이 되며 벡터합은 같습니다. 반복하면 독립 부분목록만 남습니다.

이제 원뿔의 수열 \(z_j\to z\)를 독립 부분목록들로 표현합니다. 목록은 유한 개이므로 한 부분수열에서 같은 독립행렬 \(A_I\)를 씁니다. 계수는 \(t_j=(A_I^TA_I)^{-1}A_I^Tz_j\)여서 수렴하며 극한도 비음수입니다. 따라서 \(z=A_I\lim t_j\)가 원뿔에 있습니다.

\(b\)가 원뿔 밖이면 사영 \(p\)와 \(y=p-b\)를 잡습니다. 변분부등식에서 \(y^T(z-p)\ge0\)입니다. \(z=0,2p\)를 각각 넣으면 \(y^Tp=0\)이고, 모든 원뿔점에 \(y^Tz\ge0\)입니다. 특히 각 열에 적용해 \(A^Ty\ge0\)입니다. \(y^Tb=y^T(p-y)=-\|y\|^2<0\)입니다. 배타성은 2절의 곱셈으로 증명했습니다. ∎

정리 3. Fourier–Motzkin에 의한 대수적 증명

부등식계 \(Mx\le d\)가 불가능하면 \(\lambda\ge0\), \(\lambda^TM=0\), \(\lambda^Td<0\)인 증명서가 존재합니다.

증명. 마지막 변수 \(t\)의 계수가 양·음·0인 행으로 나눕니다. 양의 행은 \(t\le U_i(z)\), 음의 행은 \(t\ge L_j(z)\)이고 0인 행은 \(z\)에 관한 제약입니다. \(t\)가 존재할 필요충분조건은 모든 \(L_j(z)\le U_i(z)\)와 0계수 행입니다. 한쪽 목록이 없으면 다른 쪽의 유한한 상·하한을 만족하도록 \(t\)를 충분히 작거나 크게 고를 수 있습니다.

각 새 부등식은 원래 양·음 행에 양의 수를 곱해 더하여 \(t\)를 소거한 것입니다. 그러므로 모든 소거 단계의 행은 최초 행들의 비음수 결합입니다. 변수 수에 귀납하면 불가능한 계는 마지막에 \(0\le d'<0\)인 행을 만듭니다. 그 행의 비음수 조합계수를 추적하면 원하는 \(\lambda\)입니다. 변수 0개의 시작 경우는 바로 거짓 상수 부등식입니다. 역으로 그런 결합이 있으면 허용 \(x\)를 대입하여 \(0\le\lambda^Td<0\)이므로 불가능합니다.

이를 \(Ax\le b\), \(-Ax\le-b\), \(-x\le0\)에 적용합니다. 증명서 계수를 \(u,v,w\ge0\)라 쓰면 \(A^T(u-v)=w\ge0\), \(b^T(u-v)<0\)입니다. 따라서 \(y=u-v\)가 Farkas 증명서입니다. ∎

정리 4. 켤레, Fenchel–Young와 이중켤레

proper 닫힌 볼록 \(f\)에는 \(f^{**}=f\)입니다. \(f(x),f^*(u)\)가 유한할 때 Fenchel–Young 등호는 \(u\in\partial f(x)\)와 동치이며, 닫힌 볼록이면 \(x\in\partial f^*(u)\)와도 동치입니다.

증명. 정의상 \(f^*(u)\ge u^Tx-f(x)\)입니다. 등호이면 모든 \(z\)에 \(u^Tz-f(z)\le u^Tx-f(x)\)여서 준미분 부등식입니다. 역으로 준미분 부등식을 정리하면 \(x\)가 켤레의 상한을 달성합니다.

이중켤레의 각 아핀항은 \(f\) 이하라 \(f^{**}\le f\)입니다. 역방향을 위해 \((x,t)\)가 닫힌 볼록 에피그래프 밖이라고 합시다. 강분리로 \(a^Tz+\beta r\ge\gamma>a^Tx+\beta t\) for \((z,r)\in\operatorname{epi}f\)를 얻습니다. 위로 열린 에피그래프 때문에 \(\beta\ge0\)입니다. 먼저 \(x_0\in\operatorname{dom}f\)의 바로 아래 점을 분리하면 같은 \(x_0\)의 그래프점이 있으므로 반드시 \(\beta>0\)입니다. 따라서 \(f\)에는 아핀 하한 \(l_0\)가 하나 존재합니다.

일반 분리에서 \(\beta>0\)이면 \(l(z)=(\gamma-a^Tz)/\beta\le f(z)\)이며 \(l(x)>t\)입니다. \(\beta=0\)이면 그 분리부등식에 \(r\ge l_0(z)\)의 양의 작은 배수를 더합니다. 새 \(r\) 계수는 양수이고, 원래 엄격 간격이 있으므로 배수를 충분히 작게 하면 \((x,t)\)와의 엄격분리는 유지됩니다. 역시 \(l(x)>t\)인 아핀 하한을 얻습니다.

모든 아핀 하한 \(v^Tz-c\le f(z)\)에는 \(c\ge f^*(v)\)이므로 \(f^{**}(x)\ge l(x)>t\)입니다. 임의 \(t<f(x)\)에 적용하여 역부등식을 얻습니다. \(f(x)=+\infty\)도 모든 유한 \(t\)에 적용하면 됩니다. \(f^*\)에 같은 결과를 적용하고 앞 등호 조건을 뒤집으면 두 준미분의 동치가 나옵니다. ∎

정리 5. 핵노름 볼록포락과 행렬 준미분

4·5절의 핵노름 포락과 두 행렬 준미분 공식이 성립합니다.

증명. SVD \(X=\sum_i\sigma_i u_iv_i^T\)에서 \(\langle Y,X\rangle\le\|Y\|_2\sum_i\sigma_i\)이며 \(Y=UV^T\)에서 등호입니다. 따라서 핵노름은 스펙트럼 단위공의 지지함수여서 볼록입니다. \(0\le\sigma_i\le1\)일 때 각 \(\sigma_i\)를 확률 \(\sigma_i\)로 1, 나머지 확률로 0인 유한 두 점 가중평균으로 씁니다. 모든 \(2^r\)개 선택을 곱가중하면 \(X\)는 같은 특이벡터의 0·1 행렬들의 평균이고 rank 평균은 \(\sum_i\sigma_i\)입니다. 임의 볼록 하한에 볼록부등식을 적용하면 핵노름 이하입니다. 핵노름 자체도 rank 이하이므로 최대 볼록 하한입니다.

일반 노름 \(N\)의 준미분은 \(N^\dagger(G)\le1\), \(\langle G,X\rangle=N(X)\)인 \(G\)들입니다. 준미분식에 \(0,2X\)를 넣어 등호를 얻고, 나머지 모든 \(Z\)에 \(\langle G,Z\rangle\le N(Z)\)를 얻으면 필요성입니다. 두 조건을 더하면 충분성입니다. 핵노름에서는 쌍대가 스펙트럼노름이므로 각 비영 특이방향에 \(u_i^TGv_i=1\)이어야 합니다. \(\|G\|_2\le1\)과 Cauchy–Schwarz의 등호에서 \(Gv_i=u_i\), \(G^Tu_i=v_i\)입니다. 나머지 직교 블록만 \(W\)로 남아 제시한 식이 됩니다. 반대로 그 블록 조건은 노름 1 이하와 내적 등호를 줍니다.

최대 고윳값에는 \(\lambda_{\max}(X)=\max_{G\succeq0,\operatorname{tr}G=1}\langle G,X\rangle\)입니다. 최대 고유공간에 지지된 그런 \(G\)는 바로 준기울기입니다.

역으로 준기울기 \(G\)에 \(X+tI\)를 대입하면 \(\operatorname{tr}G=1\)입니다. \(X-tvv^T\)는 최대 고윳값을 늘리지 않으므로 준미분 부등식에서 \(v^TGv\ge0\)입니다. \(0,2X\)를 대입하여 \(\langle G,X\rangle=\lambda_{\max}(X)\)를 얻습니다. \(G\succeq0\)이고 \(\lambda_{\max}I-X\succeq0\)와의 내적이 0이므로 \(G\)의 상은 최대 고유공간 안에 있습니다.

실제로 두 제곱근 곱의 Frobenius 제곱노름이 이 내적이라 곱이 0입니다. 그 공간 안에서 \(G\)를 고유분해하면 단위 고유벡터 사영들의 볼록결합이 됩니다. ∎

정리 6. Slater 강쌍대성

유한값 \(C^1\) 볼록 함수 \(f,g_1,\ldots,g_m\)와 아핀 등식으로 이루어진 문제에 엄격 부등식을 만족하는 등식 허용점이 있고 유한 최적값 \(p_*\)를 달성하면 쌍대 최적 승수가 존재하고 값은 \(p_*\)입니다.

증명. 등식 허용집합을 \(x=x_0+Zz\)로 먼저 매개화하면 다시 유한값 볼록 함수들입니다. 이 좌표에서

\[ \mathcal U=\{(u,t):\exists z,\ g_i(z)<u_i,\ f(z)<t\} \]

는 열린 볼록집합이며 \((0,p_*)\)를 포함하지 않습니다. 정리 1의 약분리로 비영 \((\lambda,\beta)\)에 \(\lambda^Tu+\beta t\ge\beta p_*\) for all \((u,t)\in\mathcal U\)를 얻습니다. 각 성분을 위로 무한히 늘릴 수 있어 \(\lambda\ge0,\beta\ge0\)입니다. \(\beta=0\)이면 \(\lambda\ne0\)인데 Slater 점의 모든 음수 \(g_i\)에 가까운 \(u<0\)를 택해 모순을 얻습니다.

따라서 \(\beta>0\)이고 나누어 1로 정규화합니다. \(u\downarrow g(z),t\downarrow f(z)\)를 취하면 \(f(z)+\lambda^Tg(z)\ge p_*\)입니다. 하한을 취하고 약쌍대성을 결합하여 등호를 얻습니다.

원문제 최소점 \(x_*\)에서는 \(p_*\le f(x_*)+\lambda^Tg(x_*)\le p_*\)여서 상보성이 성립하고 등식 허용집합 위의 Lagrangian 최소점입니다. 따라서 \(Z^T\nabla_xL(x_*)=0\)입니다. \(\operatorname{range}Z=\ker A\)이므로 \(\nabla_xL(x_*)\in\operatorname{range}A^T\)이고 \(\nabla_xL(x_*)+A^T\mu=0\)인 등식 승수를 고릅니다. 이 승수를 더한 전체 Lagrangian은 볼록하며 \(x_*\)에서 기울기가 0이므로 실수 공간 전체에서 최소입니다. 그 값이 \(p_*\)여서 등식을 포함한 원래 쌍대문제에서도 승수와 강쌍대성을 얻습니다. ∎

정리 7. Gordan과 Stiemke

정확히 하나가 성립한다: (i) \(Ax<0\)인 \(x\); (ii) \(y\ge0,y\ne0,A^Ty=0\). 또 정확히 하나가 성립한다: (i) \(Ax\ge0,Ax\ne0\); (ii) \(y>0,A^Ty=0\).

증명. 첫째의 엄격 부등식은 유한 행 수 때문에 스케일하여 \(Ax\le-\mathbf1\)와 동치입니다. 불가능하면 정리 3에서 \(y\ge0\), \(A^Ty=0\), \(-\mathbf1^Ty<0\)를 얻습니다. 배타성은 내적의 부호로 확인합니다.

둘째에는 \(L=\operatorname{range}A\)와 단체 \(\Delta=\{z\ge0:\mathbf1^Tz=1\}\)를 씁니다. (i)가 없으면 \(L\cap\Delta=\varnothing\)입니다. 닫힌 부분공간과 컴팩트 볼록 단체를 강분리하면 어떤 \(y\)에 \(\inf_{z\in\Delta}y^Tz>\sup_{w\in L}y^Tw\)입니다. 부분공간의 양·음 스케일 때문에 오른쪽이 유한할 수 있으려면 \(y\perp L\)이고 그 값은 0입니다. 왼쪽은 \(\min_i y_i\)이므로 모든 성분이 엄격 양수입니다. 역으로 엄격 양수 \(y\)는 모든 비영 비음수 \(Ax\)에 양의 내적을 주지만 \(A^Ty=0\)은 0을 주므로 둘은 양립하지 않습니다. ∎

생산·선택에서 한 말	수학적 표현
모든 활동은 가중합을 늘리는데 목표는 줄인다	Farkas 증명서
선형 보상을 비용에서 빼고 최댓값을 구한다	Fenchel 켤레
아래에서 지지하는 가능한 기울기를 모은다	준미분
제약의 가격으로 최적비용의 하한을 만든다	Lagrange 쌍대성

분리와 쌍대성은 가능한 해와 불가능성의 증명서를 구별하게 해 줍니다. 다음 장에서는 등식·부등식 제약이 있는 최소점에서 이러한 조건이 승수와 KKT 방정식으로 나타나는 과정을 봅니다. O3로 이어 읽기.