O4 · 경사·Newton·준Newton·근접 계산의 내부

1. 같은 비용을 얼마나 적은 반복으로 줄일 수 있을까

O1의 두 활동 비용을 합·차 좌표로 바꾸면 \(f(z)=\frac12(z_1^2+9z_2^2)\)입니다. 원래 최소점 \((1,1)\)에서의 편차를 나타내는 무차원 좌표이고, \(z_2\) 방향의 변화는 \(z_1\)보다 아홉 배 큰 곡률을 가집니다. 이번에는 그 최소점을 찾는 계산을 직접 비교합니다.

\(z_0=(1,1/9)\)에서 기울기는 \((1,1)\)입니다. 기울기의 반대 방향으로 \(z_1=z_0-\alpha\nabla f(z_0)\)를 움직일 때

\[ \alpha=\frac{g^Tg}{g^THg}=\frac2{10}=\frac15,\qquad z_1=(4/5,-4/45),\quad g_1=(4/5,-4/5). \]

다음 보폭도 \(1/5\)이고 \(z_2=(16/25,16/225)\)입니다. 큰 곡률 방향의 부호가 번갈아 바뀝니다. 처음 비용은 \(5/9\), 첫 비용은 \(16/45\), 둘째는 \(256/1125\)이며 매번 비용비는 \(16/25=(4/5)^2\)입니다. 이는 조건수 9의 최악비율에 실제로 도달하는 시작점입니다. 모든 시작점에서 반드시 이 비율이 나오지는 않습니다.

그림 125 왼쪽은 같은 비율 눈금의 두 편차 좌표, 오른쪽은 초기 비용으로 나눈 값의 로그 눈금이다. 이 시작점은 최악비율의 등호 사례로 선택했다. 일반 실험의 감소율을 이 직선에 맞추지 않는다.

2. 보폭을 고정할 때와 직선 위에서 최적화할 때

\(mI\preceq H\preceq LI\)인 이차함수에서 고정 보폭 오차는 \(e_{k+1}=(I-\alpha H)e_k\)입니다. 최악 고유방향의 배율은 \(\max_{\lambda\in[m,L]}|1-\alpha\lambda|\)이고, 최적 보폭 \(2/(L+m)\)에서는 \((L-m)/(L+m)\)입니다. 비용은 오차의 제곱이라 감소 상한에 그 제곱이 붙습니다.

정확 직선탐색은 매번 현재 방향에서 최적인 \(\alpha_k=(g_k^Tg_k)/(g_k^THg_k)\)를 고릅니다. 그때도

\[ f(x_{k+1})-f_*\le\left(\frac{\kappa-1}{\kappa+1}\right)^2(f(x_k)-f_*),\qquad\kappa=L/m \]

가 성립합니다. 마지막 절에서 Kantorovich 부등식까지 증명하여 상수를 확인합니다. 보폭이 고정된다는 사실과 최악 수축상한이 같다는 사실은 다른 주장입니다.

앞 반복들의 정보를 사용하면 다른 오차 다항식을 만들 수 있습니다. N8의 Chebyshev 논법은 차수 \(k\)의 \(q_k(0)=1\)인 다항식으로 \([m,L]\) 전체를 억제하여 \(2((\sqrt\kappa-1)/(\sqrt\kappa+1))^k\)의 에너지 노름 상한을 줍니다. 그래서 이차 문제에서는 반복 수가 \(\kappa\) 대신 \(\sqrt\kappa\) 규모로 줄어들 수 있습니다. 이는 고정 SPD 이차식의 결과입니다. 일반 비선형 Nesterov 방법의 증명은 추정수열 등 추가 논법을 요구하며 모든 비선형 궤적을 하나의 고정행렬 다항식으로 바꿀 수는 없습니다. 일반 일차 oracle 하한도 허용 알고리즘·차원·함수군의 조건이 있는 외부 결과입니다.

3. 곡률로 나누어 움직이는 Newton 단계

현재점의 이차 모형 \(f(x)+g^Tp+p^THp/2\)에서 \(H\succ0\)이면 최소 보정은 \(Hp=-g\)입니다. 이차함수에서는 이것이 정확한 최적점까지의 변화라 한 단계로 끝납니다. 일반 함수에서는 국소 모형이므로 보폭 조절이나 신뢰영역이 필요할 수 있습니다.

Newton 감소량을 \(\delta(x)^2=g^TH^{-1}g\)로 정의하면 이차 모형에서 얻는 감소는 \(\delta^2/2\)입니다. 이것을 실제 함수의 전역 최적값 차이라고 무조건 해석하지 않습니다. 같은 점의 기울기노름은 좌표 단위에 따라 바뀌지만 감소량은 가역 아핀변환에서 같습니다.

