기술적 요약: 분산 합 제곱

문제 제기

이 논문은 다항식의 비음수성 (nonnegativity) 을 증명하는 근본적인 문제를 다룹니다. 다항식 $p$가 모든 $x \in \mathbb{R}^n$에 대해 $p(x) \geq 0$일 때 비음수이지만, 이 성질을 판별하는 것은 일반적으로 NP-난해 (NP-hard) 입니다. 표준적인 접근법인 합 제곱 (Sum of Squares, SOS) 방법은 $p(x) = \sum q_i^2(x)$라는 단일 대수적 항등식으로 $p$를 표현하여 비음수성을 증명합니다. 그러나 힐베르트 (Hilbert) 가 확립한 바와 같이 모든 비음수 다항식이 SOS 는 아니며, SOS 가 아닌 다항식의 비음수성을 증명하려면 일반적으로 $p$에 고차 SOS 다항식을 곱해야 합니다 (예: 힐베르트의 17 번째 문제 해결을 위한 아르틴 (Artin) 의 해법). 이로 인해 원래 다항식보다 훨씬 높은 차수의 대수적 항등식이 생성되고, 이는 기하급수적으로 커지는 크기의 반정부호 계획법 (Semidefinite Programs, SDP) 을 초래하여 계산적으로 처리 불가능해집니다.

이 연구를 이끄는 핵심 질문은 다음과 같습니다: 단일 항등식 대신 여러 대수적 항등식을 구성함으로써 다항식 비음수성에 대한 SOS 기반 증명 의 복잡도를 낮출 수 있을까요?

방법론

저자들은 분산 합 제곱 (Disjunctive SOS) 개념을 도입합니다. 단일 전역 항등식 대신, 비음수성은 정의역의 특정 부분 영역에서 각각 유효한 대수적 항등식들의 집합으로 증명됩니다. 이러한 부분 영역들은 **대수적 분해 (algebraic disjunction)**로 정의된 공간의 분할 (또는 덮개) 을 이룹니다.

핵심 정의

1. 대수적 분해: $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$인 영역들의 합집합이 $\mathbb{R}^n$을 덮도록 하는 다항식들의 집합 $\mathcal{D} = \{\{q_{k,j}\}\}$.
2. 분산 SOS 증명: 다항식 $p$가 $\mathcal{D}$에 대해 분산 SOS 일 필요충분조건은 각 영역 $\Omega_k$에 대해 SOS 다항식 $s_{k,j}$들이 존재하여 다음이 성립하는 것입니다:
   $$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{모든 } x \in \Omega_k \text{에 대해}.$$
   중요한 점은, 전역 SOS 증명에서는 차수가 종종 증가해야 하는 것과 달리 SOS 다항식 $s_{k,j}$의 차수를 낮게 유지할 수 있다는 것입니다 (구체적으로 $p$의 차수로 제한됨).

이론적 체계

이 논문은 **분산 포지티브스텔렌차트 (Disjunctive Positivstellensätze)**라고 명명된 두 가지 주요 이론적 결과를 제시합니다:

1. SDP 기반 분산 포지티브스텔렌차트 (정리 1):
   차수 $d$인 양정부호 형식 (positive definite form) $p$에 대해, 구면 캡 (spherical caps) 을 통해 구성된 명시적인 대수적 분해의 가족이 존재하며, 이때 $p$는 SOS 승수의 차수가 최대 $d$가 되도록 분산 SOS 증명을 허용합니다. 이를 통해 단위 구면 위의 다항식 최소화에 대한 하한을 수렴시키는 고정 크기 (계층 수준과 무관한) 의 SDP 계층 구조를 사용할 수 있습니다.

2. 최적화 없는 분산 포지티브스텔렌차트 (정리 8):
   더 강력한 결과로, 임의의 양정부호 형식에 대해 단순형 분해 (simplicial disjunctions) (다면체 원뿔) 의 가족이 존재하여, 각 원뿔 내에서 선형 좌표 변환 후 계수가 비음수인지 확인하기만 하면 $p$의 비음수성을 증명할 수 있음을 보여줍니다. 이 접근법은 최적화 솔버가 필요 없으며 (선형 계획법 또는 직접적인 계수 확인만 필요), SDP 접근법보다 더 많은 영역이 필요할 수는 있습니다.

알고리즘적 체계

저자들은 이러한 분산 증명을 적응적으로 탐색하기 위한 공간 분기 - 바운드 (Spatial Branch-and-Bound, SBB) 프레임워크를 제안합니다. 이론적 증명에서와 같이 공간을 균일하게 분할하는 대신, 알고리즘은 다음과 같이 작동합니다:

