08. 수학적 기반 — gradient, convexity, norm, decomposition

// CORE 2/7 — gradient/Jacobian/Hessian, Taylor approximation, convexity, norm, inner product, orthogonality, matrix decomposition

이 페이지는 최적화 알고리즘을 읽을 때 반복해서 등장하는 수학 도구를 한곳에 묶습니다. 배경 1–4편이 문법이라면, 여기서는 그 문법이 알고리즘 안에서 어떻게 쓰이는지 봅니다.

Gradient / Jacobian / Hessian

scalar objective $f:\mathbb{R}^n\to\mathbb{R}$ 에서는 gradient가 1차 정보를 줍니다.

\nabla f(x).

vector-valued function $F:\mathbb{R}^n\to\mathbb{R}^m$ 에서는 Jacobian이 1차 정보를 줍니다.

J_F(x)=\frac{\partial F}{\partial x}.

Hessian은 scalar objective의 2차 정보를 줍니다.

\nabla^2 f(x).

제약 최적화에서는 objective의 gradient뿐 아니라 constraint의 gradient 또는 Jacobian도 함께 봅니다.

최적화 알고리즘은 복잡한 문제를 현재 점 근처의 쉬운 문제로 바꿉니다.

f(x+p)\approx f(x)+\nabla f(x)^\top p+\frac{1}{2}p^\top \nabla^2 f(x)p.

Gradient descent는 linear term만 보고 내려가는 방향을 잡습니다. Newton method는 quadratic model을 최소화해 step을 구합니다.

convex function은 두 점을 잇는 선분 위에서 함수값이 chord 아래에 있는 함수입니다.

f(\theta x+(1-\theta)y)\le \theta f(x)+(1-\theta)f(y),\quad 0\le\theta\le 1.

convex optimization이 중요한 이유는 local minimum이 global minimum이기 때문입니다. 비볼록 문제에서는 saddle point와 local minimum을 구분해야 하지만, 볼록 문제에서는 최적성 조건이 훨씬 강해집니다.

norm은 크기를, inner product는 방향의 정렬을 말합니다.

\|x\|_2=\sqrt{x^\top x},\qquad \langle x,y\rangle=x^\top y.

descent direction $p$ 는 보통 다음 조건을 만족합니다.

\nabla f(x)^\top p<0.

즉, gradient와 반대쪽 성분을 가진 방향입니다.

두 벡터가 orthogonal이면 inner product가 0입니다.

x^\top y=0.

Conjugate gradient에서는 단순한 orthogonality보다 더 강한 $A$ -orthogonality를 씁니다.

p_i^\top A p_j=0\quad (i\ne j).

이 조건 덕분에 이전에 최적화한 방향을 다시 망가뜨리지 않고 다음 방향으로 진행할 수 있습니다.

matrix decomposition은 큰 선형대수 계산을 안정적이고 빠르게 푸는 방법입니다.

decomposition	쓰임
LU	일반 선형 시스템 풀이
Cholesky	symmetric positive definite 시스템 풀이
QR	least squares, 직교화
eigen decomposition	곡률, positive definiteness 분석
SVD	rank, ill-conditioning, pseudo-inverse

Newton method에서 Hessian이 positive definite이면 Cholesky factorization으로 안정적으로 step을 구할 수 있습니다. ill-conditioned least squares에서는 QR이나 SVD가 더 안전합니다.