예를 들어 \(H=\operatorname{diag}(1,9)\), \(x=(1,1/9)\)에서는 \(g=(1,1)\), \(\delta^2=1+1/9=10/9\)입니다. \(x=By\), \(B=\operatorname{diag}(10,1)\)로 바꾸면 새 기울기는 \((10,1)\), 새 헤시안은 \(\operatorname{diag}(100,9)\)이고 감소량은 여전히 \(100/100+1/9=10/9\)입니다.

헤시안이 부정치면 Newton 방향이 상승방향일 수 있습니다. \(H=\operatorname{diag}(-1,2)\), \(g=(1,0)\)에서는 \(p=(1,0)\)이고 \(g^Tp=1>0\)입니다. \(H+\tau I\succ0\)가 되게 \(\tau>1\)로 이동하면 \(g^Tp=-g^T(H+\tau I)^{-1}g<0\)입니다. 대각 이동과 수정 Cholesky는 이런 양의 곡률 보정을 만드는 전략입니다. 특정 Gill–Murray 구현의 섭동 최소성이나 오차 상한을 임의의 이동법에 부여하지 않습니다. 희소 구조·피벗·목표 최소곡률에 따라 실제 수정량이 달라집니다.

4. Gauss–Newton이 생략한 항

잔차벡터 \(r(x)\)를 맞추는 \(f(x)=\frac12\sum_i r_i(x)^2\)의 기울기와 헤시안은

\[ \nabla f=J^Tr,\qquad \nabla^2f=J^TJ+\sum_i r_i\nabla^2r_i. \]

Gauss–Newton은 잔차의 선형화만 사용하여 두 번째 항을 생략합니다. 잔차가 작고 잔차의 이차미분이 제한되면 그 항이 작을 수 있습니다. 잔차가 크거나 Jacobian이 계수를 잃으면 결론이 달라집니다.

스칼라 \(r(x)=x^2-1\)에서는 \(J=2x\), \(J^TJ=4x^2\), 실제 헤시안은 \(6x^2-2\)입니다. 원점에서는 근사곡률이 0인 반면 실제 곡률은 \(-2\)입니다. \(x=1/2\)에서는 실제 기울기 \(2x(x^2-1)=-3/4\), Gauss–Newton 보정은 \(3/4\)이고 새 점은 \(5/4\)입니다. 이는 선형화가 만든 단계이며 무조건 최적 보폭은 아닙니다. Levenberg–Marquardt는 \(J^TJ+\lambda I\)를 사용해 이 보정을 제한하며 O3의 이동계와 연결됩니다.

5. 새 기울기 차이로 곡률을 갱신하기

두 점의 차이를 \(s=x_{k+1}-x_k\), 기울기 차이를 \(y=g_{k+1}-g_k\)라 씁니다. 이차함수에서는 정확히 \(y=Hs\)입니다. 전체 헤시안을 다시 구하지 않고 근사행렬 \(B\)를 새로 바꿔 \(B_+s=y\)를 만족시키려는 것이 시컨트 조건입니다.

BFGS 갱신은

\[ B_+=B-\frac{Bss^TB}{s^TBs}+\frac{yy^T}{s^Ty}. \]

\(B\succ0\), \(s^Ty>0\)에서 정의되며 양의 정부호를 보존합니다. \(B=I\), \(s=(1,0)\), \(y=(2,1)\)이면

\[\begin{split} B_+=\begin{pmatrix}2&1\\1&3/2\end{pmatrix},\qquad B_+s=y,\qquad\det B_+=2>0. \end{split}\]

\(y=(-1,0)\)으로 바꾸면 \(s^Ty<0\)이고 결과는 \(\operatorname{diag}(-1,1)\)입니다. 조건을 빼고 양의 정부호라고 할 수 없습니다.

하강방향 \(p\)와 \(s=\alpha p\), \(\alpha>0\)에서 Wolfe 곡률 조건 \(g_{k+1}^Tp\ge c_2g_k^Tp\), \(0<c_2<1\)은 \(s^Ty\ge\alpha(c_2-1)g_k^Tp>0\)를 보장합니다. 값이 너무 작거나 비양수일 때의 감쇠·생략은 실제 구현의 선택이며 수학적 분모를 그대로 나누어서는 안 됩니다.

BFGS는 변화가 작은 행렬을 선택한다는 변분 해석도 있습니다. 다만 임의의 가중 Frobenius 거리 최소화라고 쓰면 다른 갱신식이 나옵니다. 여기서는 다음 로그 행렬식 발산의 정확한 최소화 문제를 사용합니다.

\[ \min_{X\succ0,\ Xs=y} \operatorname{tr}(B^{-1}X)-\log\det(B^{-1}X)-n. \]

