기술 요약: 구체(Sphere) 상의 다항식 최적화를 위한 고유값 계산의 계층 구조

문제 정의

본 논문은 실수 동차 다항식(form) $p(x)$의 차수가 $D$일 때, 단위 구(unit sphere) $\mathbb{R}^n$ 상에서의 최소화 문제인 다음을 다룹니다:
$$p_{\min} = \min_{x \in \mathbb{R}^n, \|x\|=1} p(x).$$
이 문제는 $D \geq 3$인 경우 NP-hard이며, 그래프 이론(예: 최대 안정 집합), 계산 복잡도 이론, 양자 정보 이론(예: $2 \to 4$ 노름 계산) 등 다양한 분야에 걸쳐 중요한 응용 가치를 지닙니다.

표준적인 접근 방식은 실수 SOS(Real Sum-of-Squares, RSOS) 계층 구조이며, 이는 $p_{\min}$으로 수렴하는 일련의 하한값들을 제공합니다. 그러나 RSOS 계층의 각 단계는 전체 준정부호 계획법(Semidefinite Program, SDP)을 풀어야 합니다. 문제의 크기(변수의 수 $n$ 및 차수 $D$)가 증가함에 따라 SDP의 크기가 급격히 커지며, 이는 대규모 인스턴스에 대해 이 방법을 계산적으로 불가능하게 만듭니다.

방법론

저자들은 전체 SDP를 푸는 대신 최소 고유값 계산을 통해 $p_{\min}$을 근사하는 새로운 계층 구조인 HRSOS(Hermitian Real Sum-of-Squares)를 제안합니다. 이 방법론은 세 가지 핵심 구성 요소에 기반합니다:

1. 헤르미션 최적화로의 환원: 저자들은 실수 구 상의 최적화 문제를 복소 구 상의 헤르로미션 최적화 문제로 환원하는 과정을 확립합니다. 실수 형식 $p$에 대해, 이들은 최대 대칭 그람 연산자(maximally symmetric Gram operator) $P = M(p)$를 정의합니다. 저자들은 실수 형식의 최와값 $p_{\min}$이 알려진 상수 계수 $\delta(d)$에 의해 연관된 헤르미션 형식의 최소 고유값 $P_{\min}$에 의해 다음과 같이 유계됨을 증명합니다:
   $$P_{\min} \leq p_{\min} \leq \frac{P_{\min}}{\delta(d)}.$$
   결정적으로, 이 환원은 $p_{\min} > 0$인 것과 $P_{\min} > 0$인 것이 동치라는 성질을 보존합니다.

2. HSOS 계층의 활용: 헤르미션 최적화 문제는 HSOS(Hermitian Sum-of-Squares) 계층을 사용하여 해결됩니다. RSOS 계층과 달리, HSOS 계층은 입력 형식으로부터 유도된 특정 헤르미션 연산자의 최소 고유값을 구하는 "스펙트럼(spectral)" 계층입니다. HSOS 계층의 수렴 속도는 $O(1/k)$임이 알려져 있습니다.

3. HRSOS 계층의 구축: 환원 기법과 HSOS 계층을 결합함으로써, 저자들은 일련의 일반 고유값 문제(generalized eigenvalue problems)를 구축합니다. 단계 $k$에서 하한 $\eta_k$는 다음과 같이 계산됩니다:
   $$\eta_k = \lambda_{\min}\left( (N^{(d)}_k)^{-1/2} P_k (N^{(d)}_k)^{-1/2} \right),$$
   여기서 $P_k$와 $N^{(d)}_k$는 각각 $p$와 노름 형식 $\|x\|^{2d}$로부터 유도된 연산자입니다. 실제로는 큰 행렬의 명시적 역행렬을 구하는 것을 피하기 위해 이를 일반 고유값 문제 $P_k \psi = \lambda N^{(d)}_k \psi$로 해결합니다.

저자들은 이 프레임워크를 다중 동차 형식(multi-homogeneous forms, 구들의 곱 상의 최적화) 및 텐서 스펙트럼 노름으로 확장하여 m-HRSSOS 계층을 구축합니다.

주요 기여

