O3 · 제약을 만족하는 최소점과 안장점 선형계#
1. 합계를 맞추면서 두 활동의 비용을 최소화하기#
두 활동량 \(x_1,x_2\)를 같은 기준량으로 정규화하고 총량을 1로 맞춥니다. 비용도 기준비용으로 나누어
로 둡니다. 우선 등식만 부과하지만 구한 해가 비음수인지도 확인하겠습니다. \(x_2=1-x_1\)을 대입하면
따라서 유일한 최소점은 \((2/3,1/3)\)이고 비용은 \(1/3\)입니다. 두 성분이 양수이므로 나중에 비음수 조건을 추가해도 같은 해입니다.
이제 변수를 지우지 않고 등식에 승수 \(\mu\)를 붙입니다. \(L(x,\mu)=f(x)+\mu(x_1+x_2-1)\)의 \(x\) 미분을 0으로 놓으면 \(x_1+\mu=0\), \(2x_2+\mu=0\)입니다. 등식과 합치면
첫째 식에서 \(x_1=2/3\), 둘째에서 \(x_2=1/3\), 마지막에서 합계 1을 다시 얻습니다. 승수의 부호는 등식을 어떤 부호로 썼는지에 의존합니다. 총량을 \(b\)로 바꾸면 최적비용은 \(b^2/3\)이고 도함수는 \(2b/3=-\mu\)입니다. 더 많은 총량을 요구하는 한계비용이 이 부호 규약에서 승수의 음수입니다.
그림 122 전체 직선은 등식 허용집합이고 굵은 선분은 비음수 활동까지 요구한 부분이다. 해는 그 선분 내부에 있다. 가로·세로축은 같은 기준량이며 최소점에서 비용 기울기는 제약 직선에 수직이다.#
2. 기울기들의 관계가 최적조건이 되는 이유#
일반적으로 \(g_i(x)\le0\), \(h_j(x)=0\) 아래 비용 \(f\)를 최소화한다고 합시다. \(g_i(x_*)=0\)인 제약만 활성이라고 부릅니다. 충분히 작은 변화에서 이미 엄격히 음수인 제약은 계속 만족하므로 일차 방향을 제한하는 것은 활성 기울기입니다.
매끄러운 문제에서 적절한 제약자격이 있으면 국소 최소점은
을 만족합니다. 원래 허용조건까지 합친 것이 KKT 조건입니다. \(\nabla f\)의 음수가 활성 부등식 법선의 비음수 결합과 등식 법선의 실수 결합으로 표현된다는 뜻입니다.
제약자격 없이 항상 성립하는 것은 아닙니다. \(\min x\) s.t. \(x^2\le0\)에서는 허용점이 0 하나여서 최소점이지만, \(1+\lambda\cdot0=0\)을 만족하는 승수가 없습니다. 실제 가능한 변화는 0뿐인데 선형화 제약 \(0d\le0\)은 모든 방향을 허용합니다. 제약을 일차식으로 바꾸며 정보를 잃었습니다.
LICQ는 활성 부등식 기울기와 등식 기울기가 모두 일차독립이라는 조건입니다. MFCQ는 등식 기울기가 독립이고 등식을 일차적으로 보존하면서 모든 활성 부등식을 엄격히 줄이는 방향이 존재한다는 조건입니다. LICQ이면 MFCQ이지만 역은 필요하지 않습니다. 볼록 문제의 Slater는 전역의 엄격 허용점 조건으로 O2의 강쌍대성과 연결됩니다. 세 조건은 같은 문장의 다른 이름이 아닙니다.
마지막 절에서는 LICQ에서 국소좌표를 만들어 KKT를 완전히 증명합니다. MFCQ에서의 일반 접원뿔 정리와 비매끄러운 제약자격은 외부 확장으로 구별합니다. 부등식만 있고 제약자격을 가정하지 않으면 Gordan 택일로 Fritz John 조건 \(\lambda_0\nabla f+\sum_i\lambda_i\nabla g_i=0\), \(\lambda_0,\lambda_i\ge0\), 전부 0은 아님을 얻습니다. 앞 반례에서는 \(\lambda_0=0\)인 비정상 승수만 가능합니다.
3. 비용이 볼록해도 KKT 행렬은 양의 정부호가 아니다#
등식 이차계획 \(f(x)=x^THx/2+c^Tx\), \(Ax=b\)의 KKT 행렬은
승수만 바꾸는 방향 \((0,y)\)에서는 이차형식이 0이므로 \(m>0\)이면 양의 정부호일 수 없습니다. \(A\ne0\)이면 \(Az\ne0\)인 \(z\)를 잡고 \((z,ty)\)에 \(y=Az\)를 넣습니다. 이차형식은 \(z^THz+2t\|Az\|^2\)여서 \(t\)를 양·음으로 크게 바꾸면 두 부호가 모두 나옵니다. 즉 실제로 부정치입니다.
이는 최소점이 없다는 뜻이 아닙니다. 실제 가능한 변화 \(d\)는 \(Ad=0\)을 만족합니다. \(Z\)를 \(\ker A\)의 기저행렬로 잡으면 \(d=Zv\)이고 비용의 이차 변화는 \(v^TZ^THZv\)입니다. 최소성에 필요한 것은 허용 변화 위의 축소 헤시안입니다.
첫 예에서 \(Z=(1,-1)^T/\sqrt2\), \(Z^THZ=3/2>0\)입니다. \(K\)의 관성, 즉 양·음·영 고윳값의 개수는 \((2,1,0)\)입니다. \(3\times3\) 행렬의 관성을 \((1,1,0)\)으로 적으면 차원 하나가 사라집니다. 일반적으로 \(A\in\mathbb R^{m\times n}\)이 완전 행계수이면
축소 헤시안이 양의 정부호일 때 전체 관성은 \((n,m,0)\)입니다.
4. 같은 안장점 선형계를 세 가지로 풀기#
널공간법은 허용점 \(x_p\)를 하나 구한 뒤 \(x=x_p+Zz\)로 씁니다. \(Z^T(Hx+c)=0\)이므로
축소 헤시안만 양의 정부호이면 Cholesky를 쓸 수 있습니다. 첫 예에서 \(x_p=(1,0)\), 정규화하지 않은 \(Z=(-1,1)^T\)를 쓰면 \(3z=1\)이므로 \(z=1/3\), \(x=(2/3,1/3)\)입니다.
영역공간법은 \(H\succ0\)인 경우 \(x=-H^{-1}(c+A^T\mu)\)를 등식에 넣어
를 풉니다. 첫 예에서는 \(AH^{-1}A^T=1+1/2=3/2\)여서 \(\mu=-2/3\)입니다. 역행렬을 명시적으로 만들지 않고 \(H\)의 인자를 이용합니다. \(H=LL^T\)이면 Schur 행렬은 \((AL^{-T})(AL^{-T})^T\)여서 이 행렬의 조건수는 \(AL^{-T}\)의 조건수 제곱입니다. 이를 무조건 \(\kappa(H)^2\)라고 바꾸어 쓰면 안 됩니다.
대칭 부정치법은 \(K\) 자체에 피벗 LDL 분해를 적용합니다. \(D\)에는 \(1\times1\) 및 \(2\times2\) 블록이 있으므로 대각 성분만 보고 관성을 세면 안 됩니다. 각 블록의 고윳값 부호를 확인합니다. 아주 작은 계산 고윳값은 엄밀한 부호 인증이 아니라 허용오차 범위의 판단입니다.
import numpy as np
import scipy.linalg as la
def solve_kkt(H,A,c,b,method='null'):
n=H.shape[0]; m=A.shape[0]
if method=='null':
Q,R=la.qr(A.T,mode='full'); Y=Q[:,:m]; Z=Q[:,m:]
xp=Y@la.solve_triangular(R[:m,:].T,b,lower=True)
G=Z.T@H@Z
z=la.cho_solve(la.cho_factor(G),-Z.T@(H@xp+c)) if n>m else np.empty(0)
x=xp+Z@z; mu=la.lstsq(A.T,-H@x-c)[0]
elif method=='range':
factor=la.cho_factor(H)
W=la.cho_solve(factor,A.T); v=la.cho_solve(factor,c)
mu=la.cho_solve(la.cho_factor(A@W),-b-A@v);x=-v-W@mu
elif method=='ldl':
K=np.block([[H,A.T],[A,np.zeros((m,m))]])
rhs=np.r_[-c,b]; lu,D,perm=la.ldl(K,lower=True)
L=lu[perm,:]
y=la.solve_triangular(L,rhs[perm],lower=True,unit_diagonal=True)
z=la.solve(D,y,assume_a='sym')
w=la.solve_triangular(L.T,z,lower=False,unit_diagonal=True)
answer=np.empty(n+m);answer[perm]=w;x=answer[:n];mu=answer[n:]
else: raise ValueError('unknown method')
return x,mu
H=np.diag([1.,2.]); A=np.array([[1.,1.]]); c=np.zeros(2); b=np.ones(1)
for method in ['null','range','ldl']:
x,mu=solve_kkt(H,A,c,b,method)
assert np.allclose(x,[2/3,1/3]) and np.allclose(mu,[-2/3])
assert np.linalg.norm(H@x+c+A.T@mu)+np.linalg.norm(A@x-b)<1e-12
print('세 방법의 원래 KKT 잔차 확인')
세 방법의 원래 KKT 잔차 확인
\(H=\operatorname{diag}(-1,2)\), \(A=(1,0)\), \(b=1\)이라면 \(x_1\)은 고정되고 \(x_2\) 방향의 곡률은 2입니다. \(H\) 자체가 부정치여도 제약 최소점 \((1,0)\)은 유일합니다. 널공간법과 LDL은 가능하지만 위 코드의 Cholesky 영역공간법은 적용 조건을 만족하지 않습니다. 비용·오차 비교는 이 적용 범위를 먼저 맞춰야 합니다.
5. 곡선 제약에서는 비용의 헤시안만 보면 안 된다#
\(f(x_1,x_2)=x_1^2+3x_2\), \(h(x)=x_2+x_1^2=0\)을 생각합시다. 원점에서 등식 기울기는 \((0,1)\)이고 접방향은 \((d,0)\)입니다. 비용만의 헤시안은 \(\operatorname{diag}(2,0)\)여서 접방향에서 양수입니다. 하지만 실제 제약을 대입하면 \(f(x_1,-x_1^2)=-2x_1^2\)이므로 원점은 최대점입니다.
승수는 \(\mu=-3\)이고 Lagrangian 헤시안은 \(\nabla^2f+\mu\nabla^2h=\operatorname{diag}(-4,0)\)입니다. 이 곡률이 실제 제약 경로의 곡률과 일치합니다. 곡선 제약이 경로를 휘게 만드는 항을 빼서는 안 됩니다.
등식제약에서는 독립 기울기 아래 \(Z^T\nabla^2_{xx}LZ\succ0\)가 엄격 국소 최소의 충분조건입니다. 부등식이 있으면 모든 활성 제약을 등식처럼 고정하는 것으로 충분하지 않을 수 있습니다. 비용의 일차변화가 0인 임계원뿔
위의 비영 방향에서 Lagrangian 이차형식이 양수여야 합니다. 엄격 양수 승수가 붙은 활성 제약에는 임계방향에서 등호가 강제되지만 승수 0인 제약에는 그렇지 않습니다.
6. 수요의 대칭성과 음의 곡률을 어디서 얻는가#
소비량 \(x_i>0\), 가격 \(p_i>0\), 지출 \(w>0\)인 모형에서 효용 \(u(x)=\prod_i x_i^{a_i}\), \(a_i>0\), \(\sum_i a_i=1\)을 생각합니다. 수량과 가격은 정한 기준단위를 사용합니다. 로그효용 \(\sum_i a_i\log x_i\)의 일차조건 \(a_i/x_i=\nu p_i\)와 예산 \(p^Tx=w\)에서 \(\nu=1/w\), Marshall 수요 \(x_i=a_iw/p_i\)를 얻습니다.
고정 효용을 얻기 위한 최소지출은
직접 대입하면 \(p^Th=e\)이고 \(\prod h_i^{a_i}=u\)입니다. 고정 지출에서 위 로그효용의 엄격오목성으로 수요가 유일하므로 이 지출·수요가 최적입니다. 미분하면 보상 수요의 Jacobian은
대칭이고 \(Sp=0\)입니다. 임의 \(v\)에 대해
마지막은 양의 가중치 합이 1인 Cauchy–Schwarz입니다. 등호는 모든 \(v_i/p_i\)가 같을 때뿐이므로 영공간은 가격 방향이고 계수는 \(n-1\)입니다. \(a_i=1/3,p_i=1,w=3\)인 세 재화에서는 \(S=\frac13\mathbf1\mathbf1^T-I\), 고윳값은 \(0,-1,-1\)입니다.
그림 123 가격 벡터 \((1,1,1)\)에 평행한 변화와 그 수직평면의 두 방향을 구별한다. 그래프는 기준점의 국소 이차형식이며 유한한 가격변화 전체의 수요를 대신하지 않는다.#
일반적으로 지출함수는 같은 효용 이상을 주는 소비묶음들의 선형 가격비용 하한이므로 가격에 대해 오목합니다. 유일한 최적 소비가 가격에 연속이면 양쪽 최적값 비교로 Shephard 식 \(\nabla_pe=h\)를 얻고, \(C^2\)이면 \(D_ph\)는 대칭 음의 준정부호입니다. 또 \(h(p,u)=x(p,e(p,u))\)를 미분하면 \(D_ph=D_px+(D_wx)h^T\)입니다. 현재 효용에서 \(h=x\)이므로 이것이 Slutsky 식입니다.
이는 가격공간의 보상반응 성질입니다. 소비공간의 효용제약 접공간에 대한 축소 헤시안과 연결되지만 같은 행렬이라고 동일시하지 않습니다. 임의 추정 수요로부터 효용을 복원하는 적분가능성은 정의역·정칙성·전역조건이 추가되는 외부 이론입니다.
7. 신뢰영역은 부정치 비용도 전역적으로 풀 수 있다#
현재 점 주변의 이차 모형 \(m(p)=g^Tp+p^THp/2\)를 반지름 \(\Delta>0\) 안에서 최소화합니다. \(H\)는 대칭이며 양의 정부호일 필요가 없습니다. 전역해의 조건은 어떤 \(\lambda\ge0\)에 대해
입니다. 마지막 상보성을 빠뜨리면 충분조건도 되지 않습니다. 예를 들어 \(H=0\), \(g=1\), \(\Delta=2\), \(\lambda=1\), \(p=-1\)은 첫 세 조건을 만족하지만 최적점은 \(-2\)입니다.
고유좌표에서는 \(p_i(\lambda)=-g_i/(h_i+\lambda)\)입니다. \(\lambda>\max(0,-h_{\min})\)에서 제곱노름은 연속·비증가이고 \(g\ne0\)이면 엄격 감소합니다. 경계에서 노름이 반지름보다 크면 \(\|p(\lambda)\|=\Delta\)인 유일한 근을 찾으면 됩니다.
어려운 경우는 \(g\)가 최소 고유공간과 직교하여 경계 분모가 0이어도 해당 분자가 0인 때입니다. \(H=\operatorname{diag}(-1,2)\), \(g=(0,2)\), \(\Delta=2\)이면 경계 \(\lambda=1\)에서 \(p_\perp=(0,-2/3)\)이고 노름은 반지름보다 작습니다. 더 큰 \(\lambda\)로 가면 노름이 더 작아져 경계방정식의 근이 없습니다. 대신
로 영방향을 보충하면 길이가 2이고 비용은 \(-8/3\)입니다. 이것이 hard case입니다. 최소 고윳값이 음수라는 조건, 직교성, 경계해의 노름을 함께 확인합니다. 양의 준정부호 문제의 내부해를 억지로 경계까지 늘릴 필요는 없습니다.
그림 124 왼쪽 원 안만 허용되며 두 최소점이 같은 비용을 갖는다. 오른쪽은 \(\lambda>1\)에서 일반 역으로 계산한 해의 노름이다. 그 곡선이 반지름 2에 도달하지 않는 것이 영방향 보충이 필요한 이유이다.#
Hhard=np.diag([-1.,2.]); ghard=np.array([0.,2.]); Delta=2.
phard=np.array([4*np.sqrt(2)/3,-2/3]); lam=1.
assert np.allclose((Hhard+lam*np.eye(2))@phard,-ghard)
assert np.isclose(np.linalg.norm(phard),Delta)
assert np.isclose(.5*phard@Hhard@phard+ghard@phard,-8/3)
assert np.min(la.eigvalsh(Hhard+lam*np.eye(2)))>=0
print('hard case의 정상성·곡률·상보성 확인')
hard case의 정상성·곡률·상보성 확인
8. 정칙화와 강건성은 어떤 조건에서 연결되는가#
최소제곱 모형에서는 \(H=X^TX\), \(g=-X^Ty\)이고 이동방정식은 \((X^TX+\lambda I)\beta=X^Ty\)입니다. 능형회귀, 반지름 제약 최소제곱, Gauss–Newton 단계의 Levenberg–Marquardt 이동은 이 대수적 계를 공유할 수 있습니다. 그러나 계수벡터와 현재점의 보정량은 다른 변수이고, 정칙화 계수와 신뢰영역 반지름의 대응도 상보성과 활성 여부에 의존합니다.
설계행렬 오차의 스펙트럼노름을 \(\|E\|_2\le\rho\)로 제한하면 정확히
상한은 삼각부등식입니다. \(r=y-X\beta\ne0\), \(\beta\ne0\)이면 \(E=-\rho(r/\|r\|)(\beta/\|\beta\|)^T\)가 등호를 만듭니다. 둘 중 하나가 0인 경우도 직접 확인합니다. 따라서 강건 문제는 두 노름의 합을 최소화하며 고정된 두 제곱노름의 합과 같은 목적함수가 아닙니다.
비영 해와 비영 잔차에서는 일차조건을 정리하여 \((X^TX+\lambda I)\beta=X^Ty\), \(\lambda=\rho\|r\|/\|\beta\|\)를 얻습니다. 이 해 의존적 대응이 성립하는 범위에서 능형해와 연결됩니다. 영 해, 정확 적합, 비활성 반지름에서는 별도 준미분 조건이 필요합니다. 측정오차 모형의 확률적 편의 교정까지 이 항등식이 제공하는 것은 아닙니다.
비교정태는 KKT를 모수에 대해 미분하여 같은 \(K\)로 푸는 작업입니다. \(K\)의 관성만으로 모든 반응 성분의 부호가 정해지지는 않습니다. 경계 헤시안의 고전적인 선행 행렬식 규칙도 제약·변수 순서와 독립 피벗 조건을 갖습니다. 축소 좌표에서 \(AY=I\)로 정렬하면 경계블록 행렬식은 \((-1)^m\det H_{\rm red}\)가 되어 축소 Sylvester 판정을 번역할 수 있지만, 임의 원래 순서의 모든 선행 행렬식에 같은 규칙을 적용하지 않습니다.
9. 연습과 전체 풀이#
1. 첫 문제의 총량을 3으로 바꾸세요.
풀이. \(x_1=-\mu\), \(x_2=-\mu/2\)이므로 \(-3\mu/2=3\), \(\mu=-2\)이고 \(x=(2,1)\)입니다. 비용은 \((4+2)/2=3\)으로 \(b^2/3\)과 같습니다.
2. \(H=\operatorname{diag}(-1,2)\), \(x_1=1\)에서 최소점과 관성을 구하세요.
풀이. 허용 비용은 \(-1/2+x_2^2\)라 \(x_2=0\)입니다. 축소 헤시안은 2이고 \(n=2,m=1\)이므로 관성 정리에서 \((2,1,0)\)입니다. \(H\)의 음의 방향은 제약으로 제거되었습니다.
3. \(\min x\) s.t. \(x^2\le0\)의 Fritz John 승수를 구하세요.
풀이. 원점에서 \(\lambda_0\cdot1+\lambda_1\cdot0=0\)이므로 \(\lambda_0=0\), \(\lambda_1=1\)을 고를 수 있습니다. 정상 KKT의 \(\lambda_0=1\)로 정규화할 수 없습니다.
4. 곡선 제약 예에서 목적함수를 \(4x_1^2+3x_2\)로 바꾸면 어떻게 되나요?
풀이. 허용 비용은 \(x_1^2\)라 원점이 엄격 최소점입니다. 승수는 여전히 \(-3\)이고 접방향 Lagrangian 곡률은 \(8-6=2>0\)입니다.
5. 세 재화 기준점에서 \(v=(1,-1,0)\)에 대한 보상 반응을 구하세요.
풀이. 성분합이 0이라 \(Sv=-v=(-1,1,0)\)입니다. 이차형식은 \(v^TSv=-2\)입니다. 반면 \(v=(1,1,1)\)이면 \(Sv=0\)입니다.
6. hard case에서 부호 두 개가 모두 해인 이유를 확인하세요.
풀이. \(g_1=0\)이고 목적함수는 첫 좌표의 제곱에만 의존합니다. \(p_1\) 부호를 바꾸어도 정상성·길이·비용이 같습니다. 이는 승수가 1이어도 보정해가 유일하지 않을 수 있음을 보입니다.
7. \(\min p\) s.t. \(|p|\le2\)에서 올바른 신뢰영역 승수는 무엇인가요?
풀이. 해는 \(p=-2\)이고 \((0+\lambda)p=-1\)에서 \(\lambda=1/2\)입니다. \(\lambda>0\)이며 경계에 있으므로 상보성도 만족합니다. \(p=-1,\lambda=1\)은 경계 조건을 위반합니다.
8. \(X=1,y=2\)인 강건 최소제곱 \(|2-\beta|+\rho|\beta|\)의 \(0<\rho<1\) 해를 구하세요.
풀이. \(0\le\beta\le2\)에서는 \(2-(1-\rho)\beta\)라 감소합니다. \(\beta>2\)에서는 \((1+\rho)\beta-2\)라 증가하고 음수 구간에서도 0으로 갈수록 감소합니다. 해는 정확 적합 \(\beta=2\)입니다. 고정 양수 능형계수의 해 \(2/(1+\lambda)\)와 같지 않으며, 비영 잔차를 가정한 대응식의 경계 사례입니다.
10. 지금까지의 내용을 수학의 언어로 정리해 봅시다#
관성은 대칭행렬의 양·음·영 고윳값 개수를 그 순서로 기록합니다. 국소 제약좌표를 만드는 데에는 C6와 같은 유한차원 역함수정리를 출발 전제로 사용합니다.
정리 1. LICQ 아래 KKT와 볼록 문제의 충분성#
\(C^1\) 목적함수·제약의 국소 최소점에서 LICQ가 성립하면 KKT 승수가 존재하며 활성 승수 표현은 유일합니다. 볼록 목적·볼록 부등식·아핀 등식에서는 KKT가 전역 최소의 충분조건입니다.
증명. 활성 부등식 수를 \(a\), 등식 수를 \(m\)이라 합시다. 독립 기울기들을 추가 선형좌표로 완성하여 \(\Phi(x)=(g_1(x),\ldots,g_a(x),h_1(x),\ldots,h_m(x),\ell(x))\)의 Jacobian을 가역으로 만듭니다. 역함수정리로 근방의 좌표를 \((u,v,w)\)로 바꿀 수 있습니다. 허용조건은 정확히 \(u\le0,v=0\)이며 비활성 부등식은 근방에서 그대로 엄격 음수입니다.
최소점에서 자유 \(w\) 미분은 0, \(u_i\)의 음의 방향 미분은 비음수이므로 \(\partial f/\partial u_i\le0\)입니다. \(\lambda_i=-\partial f/\partial u_i\ge0\), \(\mu_j=-\partial f/\partial v_j\)로 두고 연쇄법칙을 원래 좌표로 돌리면 정상성입니다. 비활성 승수는 0으로 둡니다. 독립성 때문에 표현은 유일합니다.
Farkas 관점도 같은 내용을 줍니다. 이 좌표로 실현되는 선형화 방향들에는 비용의 음의 일차변화가 없습니다. 활성 기울기와 등식의 양·음 기울기가 생성하는 닫힌 원뿔에 \(-\nabla f\)가 없으면 O2의 분리로 \(\nabla g_i^Td\le0\), \(Dh\,d=0\), \(\nabla f^Td<0\)인 방향이 생깁니다. 이는 최소성과 모순이므로 같은 승수 표현이 나옵니다.
볼록 문제에서 Lagrangian은 \(x\)에 대해 볼록이고 정상성 때문에 \(x_*\)에서 전역 최소입니다. 임의 허용 \(x\)에 \(f(x)\ge L(x,\lambda,\mu)\ge L(x_*,\lambda,\mu)=f(x_*)\)입니다. 마지막은 허용성과 상보성입니다. ∎
정리 2. KKT 관성과 축소 이차계획#
\(A\)가 완전 행계수이고 \(Z\)가 영공간 기저이면 3절의 관성식이 성립합니다. \(Z^THZ\succ0\)이면 등식 이차계획은 모든 비어 있지 않은 허용집합에서 유일한 최소점을 갖고 KKT는 가역입니다.
증명. \(AY=I_m\)인 \(Y\)를 택하면 \([Z,Y]\)는 가역입니다. \(x=Zu+Yv\)를 KKT 이차형식에 대입하면
\(\nu=\mu+C^Tu+Dv/2\)로 가역변환하면 \(u^TRu+2v^T\nu\)가 됩니다. 뒤 부분은 \((v+\nu)/\sqrt2,(v-\nu)/\sqrt2\) 좌표에서 제곱노름의 차여서 관성이 \((m,m,0)\)입니다. 앞 \(R\)이 특이해도 이 변환은 유효합니다. 합동 관성법칙으로 식이 나옵니다.
허용 \(x=x_p+Zu\)의 목적함수는 양의 정부호 이차항 \(u^TRu/2\)와 일차항·상수입니다. 완전제곱으로 유일 최소점이 존재합니다. 관성식에서 영 고윳값이 없어 KKT도 가역입니다. 특히 KKT 역행렬의 좌상단은 \(ZR^{-1}Z^T\)입니다. 우변 변화 \((v,0)\)에는 \(dx=Zdu\), \(Rdu=Z^Tv\)로 풀리기 때문입니다. 통계적 공분산으로 해석하려면 점수의 분산 등 별도 모형 가정이 더 필요합니다. ∎
정리 3. 임계원뿔 위 이차 충분조건#
\(C^2\) 제약문제의 KKT점에서 Lagrangian 헤시안이 임계원뿔의 모든 비영 방향에 양의 값을 주면 엄격 국소 최소점입니다.
증명. 그렇지 않으면 서로 다른 허용점 \(x_k\to x_*\)에 \(f(x_k)\le f(x_*)\)가 있습니다. \(t_k=\|x_k-x_*\|\), \(d_k=(x_k-x_*)/t_k\)의 부분수열이 단위 \(d\)로 수렴합니다. 허용성의 일차 전개로 \(Dh\,d=0\), 활성 \(\nabla g_i^Td\le0\)입니다. 비용 부등식은 \(\nabla f^Td\le0\)을 주지만 KKT는 \(\nabla f^Td=-\sum_i\lambda_i\nabla g_i^Td\ge0\)을 줍니다. 따라서 \(d\)는 임계원뿔에 있습니다.
고정 승수에서 허용점의 \(L(x_k)\le f(x_k)\le f(x_*)=L(x_*)\)입니다. \(\nabla_xL(x_*)=0\)인 Taylor 전개를 \(t_k^2/2\)로 나누어 극한을 취하면 \(d^T\nabla^2L(x_*)d\le0\)이므로 가정과 모순입니다. 등식만 있는 경우 임계원뿔은 접공간이고 축소 헤시안 조건으로 돌아갑니다. ∎
정리 4. 신뢰영역 전역해의 필요충분조건과 hard case#
대칭 \(H\), \(\Delta>0\)에서 7절 네 조건은 전역 최소의 필요충분조건입니다.
증명. 네 조건을 만족하는 \(p,\lambda\)와 허용 \(q\)에 대해 직접 전개하면
첫 항은 PSD이고, 둘째는 \(\lambda=0\)이거나 \(\|p\|=\Delta\ge\|q\|\)여서 비음수입니다. 충분성이 증명됩니다.
필요성은 먼저 증명서를 가진 해가 항상 존재함을 보입니다. \(H=Q\operatorname{diag}(h_i)Q^T\), \(a=Q^Tg\), \(\lambda_0=\max(0,-\min h_i)\)라 놓습니다. \(\lambda>\lambda_0\)에서는 \(z_i(\lambda)=-a_i/(h_i+\lambda)\)이고 노름이 0으로 감소합니다. \(\lambda\downarrow\lambda_0\)에서 극한 노름이 \(\Delta\)보다 크면 연속성으로 유일한 경계 근이 있습니다. 무한 극한도 포함합니다.
극한 노름이 \(\Delta\) 이하이면 영 분모에 해당하는 \(a_i\)는 모두 0이어야 합니다. 비영 분모만 나누어 \(z_\perp\)를 만듭니다. \(\lambda_0=0\)이면 이 점을 그대로 사용합니다. \(\lambda_0>0\)이면 최소 고유공간에서 길이 \(\sqrt{\Delta^2-\|z_\perp\|^2}\)인 벡터를 더합니다. 두 경우 모두 네 조건을 만족합니다. 따라서 앞 충분성으로 전역해 하나가 확보됩니다.
임의의 다른 전역해 \(q\)는 위 차이식의 두 비음수 항을 모두 0으로 만듭니다. PSD 이차형식이 0이면 \((H+\lambda I)(q-p)=0\)이므로 정상성을 공유하고, \(\lambda>0\)이면 길이도 \(\Delta\)입니다. 따라서 같은 \(\lambda\)로 네 조건을 만족하여 모든 전역해의 필요성까지 얻습니다. 이 증명은 하나의 구 제약의 고유좌표 구조를 사용했으며 일반 비볼록 제약문제의 강쌍대성을 주장하지 않습니다. ∎
정리 5. 지출함수의 곡률과 Slutsky 식#
유일하고 연속인 보상수요가 존재하고 지출함수가 \(C^2\)인 양의 가격 영역에서, 지출함수는 오목·1차 동차이고 \(\nabla_pe=h\), \(S=D_ph\)는 대칭 음의 준정부호이며 \(Sp=0\)입니다.
증명. 효용 하한의 허용집합은 가격과 무관합니다. 각 허용 소비의 가격비용은 선형이므로 그 하한 \(e\)는 오목합니다. 양의 가격 배율 \(t\)를 목적함수 밖으로 빼면 \(e(tp,u)=te(p,u)\)입니다. 최적묶음 비교에서
연속성으로 두 선형항의 차이가 \(o(\|d\|)\)이므로 미분은 \(h\)입니다. 두 번 미분가능한 오목함수의 헤시안은 대칭 NSD입니다. 가격을 양의 배율로 바꾸어도 최소 소비묶음은 같고 유일하므로 \(h(tp,u)=h(p,u)\)입니다. \(t\)를 1에서 미분하면 \(Sp=0\)입니다. 끝으로 \(h(p,u)=x(p,e(p,u))\)의 연쇄법칙과 \(\nabla_pe=h\)를 적용하면 Slutsky 식을 얻습니다. ∎
실제 계산에서 구별한 것 |
수학적 조건 |
|---|---|
허용 변화에서 비용이 커진다 |
축소 헤시안 또는 임계원뿔 |
비용과 제약을 한꺼번에 푼다 |
대칭 부정치 KKT 시스템 |
구 안의 비볼록 이차식을 전역적으로 푼다 |
PSD 이동·정상성·상보성 |
가격 배율과 가격비의 반응이 다르다 |
\(Sp=0\)와 수직 방향의 음의 곡률 |
KKT 조건은 가정에 따라 필요조건 또는 충분조건이 되며, 이차 조건이 그 역할을 보강합니다. 다음 장에서는 이 조건들을 실제로 만족시키는 점을 찾는 반복 알고리즘을 비교합니다. O4로 이어 읽기.