마지막 절에서 이 문제의 유일한 해가 위 BFGS임을 블록 완전제곱으로 보입니다. 역헤시안 \(G=B^{-1}\)의 갱신은 \(\rho=1/(s^Ty)\)에

\[ G_+=(I-\rho sy^T)G(I-\rho ys^T)+\rho ss^T \]

입니다. 앞 식과 곱하여 역 관계와 \(G_+y=s\)를 확인할 수 있습니다. 일반 초선형 수렴의 Dennis–Moré 조건은 함수의 정칙성·수렴 중인 반복·보폭 조건과 함께 사용하는 외부 정리이며 이 한 단계의 대수와 구별합니다.

6. L-BFGS는 큰 행렬 대신 최근 변화쌍을 저장한다

최근 \(m\)개의 \((s_i,y_i)\)와 초기 \(G_0=\gamma I\)만 저장해도 위 역갱신을 벡터에 적용할 수 있습니다. 먼저 뒤에서 앞으로 \(q\leftarrow q-\alpha_i y_i\), \(\alpha_i=\rho_i s_i^Tq\)를 수행합니다. 다음 \(r=G_0q\)를 구하고 앞에서 뒤로 \(r\leftarrow r+s_i(\alpha_i-\rho_i y_i^Tr)\)를 수행합니다. 두 방향의 순서가 서로 반대라는 점이 핵심입니다.

import numpy as np
import scipy.linalg as la

def lbfgs_apply(v,pairs,gamma=1.):
    q=np.array(v,dtype=float,copy=True); alpha=[]
    for s,y in reversed(pairs):
        sy=s@y
        if sy<=0: raise ValueError('양의 곡률쌍이 필요합니다')
        a=(s@q)/sy;alpha.append(a);q-=a*y
    r=gamma*q
    for (s,y),a in zip(pairs,reversed(alpha)):
        r+=s*(a-(y@r)/(s@y))
    return r

H=np.array([[2.,1.],[1.,3.]])
pairs=[(np.array([1.,0.]),H[:,0]),(np.array([0.,1.]),H[:,1])]
G=np.eye(2)
for s,y in pairs:
    rho=1/(s@y);V=np.eye(2)-rho*np.outer(s,y)
    G=V@G@V.T+rho*np.outer(s,s)
v=np.array([2.,-1.])
assert np.allclose(lbfgs_apply(v,pairs),G@v)
assert np.min(la.eigvalsh(G))>0
print('두 루프와 명시적 역갱신의 곱 일치')

두 루프와 명시적 역갱신의 곱 일치

각 변화쌍에서 내적과 벡터 갱신만 하므로 저장과 비용은 \(O(mn)\)입니다. 최근 \(m\)쌍만 사용하는 방식은 그 쌍들을 현재 \(G_0\)에서 다시 적용한 행렬에 해당합니다. 전체 BFGS 역행렬의 일부 행·열을 잘라낸 것과 같지 않습니다. Sherman–Morrison–Woodbury는 이러한 rank-two 역갱신의 대수적 근거를 제공하며, 두 루프의 정확한 순서는 마지막 절에서 직접 유도합니다.

7. 절댓값 벌점을 붙이면 가까운 최적점을 구한다

미분가능하지 않은 볼록 벌점 \(g\)에는

\[ \operatorname{prox}_{\tau g}(v) =\arg\min_x\left(g(x)+\frac1{2\tau}\|x-v\|^2\right),\qquad\tau>0 \]

를 사용합니다. \(g\)가 proper·닫힌·볼록이면 해가 하나 존재합니다. \(g=\delta_C\)일 때는 O1의 집합 사영입니다.

\(g(x)=\lambda\|x\|_1\)이면 좌표별로 문제를 나눕니다. 양수 해에서는 \(\lambda+(x-v)/\tau=0\)이므로 \(x=v-\tau\lambda>0\)이고, 음수 해에서는 \(-\lambda+(x-v)/\tau=0\)이므로 \(x=v+\tau\lambda<0\)입니다. 원점은 \(v\in[-\tau\lambda,\tau\lambda]\)일 때 최적입니다. 따라서

\[ x_i=\operatorname{sign}(v_i)\max(|v_i|-\tau\lambda,0) \]

인 소프트 임계값을 얻습니다. \(v=(2,-1/2,-3)\), \(\tau\lambda=1\)이면 \((1,0,-2)\)입니다. 성분을 0으로 만드는 일이 근사적인 휴리스틱이 아니라 이 최적문제의 정확해입니다.

그림 126 가로축은 입력 \(v\), 세로축은 연산 결과이다. 소프트 임계는 벌점의 근접연산이고 구간으로 자르는 사영과 다르다. 점선 \(x=v\)는 입력을 그대로 보존하는 기준이다.

자주 쓰는 사영의 공식도 원래 최소화 문제에서 얻습니다.

