레이먼 다면체의 무제약 최적화 문제를 해결하기 위해 공멍 사다리법을 소개했다.
동시에 파이톤의 실현에 대한 소개입니다.

대상 문제

레이먼 달러\mathcal{M}의 무제약 최적화 문제
$$\mathop{\text{minimize}}_{x\in\mathcal M}\quad f(x)$$
여기서 $f:\mathcal M\to\mathbR은 매끄러운 매핑입니다.

수공간 공멍 사다리법

공멍 사다리법의 알고리즘은 다음과 같다.

$x^0달러 초기화
달러로 검색 방향 초기화

for $k=0,1,\ldots$ do

보폭 $t계산k$.

$x^{k+1}=x^k+t_kd^k 달러로 업데이트

$\beta_k=\rac{nablaf(x^{k+1})^\top\nablaf(x^{k+1})} 계산 {nablaf(x^k)^\top\nablaf(x^k)}달러

$d^{k+1}=−\nabla f(x^{k+1})+\beta_kd^k 달러로 검색 방향 업데이트

end for

전편의 기사에 상세하게 기재하다.

선형 방정식과 공멍 사다리법 - Qita

레이먼 다면체의 멍에 사다리법

리먼 다면체의 경우 공멍 사다리법의 알고리즘, Absil 등 다양체에 최적화된 책'Optimization Algorithms on Matrix Manifolds'에 소개됐다.

$x^0달러 초기화

$d^0=-\mathop{\mathrm{grad}}f(x^0)$로 검색 방향 초기화

for $k=0,1,\ldots$ do

보폭 $t계산k$.