• 실수 최적화를 위한 스펙트럼 계층: 본 논문은 전체 SDP 대신 오직 고유값 계산만을 사용하는 실수 다항식 최적화를 위한 최초의 수렴 계층을 도입합니다.
• 수렴 보장: 저자들은 HRSOS 계층이 $O(1/k)$의 속도로 $p_{\min}$에 가산적(additively)으로 수렴함을 증명합니다. 이는 $D \leq 2n$일 때 알려진 RSOS의 $O(1/k^2)$ 속도보다는 느리지만, $D > 2n$일 때의 RSOS 속도인 $O(1/k)$와 일치합니다.
• 텐서 스펙트럼 노름 계산: 방법론을 텐서의 실수 스펙트럼 노름을 계산하고 이차 형식(biquadratic forms)을 최소화하는 데 일반화하여, 기존의 텐서 분해 및 최적화 기법에 대한 스펙트럼 대안을 제공합니다.
• 정형적 구축(Canonical Construction): 다른 "저렴한" 대안들(예: 조화 계층)과 달리, 제안된 방법은 임의의 입방 규칙(cubature rules)이나 커널을 선택할 필요가 없는 완전히 정형적인(canonical) 방식입니다.

결과 및 수치적 성능

저자들은 MATLAB을 사용하여 HRSOS 계층을 구현하고 이를 RSOS, DSOS(Diagonally-Dominant SOS), 그리고 조화 계층(harmonic hierarchy)과 비교하였습니다.

• 확장성: 주요 장점은 확장성입니다. RSOS는 SDP 솔버의 메모리 제약으로 인해 작은 규모의 문제(예: 변수 약 25개인 4차 다항식)로 제한되는 반면, HRSSOS는 희소 일반 고유값 솔버(sparse generalized eigenvalue solvers)를 활용하기 때문에 훨씬 더 큰 규모의 인스턴스(예: 변수 90개 이상의 4차 다항식)를 처리할 수 있습니다.
• 효율성 vs RSOS: RSOS가 실행 가능한 작은 문제의 경우, RSOS가 계산 시간 대비 일반적으로 더 타이트한 하한을 제공합니다. 그러나 RSOS가 실패하는 더 큰 문제의 경우, HRSSOS가 유일한 실행 가능한 스펙트럼 대안입니다.
• 효율성 vs 대안: 최적화 과정이 없는 조화 계층과 비교했을 때, HRSSOS는 단위 시간당 더 나은 하한을 제공합니다. 조화 계층은 $n$에 대해 지수적인 크기의 입방 규칙 위에서 다항식을 최소화해야 하므로 $n \geq 10$인 경우 지나치게 비용이 많이 듭니다. HRSSOS는 이러한 이산 최적화 병목 현상을 피합니다.
• 수렴성: 모츠킨(Motzkin) 다항식 및 무작위 4차 형식을 포함한 수치 실험에서, HRSSOS는 고정된 시간 예산 내에서 달성된 하한의 품질 측면에서 DSOS 및 조화 계층보다 일관되게 우수한 성능을 보였습니다.

의의 및 주장

본 논문은 HRSSOS 계층이 헤르미션 최적화 및 양자 데 피네티 정리(quantum de Finetti theorems)로부터 파생된 기법들을 활용함으로써, 대규모 제약 실수 최적화 문제를 해결하는 새로운 경로를 열어준다고 주장합니다.

• 실질적 영향: 이 방법은 표준 SDP 기반 방식으로는 다루기 힘든 다항식 최적화 문제에 대한 경계값 계산을 가능하게 합니다.
• 이론적 가교: 실수와 헤르미션 최적화 사이의 엄밀한 연결 고리를 확립하며, 다른 헤르미션 스펙트럼 기법들이 실수 문제에도 적응될 수 있음을 시사합니다.
• 겸허한 태도: 저자들은 자신들의 수렴 속도($O(1/k)$)가 낮은 차수에서의 최선 RSOS 속도보다 빠르지는 않지만, 고차원 문제에 대한 계산적 실행 가능성이 이 영역에서 더 우수한 실용적 도구임을 인정합니다. 또한, 제약 최적화의 경우 실수와 헤르미션 최소값 사이의 직접적인 동등성이 항상 성립하지는 않으므로, 이분법(bisection)이나 전체 SDP를 사용하지 않고 계층을 적응시키기 위한 추가 연구가 필요함을 언급합니다.

결론적으로, 구체 상의 대규모 다항식 최적화 및 텐서 스펙트럼 노름 계산을 위해, 제안된 고유값 계산 계층은 계산적 실행 가능성과 하한 품질 사이에서 설득력 있는 균형을 제공하며 기존의 비-SDP 대안들보다 뛰어난 성능을 보여줍니다.