집합 또는 벌점	결과와 필요한 조건
상자 \(l_i\le x_i\le u_i\)	\(\min(u_i,\max(l_i,v_i))\), \(l_i\le u_i\)
단체 \(x\ge0,\sum x_i=a\)	\(x_i=\max(v_i-\theta,0)\), 합을 \(a>0\)로 맞춤
\(\ell_1\) 공 $\sum	x_i
대칭 PSD 원뿔	\(V\operatorname{diag}(\max(\lambda_i,0))V^T\), Frobenius 거리
핵노름 벌점 \(\tau|X|_*\)	같은 특이벡터에 \(\max(\sigma_i-\tau,0)\) 적용

단체의 문턱은 정렬한 \(v_{(1)}\ge\cdots\ge v_{(n)}\)에서 \(\theta_j=(\sum_{i\le j}v_{(i)}-a)/j\)를 만들고 \(v_{(j)}>\theta_j\)인 마지막 \(j\)로 정합니다. 활성 좌표의 합과 나머지 0이라는 조건을 동시에 맞춥니다.

def simplex_projection(v,total=1.):
    v=np.asarray(v,dtype=float)
    if total<=0: raise ValueError('양의 총량이 필요합니다')
    u=np.sort(v)[::-1]; theta=(np.cumsum(u)-total)/np.arange(1,len(v)+1)
    j=np.flatnonzero(u>theta)[-1]
    return np.maximum(v-theta[j],0)

v=np.array([.8,.4,-.1]);p=simplex_projection(v)
assert np.allclose(p,[.7,.3,0.])
soft=lambda x,t:np.sign(x)*np.maximum(np.abs(x)-t,0)
v2=np.array([2.,-.5,-3.])
assert np.allclose(soft(v2,1)+np.clip(v2,-1,1),v2)
print('단체 사영과 절댓값의 Moreau 분해 확인')

단체 사영과 절댓값의 Moreau 분해 확인

O2의 켤레를 사용하면 일반적으로

\[ v=\operatorname{prox}_{\tau g}(v) +\tau\operatorname{prox}_{g^*/\tau}(v/\tau) \]

입니다. \(g=\delta_K\)인 닫힌 볼록원뿔에서는 \(g^*=\delta_{K^\circ}\)이므로 \(v=P_K(v)+P_{K^\circ}(v)\)입니다. 비음수 내적으로 정의한 쌍대 \(K^*\)를 쓰면 \(v=P_K(v)-P_{K^*}(-v)\)입니다. \(\mathbb R_+\)에서 음수 입력을 대입하면 부호를 잘못 쓴 식을 즉시 발견할 수 있습니다.

8. lasso 경로와 반복에서 재사용하는 분해

두 회귀계수가 각각 목표값 2와 \(1/2\)에 가까워지도록

\[ F_\lambda(\beta)=\tfrac12(\beta_1-2)^2+(\beta_2-\tfrac12)^2 +\lambda(|\beta_1|+|\beta_2|),\qquad\lambda\ge0 \]

를 최소화합니다. 좌표마다 앞 절을 적용하면

\[ \beta_1(\lambda)=\max(2-\lambda,0),\qquad \beta_2(\lambda)=\max(\tfrac12-\tfrac\lambda2,0). \]

경로는 \(\lambda=2\)에서 첫 계수가, \(\lambda=1\)에서 둘째가 0으로 바뀌는 조각별 직선입니다. 일반 설계에서도 활성집합 \(J\)와 부호 \(s_J\)를 고정하고 \(X_J\)가 완전 열계수이면

\[ \beta_J(\lambda)=(X_J^TX_J)^{-1}(X_J^Ty-\lambda s_J). \]

이 구간은 비영 계수의 부호가 유지되고 비활성 상관의 절댓값이 \(\lambda\) 이하인 동안입니다. 계수가 0에 도달하는 이탈, 비활성 상관이 경계에 닿는 진입에서 식이 바뀝니다. 중복 열·동시 진입에서는 해가 유일하지 않을 수 있어 일반적인 단일 LARS 경로를 조건 없이 주장하지 않습니다.

ADMM은 \(\beta=z\)를 추가하여 매 반복 다음을 계산합니다.

\[ (X^TX+\rho I)\beta^{k+1}=X^Ty+\rho(z^k-u^k),\quad z^{k+1}=\operatorname{soft}(\beta^{k+1}+u^k,\lambda/\rho), \]

\[ u^{k+1}=u^k+\beta^{k+1}-z^{k+1},\qquad\rho>0. \]

같은 \(\rho\)를 유지하면 첫 행렬의 Cholesky를 재사용합니다. 반복마다 선형계의 계수는 같고 우변만 바뀌기 때문입니다. 정지 검사에는 원래 제약 잔차 \(\beta-z\)와 쌍대 잔차 \(\rho(z^{k+1}-z^k)\)를 함께 사용합니다. 두 잔차가 작다는 허용오차 판정과 정확한 최적성은 구별합니다.