• 부분 영역 (단순형 원뿔) 의 트리를 유지합니다.
• 각 부분 영역에서 SDP (또는 선형 확인) 를 통해 하한을 계산합니다.
• 투영 경사 하강법 (projected gradient descent) 을 통해 상한을 계산합니다.
• 가장 작은 하한을 가진 부분 영역의 가장 긴 모서리를 이등분하여 분기합니다.
  이 적응적 접근법은 균일 구성보다 적은 수의 부분 영역으로 증명서를 찾도록 합니다.

주요 기여 및 결과

1. 이론적 보장

• 고정 차수: 이 논문은 저차 분산 SOS 증명이 항상 존재함을 증명합니다. 증명 내 SOS 다항식의 차수는 계층 수준에 따라 증가할 필요가 없으며, 원래 다항식의 차수로 고정될 수 있습니다.
• 수렴: 저자들은 단위 구면 위의 동차 다항식의 전역 최소값으로 수렴하는 고정 제약 크기의 SDP 계층 구조를 구성합니다. 공간 분할의 해상도 $m$과 관련된 $O(1/m)$의 수렴 속도를 확립합니다.
• 최적화 없는 증명서: 두 번째 포지티브스텔렌차트는 SDP 를 풀지 않고 선형 변환과 계수 비음수성 확인에 의존하여 비음수성을 증명하는 방법을 제공합니다.

2. 제약 최적화에의 적용

• 다항식 최적화: 분산 접근법과 [2] 의 축소 기법을 결합하여, 콤팩트 기본 반대수적 집합 (compact basic semialgebraic sets) 위의 일반 다항식 최적화 문제 (POPs) 에 대한 하한의 수렴 계층 구조를 구성합니다.
• 공양성 계획법 (Copositive Programming): 이 방법은 행렬의 공양성 (nonnegative orthant 위의 $x^T Q x \geq 0$ 확인) 을 증명하는 데 특화됩니다. 저자들은 "분산 P+N" 조건을 정의하여, 비음수 오일러 (orthant) 의 각 단순형 부분 영역에서 행렬이 양의 반정부호 행렬과 비음수 행렬로 분해될 수 있을 때 행렬이 공양성임을 증명합니다. 이는 기존 계층 구조에서 제약 크기가 수준에 따라 다항식적으로 증가하는 것과 대조적으로, SDP 제약의 크기가 고정 ($n \times n$) 된 완전한 계층 구조를 제공합니다.

3. 수치 실험

저자들은 다음과 같은 수치 실험을 제시합니다:

• 비-SOS 다항식: SBB 프레임워크를 통해 소수의 부분 영역 (종종 20 개 미만) 으로 모트킨 (Motzkin), 로빈슨 (Robinson), 초이 - 람 (Choi-Lam), 델젤 (Delzell) 과 같은 고전적인 비-SOS 다항식들의 비음수성을 성공적으로 증명했습니다.
• 공양성 프로그램: 이 알고리즘은 비볼록 2 차 계획법을 해결하고, 모트킨 - 스트라우스 (Motzkin-Straus) 정리를 통해 무작위 인스턴스에서 그래프의 클릭 수 (clique number) 를 계산했습니다.
• 성능: 결과는 분산 접근법이 균일 분할보다 훨씬 적은 수의 부분 영역으로 비음수성을 증명하고 최적화 문제를 해결할 수 있으며, SDP 제약의 크기가 관리 가능한 수준으로 유지됨을 나타냅니다.

중요성 및 주장

이 논문은 분산 합 제곱 접근법이 SOS 다항식의 차수 (증명의 복잡도) 와 사용된 대수적 항등식의 수를 분리함으로써 전통적인 SOS 계층 구조에 대한 실현 가능한 대안을 제공한다고 주장합니다.

• 계산 효율성: SOS 다항식의 차수를 낮고 고정된 상태로 유지함으로써, 기반 SDP 의 크기가 계층 전체에서 일정하게 유지되어 표준 SOS 방법에서 다항식 차수 증가와 관련된 "차원의 저주"를 피합니다.
• 유연성: 이 프레임워크는 더 적은 영역으로 더 엄격한 하한을 위한 SDP 기반 탐색과 더 빠르지만 잠재적으로 더 거친 증명서를 위한 최적화 없는 탐색을 모두 지원합니다.
• 완전성: 저자들은 이 접근법이 완전함을 증명합니다. 즉, 임의의 엄격하게 양수인 다항식 (또는 엄격하게 공양성인 행렬) 에 대해 그들의 프레임워크 내에서 증명서가 존재합니다.

이 논문은 이론적 구성이 균일 분할을 사용하지만, 실제 SBB 알고리즘은 공간을 적응적으로 세분화하여 인스턴스별 분해가 필요한 영역의 수를 더 줄일 수 있음을 지적하며 마무리합니다. 이 연구는 분산 SOS 와 희소성 및 대칭성 활용을 결합하고, 프레임워크의 이중 모멘트 (dual moment) 측면을 탐구하는 새로운 길을 엽니다.