14-08 Special cases

Sparse, structured problems

우리가 해결하려는 문제의 linear system matrix가 \(O(n^{3})\)의 연산시간을 가지는 Hessian의 역행렬의 계산을 효과적으로 할 수 있는 조건을 만족하면, 우리는 이 문제를 좀 더 효율적으로 해결할 수 있다.

예를들어, \(\nabla^{2}f(x)\)가 모든 \(x\)에 대하여 sparse하고 structured 되어 있는 matrix 형태, 예를 들면 band matrix의 경우, Newton’s method를 적용하면서 memory와 computation에서 O(n)의 성능을 가진다. (Band matrix는 대각행과의 거리가 일정 범위 이내에 0이 아닌 항들이 모두 존재하는 형태, 즉 대각행 근처에만 값을 가지는 matrix를 의미한다.)

Structured Hessian을 만드는 대표적인 두가지 함수의 예를 알아보자.

• \(g(\beta) = f(X\beta)\)이면, \(\nabla^{2}g(\beta)=X^{T}\nabla^{2}f(X\beta)X\)이다. 또한 만약 X가 structured predictor matrix 이고 \(\nabla^{2}f\), 즉 \(f\)의 hessian이 digonal이면, \(\nabla^{2}g\)는 structured 되어있다.

• 만약 \(\nabla^{2}f\)가 diagonal이고, \(g\)가 non smooth일때, \(f(\beta)+g(D\beta)\)를 최소화하고자 한다고 하자. 또한 \(D\)는 structured penalty matrix이다. 이때 Lagrange dual은 \(-f^{*}(-D^{T}u)-g^{*}(-u)\)이다. 일반적으로 \(-D\nabla^{2}f^{*}(-D^{T}u)D^{T}\)는 structured 될 수 있다.

Equality-constrained Newton’s method

이제 등호 조건(equallity constraints)이 있는 최적화 문제를 살펴보자. 우리는 일반적으로 이 문제를 아래와 같이 나타내었다.

\[\begin{align} &\min_{x} f(x) & \text{subject to }Ax=b. \end{align}\]

이 문제의 해결에 대하여 크게 세가지 방법으로 접근해볼 수 있다.

1) 등호 조건의 제거(reduced-space approach) : 정의역 자체를 equality constraint를 만족하는 space로 제한하여 문제를 해결한다. 위의 문제라면, x를 A의 null space를 span하는 F와 \(Ax_{0}=b\)의 합으로 표현한다. 즉, \(x=Fy+x_{0}\)로 나타내고 y에 관하여 문제를 해결하는 방식이다.

2) 등호 제약조건을 만족하는 Newton’s method(Equality-constrained Newton)[4] : 기본적으로 unconstrained Newton’s method와 동일하나 두가지 차이가 있다. 첫째로는 초기값이 feasible해야하고(\(x \in dom (f)\)이고, \(Ax = b\))를 만족하고, 두 번째로는 Newton step의 과정에서 equality constraints를 고려한다는 것이다. 즉, Newton step \(\Delta x_{nt}\)를 \(A\Delta x_{nt}=0\)을 만족하도록 값을 결정한다. 아래에서 자세히 살펴보도록 한다.

3) Dual의 유도를 통한 해결 : Fenchel dual은 \(-f^{*}(-A^{T}v)-b^{T}v\)로 정의되고, strong duality를 만족한다. (16-03에서 자세히 다루도록 한다.) 간략하게 conjugate function의 정의를 활용하여 dual 문제의 목적함수를 유도해보도록 하자. 여기서의 \(f^{*}\)는 f의 conjugate이다.

\[\begin{align} g(v) &= -b^{T}v + \min_{x}(f(x)+v^{T}Ax)\\\\ &= -b^{T}v - \max_{x}\big( (-A^{T}v)^{T}x - f(x) \big)\\\\ &= -b^{T}v - f^{*}(-A^{T}v), \end{align}\]

이 되므로, dual 문제는 다음과 같다.

\[\begin{align} \max -b^{T}v-f^{*}(-A^{T}v). \end{align}\]

최적값이 존재한다고 가정하기에, 이 문제는 strictly feasible하고, slater’s condition을 만족한다. 따라서 위에서 언급했듯이 strong duality를 만족하고, \(g(v^{*})=p^{*}\)인 \(v^{*}\)가 존재한다.[1, p.525]

이제 2)의 방법을 살펴보자. feasible한 Newton step \(\Delta x_{nt}\)을 유도하기 위하여, 원래의 문제에서의 목적 함수를 x 근처의 2차 taylor 근사를 한 식으로 대체한다. 이를 나타내면 다음과 같다.

\[\begin{align} \text{minimize}\quad &\hat{f}(x+v) = f(x) + \nabla f(x)^{T}v + \frac{1}{2}v^{T}\nabla^{2} f(x) v\\\\ \text{subject to}\quad &A(x+v) = b, \end{align}\]

위의 식을 아래의 식으로도 표현할 수 있다.

\[\begin{align} x^{+} = x + tv,\,\, \text{where}\\\\ v = \underset{A(x+z)=b}{\operatorname{argmin}}\big( f(x)+\nabla f(x)^{T}z+\frac{1}{2}z^{T}\nabla^{2} f(x)z \big)\\\\ \end{align}\]

\(Ax^{+} = Ax+tAv = b\)이므로, 식을 반복하는 과정에서도 다음 스텝의 solution \(x\)가 계속 constraint 안에 존재하도록 유지한다.

이 문제에 대한 KKT를 아래와 같이 나타내고, linear system인 아래의 문제를 풀면 solution을 구할 수 있다. \(v\)가 Newton step \(\Delta x_{nt}\)임을 상기하자.

\[\begin{align} \begin{bmatrix} \nabla^{2} f(x) & A^{T}\\\\ A & 0 \end{bmatrix} \begin{bmatrix} v\\\\ w \end{bmatrix} =- \begin{bmatrix} \nabla f(x)\\\\ Ax-b \end{bmatrix} \end{align}\]

\(w\)는 위의 quadratic problem에 대한 optimal dual variable이다.