def admm_lasso(G,c,lam,rho=1.,tol=1e-10,limit=10000):
    factor=la.cho_factor(G+rho*np.eye(len(c)))
    z=np.zeros_like(c);u=z.copy();history=[]
    for _ in range(limit):
        x=la.cho_solve(factor,c+rho*(z-u))
        old=z.copy();z=soft(x+u,lam/rho);u+=x-z
        rp=np.linalg.norm(x-z);rd=rho*np.linalg.norm(z-old)
        history.append((rp,rd))
        if max(rp,rd)<=tol:return x,z,np.array(history)
    raise RuntimeError('최대 반복에서 정지 기준 미달')

G=np.diag([1.,2.]);c=np.array([2.,1.]);lam=.5
x,z,history=admm_lasso(G,c,lam)
assert np.allclose(z,[1.5,.25],atol=2e-10)
assert np.linalg.norm(G@z-c+lam*np.sign(z))<1e-9
print('ADMM 해와 원래 lasso 최적조건:',z,len(history))

ADMM 해와 원래 lasso 최적조건: [1.5  0.25] 35

그림 127 왼쪽은 손으로 구한 조각별 직선이다. 오른쪽은 \(\lambda=1/2\), \(\rho=1\)의 실제 계산 이력이며 세로축이 로그이다. 로그 눈금에 표시할 수 있도록 \(10^{-16}\)보다 작은 잔차는 그림에서만 \(10^{-16}\)로 올려 표시했다. 두 그림의 가로축은 각각 벌점과 반복 횟수로 다르다.

ADMM의 일반 전역수렴 정리와 비볼록 변형은 외부 조망이며 이 예의 폐형식 해와 잔차 검산으로 대신 증명했다고 하지 않습니다. LARS의 전체 진입·이탈 구현, 자기일치 장벽의 감소량 이론, 일반 준Newton의 초선형성도 각각 별도 조건을 요구합니다. 이 장은 현재 계산에 필요한 대수와 볼록 최적조건을 아래에서 완성합니다.

9. 연습과 전체 풀이

1. 첫 예의 시작점을 \(z=(1,0)\)으로 바꾸면 정확 직선탐색은 몇 번 필요한가요?

풀이. 기울기 \((1,0)\)에 보폭은 1입니다. 한 번에 원점에 갑니다. 조건수는 9로 같아도 최악상한 \(16/25\)가 실제 모든 시작점의 감소비는 아닙니다.

2. \(H=\operatorname{diag}(1,9)\)에서 고정 보폭 \(1/9\)의 두 방향 배율을 구하세요.

풀이. \(1-1/9=8/9\)와 \(1-9/9=0\)입니다. 큰 곡률 방향은 한 번에 없애지만 작은 곡률 방향의 오차는 \(8/9\)배로 남습니다. 최악 오차배율은 최적 고정 보폭의 \(4/5\)보다 큽니다.

3. BFGS 예의 역행렬과 역 시컨트 조건을 확인하세요.

풀이. 행렬식이 2이므로 \(B_+^{-1}=\begin{pmatrix}3/4&-1/2\\-1/2&1\end{pmatrix}\)입니다. \((2,1)^T\)를 곱하면 \((1,0)^T=s\)입니다.

4. 소프트 임계값 1과 구간 \([-1,1]\) 사영을 \(v=3\)에서 비교하세요.

풀이. 소프트 임계는 2이고 사영은 1입니다. 합은 3으로 Moreau 분해를 만족하지만 두 연산 자체는 다릅니다.

5. \(v=(2,1,-1)\)을 총량 1 단체에 사영하세요.

풀이. 문턱 \(\theta=1\)이면 \((\max(1,0),\max(0,0),\max(-2,0))=(1,0,0)\)이고 합이 1입니다. 비활성 성분은 문턱 이하이며 사영 최적조건을 만족합니다.

6. \(v=(2,-1)\)을 \(\ell_1\) 반지름 1 공에 사영하세요.

풀이. 절댓값 \((2,1)\)을 합 1 단체에 사영하면 \((1,0)\)이고 부호 복원 후에도 \((1,0)\)입니다. 고정 임계값을 임의로 정하지 않고 결과의 절댓값 합이 1이 되게 문턱을 고릅니다.

7. lasso 예에서 \(\lambda=3/2\)와 \(1/2\)의 해를 구하세요.

풀이. 첫 경우 \((1/2,0)\)이고 둘째는 \((3/2,1/4)\)입니다. 첫 경우 비활성 둘째 좌표의 상관은 1로 \(\lambda=3/2\) 이하이고, 둘째 경우 두 좌표 모두 양수라 일차 최적조건 \(G\beta-c+\lambda(1,1)=0\)을 만족합니다.