$x^{k+1}={red}{R{x^k}\left(t kd^k\right)$로 업데이트

$\beta_k=\frac{\left\langle\mathop{\mathrm{grad}}f(x^{k+1}),\mathop{\mathrm{grad}}f(x^{k+1})\right\rangle_{\color{red}{x^{k+1}}}}{\left\langle\mathop{\mathrm{grad}}f(x^{k}),\mathop{\mathrm{grad}}f(x^{k})\right\rangle_{{{color{red} {x^{k}}}}$. 계산 $.

$d^{k+1}=−\mathop{\mathrm{grad}} f(x^{k+1})+\beta_k\color{red} {mathcalT{t kd^k}(d^k)$로 검색 방향 업데이트

end for

수 공간 $\mathbR^n의 경우와 비교하면 빨간색 문자의 위치가 크게 다르다.
다음은 각각의 해설.

레만도르양의 체내적

레이먼에서 $\mathcal M달러를 다양화하고, 레이먼의 도량에 따라 어떤 점$x\in\mathcal M달러의 접촉 공간$T$\langle\cdot,\cdot\rangele결정했어.

레이먼 다면체의 사다리

$\mathcal M=\mathbR^n 달러의 경사도는
$$\nabla f(x) :=\left(\frac{\partial f}{\partial x_1}(x),\frac{\partial f}{\partial x_2}(x),\ldots,\frac{\partial f}{\partial x_n}(x)\right)^\top$$
이때 사다리와 방향 도수 사이에서
$$\mathop{\mathrm D}f(x)[d] :=\frac{\mathrm d}{\mathrm dt}f(x+td) =\nabla f(x)^\top d$$
관계를 맺다.
레이먼 다면체\mathcal M 달러 상한선 $f 달러의 방향도수, $\gamma(0)=x달러와 $\dot\gamma(0)=d달러의 곡선 $\gamma:\mathbR\to\mathcal M 달러 사용
$$\mathop{\mathrm D}f(x)[d] :=\frac{\mathrm d}{\mathrm dt}f(\gamma(t))$$
이 방향의 미분으로 함수 $f$\mathop{mathrm{grad}의 레이먼 다면체의 사다리를 계산할 수 있습니다
$$\mathop{\mathrm{D}} f(x)[d] =\langle\mathop{\mathrm{grad}} f(x), d\rangle_x$$
전체 버전 보기상원으로 정의하다.

복제하다

레이먼 변형 $\mathcal M의 변수 업데이트 공식에서 $x^k\in\mathcal M$d^k\in T{x^k}\mathcal M달러, 소속 공간이 다르기 때문에 단순히 $x^{k+1}=x^k+t업데이트할 수 없습니다.
따라서 자연의 확장으로 리만 다양성의 직선(가속도 0)을 따라 지선을 갱신하는 것을 고려할 수 있다.
$$x^{k+1}=\gamma(t_k;x^k,d^k)=:\exp_{x^k}(t_kd^k)$$
여기서 $\exp:T\mathcal M\to\mathcal M은 지수 매핑이라고 합니다.
레이먼 다면체의 최적화 분야에서 지수영사를 사용하면 더욱 일반화된 굴절영사라고 불린다.
$$x^{k+1}=R_{x^k}(t_kd^k)$$
변수를 업데이트합니다.

$R_x(0 x) = x\qquad$($0 x는 $T x\mathcal M의 0 벡터)

$\mathop{\mathrm{D}}R_x(0_x) =\mathrm{id}_{T x\mathcalM]\qquad$($\mathrm{id}달러는 항등영사)

벡터 수송

공멍 사다리법의 탐색 방향을 레이먼 다면체로 확장하기 $\mathcal M 시 그대로 유지
$$d^{k+1}=−\mathop{\mathrm{grad}} f(x^{k+1})+\beta_kd^k$$
$mathop{\mathrm{grad}f(x^{k+1})\in T{x^{k+1}\mathcal M달러 및 $d^k\in T{x^k}\mathcal M달러가 속한 접촉 공간이 다르기 때문이다.
그래서 자연의 확장으로{x^k}\mathcal M$T{x^{k+1}\mathcal M달러와 평행으로 이동합니다. 여기서 말하는 평행은 어떤 곡선 (예를 들어 측지선 $\gamma (t; x^k, d^k) $) 을 따라 벡터장이 평행하는 것을 말합니다.
레이먼 다면체의 최적화 영역에서 평행운동은 벡터 전송의 보다 일반화된 매핑 $\mathcal T,
$$d^{k+1}=−\mathop{\mathrm{grad}} f(x^{k+1})+\beta_k\mathcal T_{t_kd^k}(d^k)$$
구문을 사용합니다.{eta x} $T$x\mathcal M$\xi 조인트 벡터x$T{R x (\eta x)} $\mathcalT 이상{eta x} {\xi x} 달러에 비추어 다음과 같은 두 가지 조건을 만족시킨다.

$\mathcal T_{0_x}(\xi_x) =\xi_x$

$\mathcal T_{\eta_x}(a\xi_x + b\zeta_x) = a\mathcal T_{\eta_x}(\xi_x) + b\mathcal T_{\eta_x}(\zeta_x)$

파이톤에서의 실현

Python에서 Pymanopt라는 레이먼 다면체의 최적화 구해기를 실현했다.

사용 예

문제.

다음 Brockett cost function의 최소화를 고려합니다.

\begin{align}
\mathop{\mathrm{minimize}}_{X\in \mathbb R^{n \times r}} &\quad f(X) :=\mathop{\mathrm{tr}}\left(X^\top A X N\right)\\
\text{subject to} &\quad X^\top X = I_r
\end{align}

여기, $A\in\mathb{R}^{n\timesn}은 대칭 행렬이고, $N\in theb{R}^{timesr}는 양수 대각 행렬 $N=\mathop{mathrm{diag}(\mu 1,\mu 2,\ldots,\mu r)$1\leq\mu_2\leq\dots\leq\mu_적합한 솔루션 찾기$A$A의 작은 순서에 따라 $r$개의 특징 값에 대응하는 고유 벡터를 배열하는 행렬입니다.
$$\nabla f(X) = 2AXN$$
계산하다.
이 최적화 문제는 슈티펠 다면체입니다.

\mathop{\mathrm{St}}(n, r) := \left\{X\in\mathbb{R}^{n\times r} \mid X^\top X = I_r\right\}

위의 무제약 최적화 문제

\mathop{\mathrm{minimize}}_{X \in \mathop{\mathrm{St}}(n, r)} \quad f(X)

로 변환할 수 있습니다.

실행 예

대칭 행렬 $A$A는 다음과 같이 생성됩니다.

import numpy as np


n = 10
r = 3
np.random.seed(0)

A = np.random.randn(n, n)
A = 0.5 * (A + A.T)

pymanopt.solvers.conjugate_gradient.ConjugateGradient를 사용하려면 설정pymanopt.solvers.conjugate_gradient.ConjugateGradient이 필요합니다. 설정 방법은 pymanopt.core.problem.Problem에 기재되어 있으며, 이번에도 파이톤 함수로 목적 함수와 사다리(유클리드 공간)를 지정하는 방법으로내부가 유클리드 공간의 사다리 $\nablaf$\mathop{mathrm{grad}에서 슈티펠 다면체의 사다리 $\mathop{mathrm{grad}로 변환되었습니다.

class Brockett:
    def __init__(self, A: np.ndarray, r: int):
        if A.ndim != 2:
            raise ValueError(f'Expected 2D array, got {A.ndim}D array instead.')
        self.A = A
        r = np.minimum(r, A.shape[0])
        self.N = np.arange(1, r + 1) / r

    def cost(self, X: np.ndarray) -> float:
        return np.sum((self.A @ X) * (X * self.N))

    def egrad(self, X: np.ndarray) -> np.ndarray:
        return 2 * self.A @ X * self.N

위에서 정의한 Brockett cost function의 클래스를 사용하여 Pymanopt의Problem를 다음과 같이 설정합니다.

from pymanopt import Problem
from pymanopt.manifolds import Stiefel


brockett = Brockett(A=A, r=r)
stiefel = Stiefel(n, r)
prob = Problem(manifold=stiefel, cost=brockett.cost, egrad=brockett.egrad)

ConjugateGradient에서 $\beta의 종류를 지정할 수 있습니다. 이번에는 beta_type=0(Fletcher-Reeves)를 사용했습니다. 또한 solve 함수에서는 문제 외에 초기점을 지정할 수 있습니다.0=(I r, O)^\top 달러를 초기 매트릭스로 사용합니다.

from pymanopt.solvers import ConjugateGradient


X0 = np.eye(n, r)
solver = ConjugateGradient(beta_type=0)
Xopt = solver.solve(prob, x=X0)

얻은 해의 정확성은 numpy.linalg.eigh의 결과와 비교하여 확인한다.

_, V = np.linalg.eigh(A)
print(np.sum(Xopt * V[:, :r][:, ::-1], axis=0)) # [1. 1. 1.]

참고 문헌

공식.