Making Non-Negative Polynomials into Sums of Squares

기술 요약: 비음수 다항식을 제곱합(SOS)으로 변환하기

문제 정의
본 논문은 닫힌 집합 $K \subseteq \mathbb{R}^n$에 대한 비음수 다항식의 집합 $\text{Pos}(K)$를 제곱합(Sum of Squares, SOS) 원뿔인 $\Sigma \mathbb{R}[x_1, \dots, x_n]^2$로 변환하는 과제를 다룬다. 비음수 다항식과 모멘트 수열은 잘 연구되어 왔으나, 모든 비음수 다항식이 제곱합인 것은 아니며(Motzkin, 1967), 모든 제곱 양의 범함수가 모멘트 범함수인 것도 아니기 때문에(Scheiderer, 1979) 이를 다루는 것은 계산적으로 매우 어렵다. 저자는 비음수 다항식의 집합을 더 다루기 쉬운 형태로 "전처리(preconditioning)"하는 선형 연산자 $T: \mathbb{R}[x_1, \dots, x_n] \to \mathbb{R}[x_1, \dots, x_n]$를 조사한다. 이는 최적화 문제에서 집합 $S$에 대한 범함수의 최소화가 $TS$에 대한 최소화로 변환될 수 있으며, 이를 통해 수치적 안정성을 개선하거나 SOS 기반 솔버를 사용할 수 있다는 점에 착안하였다.

방법론
핵심 방법론은 정규 프레셰 리 군(regular Fréchet Lie groups) 이론과 그와 관련된 리 대수(Lie algebra)가 다항식 공간에 작용하는 방식에 기초한다.

1. 연산자 반군(Operator Semigroups): 저자는 선형 생성자 $A$에 의한 연산자 $T_t = e^{tA}$ 형태를 연구한다. 이러한 생성자들의 집합 $\mathfrak{g}$는 $e^{tA}$가 모든 $t \in \mathbb{R}$에 대해 다항식을 다항식으로 사상한다는 성질로 특징지어진다.
2. 표준 표현(Canonical Representation): 다항식 상의 선형 연산자의 표준 표현 $T = \sum q_\alpha \cdot \partial^\alpha$를 활용하여, 논문은 Theorem 1.1(dD25로부터)을 통해 $K$-양성 보존 연산자와 $K$-모멘트 수열 사이의 관계를 연결한다.
3. 유한 차원 불변 부분 공간: 핵심적인 기술적 도구인 Theorem 3.3은 임의의 $A \in \mathfrak{g}$에 대하여, 다항식 환(ring)을 덮는 유한 차원 불변 부분 공간의 여과(filtration) $V_i$가 존재함을 확립한다. 이를 통해 무한 차원 연산자 지수를 유한 부분 공간에서의 행렬 지수로 극한을 취하여 계산할 수 있다.
4. 특정 연산자 구성: 비음수 다항식을 SOS로 매핑하기 위해, 저자는 $Ap = \ell(p) \cdot f$로 정의된 특정 랭크-1 연산자 $A$를 구성한다. 여기서 $\ell$은 원뿔에 대해 양수인 선형 범함수이고, $f$는 대상 SOS 원뿔의 내부 점이다.

주요 기여 및 결과