8. 자기쌍대 원뿔 \(\mathbb R_+\)에서 \(v=-2\)의 Moreau 분해를 쓰세요.

풀이. 비양수 극원뿔 사영은 \(-2\), 비음수 원뿔 사영은 0이므로 \(-2=0+(-2)\)입니다. 양의 쌍대를 쓰면 \(-2=P_{\mathbb R_+}(-2)-P_{\mathbb R_+}(2)=0-2\)입니다. 두 양의 원뿔 사영을 그냥 더하면 틀립니다.

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

앞의 반복은 서로 다른 최적문제와 가정을 갖습니다. 정확산술의 대수적 성질과 유한정밀도 실행 검산을 구별합니다.

정리 1. Kantorovich 부등식과 최급강하의 최악비율

\(mI\preceq H\preceq LI\), \(m>0\)이면 비영 \(v\)에

\[ \frac{(v^THv)(v^TH^{-1}v)}{(v^Tv)^2}\le\frac{(L+m)^2}{4Lm}. \]

따라서 2절의 정확 직선탐색 비용 감소율이 성립하며 상수는 개선할 수 없습니다.

증명. \(H\)의 고유기저에서 가중치 \(w_i=v_i^2/\|v\|^2\)를 쓰고 \(a=\sum w_i\lambda_i\), \(b=\sum w_i/\lambda_i\)라 놓습니다. \((L-\lambda_i)(\lambda_i-m)\ge0\)을 \(\lambda_i\)로 나누면 \(\lambda_i+Lm/\lambda_i\le L+m\)입니다. 평균하여 \(a+Lmb\le L+m\)이고, 양수 두 수의 곱은 합의 제곱의 \(1/4\) 이하이므로 \(ab\le(L+m)^2/(4Lm)\)입니다.

이차비용의 현재 간극은 \(g^TH^{-1}g/2\)입니다. 정확 직선탐색의 감소는 \((g^Tg)^2/(2g^THg)\)이므로 간극비는 \(1-(g^Tg)^2/[(g^THg)(g^TH^{-1}g)]\)입니다. 앞 부등식으로 \(1-4Lm/(L+m)^2=((L-m)/(L+m))^2\)를 얻습니다. \(H=\operatorname{diag}(m,L)\), \(g=(1,1)\)이면 위 가중치는 두 끝점에 각각 \(1/2\)여서 모든 부등식이 등호입니다. \(x=H^{-1}g\)를 시작점으로 고르면 실제 달성합니다. ∎

정리 2. Newton의 아핀불변성과 국소 이차수렴

가역 \(B\)의 좌표 \(x=By+c\)에서 정확 Newton 보정은 \(p_x=Bp_y\)이고 감소량도 같습니다. 정지점 \(x_*\)의 헤시안이 양의 정부호이고 근방에서 헤시안이 Lipschitz이면 충분히 가까운 시작점의 전보폭 Newton은 국소 이차수렴합니다.

증명. 변환 기울기와 헤시안은 \(B^Tg,B^THB\)입니다. \((B^THB)^{-1}=B^{-1}H^{-1}B^{-T}\)를 대입하면 \(p_y=-B^{-1}H^{-1}g\), 따라서 \(Bp_y=p_x\)이고 감소량도 양쪽 \(B\)가 소거되어 같습니다. 같은 보폭을 쓰면 반복점도 대응합니다. 서로 다른 정지 기준·비정확 선형풀이·수치 반올림까지 비트 단위로 불변이라는 뜻은 아닙니다.

근방에서 \(\lambda_{\min}(H(x))\ge m_0>0\), \(\|H(x)-H(z)\|\le M\|x-z\|\)라 합시다. \(e=x-x_*\)이고 \(g(x_*)=0\)이므로 \(g(x)=\int_0^1H(x_*+te)e\,dt\)입니다. Newton 뒤 오차는

\[ e_+=H(x)^{-1}\int_0^1[H(x)-H(x_*+te)]e\,dt, \quad\|e_+\|\le\frac{M}{2m_0}\|e\|^2. \]

반지름을 충분히 작게 잡으면 이 상한이 현재 반지름보다 작아 같은 근방에 머뭅니다. 귀납으로 반복이 정의되고 이차수렴합니다. ∎

정리 3. BFGS의 양의 정부호성과 변분 특성

\(B\succ0\), \(s^Ty>0\)이면 5절의 \(B_+\)는 시컨트 조건과 양의 정부호성을 만족하며 제시한 로그 행렬식 발산의 유일한 최소점입니다.

