03. 최적화를 위한 선형대수 — 방향, 곡률, 선형 시스템

// BACKGROUND 3/6 — vector, matrix, inner product, linear independence, eigenvalue, positive definiteness, linear systems

최적화 알고리즘은 거의 항상 벡터 공간 위에서 움직입니다. 선형대수는 그 공간에서 방향, 거리, 직교성, 곡률, 계산 가능성을 말하는 언어입니다.

Vector and matrix

벡터 $x\in\mathbb{R}^n$ 은 한 후보해입니다. 행렬 $A\in\mathbb{R}^{m\times n}$ 은 벡터를 다른 벡터로 보내는 선형 변환입니다.

y=Ax.

제약 $Ax\le b$ 는 “ $x$ 가 여러 선형 부등식을 동시에 만족해야 한다”는 뜻입니다. 최소제곱 문제의 예시는 다음과 같습니다.

\min_x \|Ax-b\|_2^2.

inner product는 두 벡터가 얼마나 같은 방향을 보는지 측정합니다.

\langle x,y\rangle=x^\top y.

$x^\top y$ 가 양수면 비슷한 방향, 음수면 반대 방향, 0이면 직교입니다. Gradient descent에서 $p=-\nabla f(x)$ 를 고르면

\nabla f(x)^\top p=-\|\nabla f(x)\|_2^2<0

이므로 descent direction입니다.

벡터들이 서로 중복되지 않는 방향을 제공하면 linearly independent라고 합니다. 선형 시스템을 풀 때, 또는 제약의 독립성을 확인할 때 중요합니다.

제약 gradient들이 독립이면 “제약들이 같은 말만 반복하지 않는다”고 볼 수 있습니다. 이 조건은 Lagrange multiplier와 KKT 조건을 안정적으로 다룰 때 필요합니다.

행렬 $A$ 가 어떤 방향 $v$ 를 방향은 유지한 채 크기만 바꾼다면

Av=\lambda v

라고 쓰고, $\lambda$ 를 eigenvalue라고 합니다. Hessian의 eigenvalue는 함수의 곡률을 방향별로 보여줍니다.

대칭 행렬 $H$ 가 모든 $p\ne 0$ 에 대해

p^\top H p>0

이면 positive definite입니다. 최적화에서는 Hessian이 positive definite일 때 그 점 주변이 bowl-shaped이며 strict local minimum을 기대할 수 있습니다.

Newton method는 매 반복마다 다음 선형 시스템을 풉니다.

\nabla^2 f(x_k)p_k=-\nabla f(x_k).

즉, Newton step은 Hessian의 역행렬을 직접 구하는 문제가 아니라 선형 시스템을 안정적으로 푸는 문제입니다. 실제 구현에서는 역행렬을 만들지 않고 factorization이나 iterative solver를 씁니다.