• 생성자($\mathfrak{g}$)의 특징 규명: 본 논문은 $e^{tA}$가 다항식 환 위에서 잘 정의된 군(group)이 되는 생성자 $\mathfrak{g}$의 집합을 완전히 규명한다. $\mathfrak{g}$는 원뿔(cone)이지만 벡터 공간은 아니다(일반적으로 덧셈이나 곱셈에 대해 닫혀 있지 않다). 그러나 공통의 유한 차원 불변 부분 공간을 공유하는 $\mathfrak{g}$의 부분집합들은 정규 프레셰 리 대수를 형성한다.
• Stochel의 정리(삼선 증명): 저자는 수열이 $K$-모멘트 수열이기 위한 필요충분조건이 그 절단(truncation)들이 절단된 $K$-모멘트 수열이라는 Stochel의 정리(2001)에 대한 간결한 증명을 제공한다. 이 증명은 다항식과 수열 사이의 쌍대성(duality) 및 Haviland의 정리에 의존한다.
• $K$-양성 보존 반 ever의 생성자: Theorem 6.3은 $K$-양성을 보존하는 생성자 $A \in \mathfrak{g}$에 대한 분해서(resolvent) 설명을 제공한다. 이는 기존의 결과들을 일반화하며, 추상적이지만 완전한 특징을 제공한다.
• 제곱합으로의 변환 (Theorem 7.1): 중심 결과는 고정된 차수 상한 $d$에 대하여, 임의의 비음수 다항식 집합 $S \subseteq \text{Pos}(K)_{\le 2d}$를 제곱합 원뿔 $\Sigma \mathbb{R}[x_1, \dots, x_n]^2_{\le d}$로 매핑하는 선형 연산자 $T = e^{\tau A}$가 존재함을 입증한다.
• 계산 효율성: 논문은 구성된 연산자 $T$의 특정한 구조(항등 연산자에 대한 랭크-1 업데이트)가 극도로 높은 계산 효율성을 가져온다는 점을 강조한다.
  • 메모리: 연산자 행렬 $\tilde{T}$를 저장하는 데는 $2N + 1$개의 스칼라만 필요하다($N = \dim \mathbb{R}[x]_{\le 2d}$). 이는 저장 용량을 $O(N^2)$에서 $O(N)$으로 줄인다.
  • 복잡도: 행렬-벡터 곱($Tv$)은 최대$4N + 1$번의 연산을 필요로 한다. 행렬-행렬 곱($\tilde{T}M$)은 최대$4N^2 + 1$번의 연산을 필요로 한다.
  • 역행렬: 역 연산자 $\tilde{T}^{-1}$을 계산하는 데는 단 한 번의 연산(나눗셈)만 필요하며, 이는 표준적인 $O(N^3)$ 이상의 복잡도와 극명한 대조를 이룬다.
• 불가능성 결과 (Theorem 7.5): 본 논문은 컴팩트한 $K$에 대하여, 차수 제한 없이 전체 무한 차원 원뿔 $\text{Pos}(K)$를 SOS 원뿔로 매핑하는 단사 선형 연산자 $T$가 존재할 수 없음을 증명한다. 이는 메인 정리에서 차수 제약의 필요성을 부각시킨다.
• 비마르코프 예시: 섹션 8에서는 Burgers' 방정식을 사용한 예시를 통해, 균질 마르코프 과정(homogeneous Markov process)이 아닌 시간 진화(time-evolution)를 제시하며, $e^{tA}$ 이론이 모든 가능한 다항식 진화를 다루지는 않는다는 점을 보여준다.

의의 및 주장
본 논문은 개발된 이론이 비음수 다항식을 제곱합으로 변환하는 계산 가능한 방법을 제공한다고 주장한다. 비음수성과 SOS 사이의 간극 때문에 이 작업은 일반적으로 어렵다. 본 연구의 의의는 제안된 변환의 알고리즘적 효율성에 있다. 저자는 정규 프레셰 리 군의 특정 구조적 특성을 가진 연산자를 활용함으로써, 행렬 연산의 자명한 하한선($O(N^2)$)을 충족하고 역행렬 계산을 단 한 번의 연산으로 줄였다.

저자는 $T$와 그 역연산이 효율적으로 계산 가능하지만, 이 접근법이 고정된 차수 상한에 국한된다는 점을 명시적으로 밝히고 있다. 본 논문은 모든 비음수 다항식을 SOS로 표현하는 일반적인 문제(불가능한 문제)를 해결하려는 것이 아니라, 최적화 또는 수치적 안정성을 목적으로 특정 비음수 다항식 부분집합을 SOS 원뿔으로 이동시키기 위한 도구를 제공하는 것이다. 이 연구는 무한 차원 리 군의 추상적 이론과 실용적인 계산 대수 기하학 사이의 가교 역할을 한다.