증명. \(s\)를 곱하면 첫 두 항이 소거되고 마지막 항이 \(y\)여서 시컨트 조건입니다. 임의 \(v\)에 처음 두 항의 이차형식은 \(v^TBv-(v^TBs)^2/(s^TBs)\ge0\)입니다. 등호는 \(v\)가 \(s\)와 평행할 때뿐입니다. 마지막 항 \((v^Ty)^2/(s^Ty)\)도 비음수이며, 비영 \(v\)가 \(s\)와 평행하면 \(s^Ty>0\) 때문에 엄격 양수입니다. 따라서 합은 PD입니다.

변분문제에서 \(T=B^{-1/2}XB^{-1/2}\), \(a=B^{1/2}s\), \(b=B^{-1/2}y\)라 놓으면 목적함수는 \(\operatorname{tr}T-\log\det T-n\), 조건은 \(Ta=b\)입니다. 직교좌표를 골라 \(a=\|a\|e_1\)로 만들면 \(T\)의 첫 열·행이 고정되어

\[\begin{split} T=\begin{pmatrix}\alpha&w^T\\w&C\end{pmatrix},\quad \alpha=\frac{s^Ty}{s^TBs}>0. \end{split}\]

\(V=C-ww^T/\alpha\succ0\)가 Schur 보원입니다. 목적함수에서 변하는 부분은 \(\operatorname{tr}V-\log\det V\)뿐입니다. 고윳값마다 \(t-\log t\ge1\), 등호는 \(t=1\)에서만이므로 유일해는 \(V=I\). 이를 되돌리면 \(T=I-aa^T/(a^Ta)+bb^T/(a^Tb)\)이고 원래 좌표에서 바로 BFGS 식입니다. ∎

정리 4. 두 루프 재귀의 정확성

6절의 두 루프는 주어진 곡률쌍들로 \(G_0\)부터 역 BFGS 갱신을 한 행렬의 벡터곱입니다.

먼저 역갱신 자체를 확인해 봅시다. \(G=B^{-1}\), \(b=Bs\), \(\sigma=s^TBs\), \(\rho=1/(s^Ty)\), \(V=I-\rho sy^T\)라 두면 \(B_+s=y\)로부터

\[ B_+V=B-\frac{bb^T}{\sigma},\qquad \left(B-\frac{bb^T}{\sigma}\right)G=I-\frac{bs^T}{\sigma}. \]

따라서 \(\rho s^Ty=1\)을 사용하여

\[\begin{split} \begin{aligned} B_+(VGV^T+\rho ss^T) &=\left(I-\frac{bs^T}{\sigma}\right)(I-\rho ys^T)+\rho ys^T\\ &=I-\frac{bs^T}{\sigma} +\frac{\rho b(s^Ty)s^T}{\sigma}=I. \end{aligned} \end{split}\]

즉 \(G_+=VGV^T+\rho ss^T\)가 실제로 \(B_+^{-1}\)입니다.

증명. 마지막 쌍에 \(V=I-\rho sy^T\)를 쓰면 \(G_+v=VG(V^Tv)+\rho s(s^Tv)\)입니다. 먼저 \(\alpha=\rho s^Tv\), \(q=V^Tv=v-\alpha y\)를 구합니다. 이전 행렬곱 \(r=Gq\)를 구한 뒤 \(Vr+\alpha s=r+s(\alpha-\rho y^Tr)\)를 계산하면 됩니다. \(Gq\) 안에 있는 이전 쌍에도 같은 식을 재귀적으로 적용합니다. 들어갈 때는 뒤에서 앞으로 \(q\)를 갱신하고, 나올 때는 앞에서 뒤로 \(r\)를 갱신합니다. 이것이 코드의 두 루프입니다. 각 쌍에 상수 번의 길이 \(n\) 벡터 연산이므로 비용·저장은 \(O(mn)\)입니다. ∎

정리 5. 근접연산자의 존재, 강한 비확장성과 Moreau 분해

proper 닫힌 볼록 \(g\)와 \(\tau>0\)에서 근접점은 존재·유일하고 \((v-p)/\tau\in\partial g(p)\)로 특성화됩니다. 이 사상은 강하게 비확장이고 7절의 Moreau 분해가 성립합니다.

증명. O2의 분리 논법에서 \(g\)에는 아핀 하한이 있습니다. 그 하한에 양의 이차항을 더하면 무한대로 가는 함수이므로 목적함수의 하위수준집합은 유계입니다. 하반연속과 비어 있지 않은 유한 수준집합에서 최소를 달성합니다. 이차항의 엄격볼록성으로 해는 유일합니다.

최소점 \(p\)와 임의 \(z\in\operatorname{dom}g\)에 \(p+t(z-p)\)를 대입합니다. 볼록성으로 \(g\)의 중간값을 \((1-t)g(p)+tg(z)\)로 위에서 제한하고 최소성을 사용하면 \(g(z)-g(p)\ge(v-p)^T(z-p)/\tau-t\|z-p\|^2/(2\tau)\)입니다. \(t\downarrow0\)에서 준미분 조건이 나옵니다. 역으로 그 조건과 제곱 전개를 합하면 임의 \(z\)의 목적함수가 최소값보다 \(\|z-p\|^2/(2\tau)\) 이상 큽니다.

두 입력 \(v,w\)의 근접점 \(p,q\)에 준미분 부등식을 서로 대입해 더하면 \([(v-p)-(w-q)]^T(p-q)\ge0\)입니다. 따라서 \(\|p-q\|^2\le(v-w)^T(p-q)\)입니다.

\(u=(v-p)/\tau\)라 두면 O2의 켤레 등호에서 \(p\in\partial g^*(u)\)입니다. 즉 \(\tau(v/\tau-u)=p\in\partial g^*(u)\)여서 \(u=\operatorname{prox}_{g^*/\tau}(v/\tau)\)입니다. \(v=p+\tau u\)로 Moreau 식을 얻습니다. 원뿔 지시함수의 지지함수는 극원뿔 안에서 0, 밖에서 양의 내적 방향을 무한히 늘려 \(+\infty\)이므로 원뿔 분해와 부호도 따릅니다. ∎

정리 6. 단체·행렬 사영과 근접 경사 감소

7절의 단체·\(\ell_1\)공·PSD 사영식이 성립합니다. 볼록 \(L\)-평활 \(f\)와 proper 닫힌 볼록 \(g\)에 \(x_+=\operatorname{prox}_{\tau g}(x-\tau\nabla f(x))\), \(0<\tau\le1/L\)이면

\[ f(x_+)+g(x_+)\le f(x)+g(x)-\left(\frac1\tau-\frac L2\right)\|x_+-x\|^2. \]

증명. 단체에서는 \(p_i=\max(v_i-\theta,0)\)에 합을 맞춥니다. \(p_i>0\)이면 \(v_i-p_i=\theta\), \(p_i=0\)이면 \(v_i\le\theta\)입니다. 임의 허용 \(z\)에 \((v-p)^T(z-p)\le\theta\sum_i(z_i-p_i)=0\)이므로 O1의 사영 특성화가 적용됩니다. 정렬 알고리즘은 양수 성분이 앞 \(j\)개라는 가정을 합식에 대입하고 마지막 양수 조건으로 일관된 \(j\)를 고르는 것입니다. \(\ell_1\) 공에서는 입력 부호에 맞추면 거리만 줄어들므로 절댓값 문제로 환원되며 바깥 입력에는 경계 합을 맞춥니다.

PSD에는 입력을 \(V\Lambda V^T\)로 대각화하고 후보를 같은 좌표 \(Y\)로 옮깁니다. 거리제곱은 \(\sum_i(Y_{ii}-\lambda_i)^2+\sum_{i\ne j}Y_{ij}^2\)이며 PSD이면 \(Y_{ii}\ge0\)입니다. 따라서 대각을 \(\max(\lambda_i,0)\)로 하고 비대각을 0으로 두면 가능한 하한을 달성합니다. 핵노름 근접식은 특이값 소프트 임계 후보에 \(X-P\)가 임계값 배수의 핵노름 준기울기임을 O2 공식으로 확인하고 정리 5를 적용하면 됩니다.

마지막으로 \(d=x_+-x\)라 두면 근접 최적조건에서 \(-\nabla f(x)-d/\tau\in\partial g(x_+)\)입니다. \(g(x)\ge g(x_+)+\nabla f(x)^Td+\|d\|^2/\tau\)이고, 평활성에서 \(f(x_+)\le f(x)+\nabla f(x)^Td+L\|d\|^2/2\)입니다. 두 식을 더하면 감소식입니다. 고정점에서는 \(0\in\nabla f(x)+\partial g(x)\)여서 볼록 전체 목적함수의 최소점입니다. ∎

계산에서 사용한 정보	해당 수학적 구조
현재 기울기만으로 이동한다	오차의 일차 다항식
현재 곡률계로 보정을 푼다	Newton 이차 모형과 합동불변성
기울기 차이로 곡률을 갱신한다	시컨트 조건과 BFGS
벌점과 가까운 거리의 합을 최소화한다	근접연산자와 준미분
같은 계수행렬에 우변만 바꾼다	ADMM의 분해 재사용

기울기·곡률·근접사상은 서로 다른 구조를 이용해 최소점을 찾습니다. 다음 장부터는 확률벡터를 도입하여, 같은 최소제곱 계산이 모집단 예측과 표본 추정에서 각각 무엇을 뜻하는지 구별합니다. E0로 이어 읽기.