Non-Negative Conjugate Gradients

기술 요약: 비음수 공액 기울기법 (Non-Negative Conjugate Gradients)

문제 정의
본 논문은 다음과 같은 엄격한 볼록성(strictly convex)을 가진 비음수 이차 계획법(NNQP)을 다룹니다:
$$\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^\top A x - b^\top x \quad \text{subject to} \quad x \ge 0,$$
여기서 $A$는 대칭 양의 정부호(symmetric positive definite, SPD) 행렬입니다. 저자들은 또한 선형 제약 조건 $Bx = c$가 포함된 등식 확장 변형 모델도 고려합니다. 공액 기울기(Conjugate Gradient, CG)법은 무제약 SPD 시스템 $Ax=b$를 위한 표준 솔버이지만, 비음수 제약 조건$x \ge 0$을 본질적으로 준수하지는 못합니다. 기존의 가용 점(feasible-point) 방법들(예: 투영 기울기법, MPRGP)은 종종 느린 수렴 속도($O(\kappa)$)를 보이거나, 외부 증강 라그랑주(augmented-Lagrangian) 루프를 도입하지 않고는 일반적인 등식 제약 조건을 처리하는 데 어려움을 겪습니다. 본 연구의 목표는 CG의 $O(\sqrt{\kappa})$ 수렴 속도와 행렬 프리(matrix-free) 역량을 희생하지 않으면서 이 문제를 해결하는 것입니다.

방법론
제안된 방법인 **비음수 공액 기울기법(Non-Negative Conjugate Gradients, NNCG)**은 CG 솔버를 프라이멀-듀얼 활성 집합(primal-dual active-set) 외부 루프로 감싸는 구조를 가집니다. 핵심 전략은 다음과 같습니다:

1. 활성 집합 축소 (Active-Set Reduction): 알고리즘은 $x_i > 0$인 인덱스의 "자유 집합(free set)" $F$를 유지합니다. 이 집 set 위에서 경계 제약 조건은 비활성화되며, 이는 무제약 SPD 시스템 $A_F x_F = b_F$ (또는 등식 확장 케이스의 경우 saddle-point 시스템)로 축소됩니다.
2. 행렬 프리 내부 솔브 (Matrix-Free Inner Solve): 내부 시스템은 CG를 사용하여 해결됩니다. 결정적으로, 이 방법은 행렬 프리 방식입니다. 만약 $A = M^\top M$이라면, 연산자 $v \mapsto A_F v$는 $M_F^\top (M_F v)$로 계산되어, $A$의 $O(n^2)$ 저장 공간을 피하고 $M$과의 두 번의 행렬-벡터 곱만으로 수행됩니다.
3. 프라이멀-듀얼 토글링 (Primal-Dual Toggling):
   • 프라이멀 단계: 음수가 되는 자유 변수 $x_i$는 $F$에서 제외됩니다 (0으로 설정).
   • 듀얼 단계: 음의 축소 기울기 $s_i = (Ax)_i - b_i$를 갖는 경계 변수 $x_i = 0$은 $F$에 수용됩니다.
   • 이러한 토글링은 선형 상보성 문제(LCP) $(A, -b)$의 주 원소 피벗(principal pivots)에 해당합니다.
4. 종료 전략: 퇴화(degeneracy) 상황에서도 유한 종료를 보장하기 위해, 본 방법은 블랜드의 최소 인덱스 폴백(least-index Bland fallback)(단일 인덱스 교환)에 의해 보호되는 블록 주 원소 피벗 경로(fast batch exchanges)를 채택합니다. J´udice와 Pires [21] 및 Murty [25]에 기반한 이 구조는 유일한 전역 최적해로의 수렴을 보장합니다.
5. 불완전성 처리 (Handling Inexactness): 핵심적인 이론적 기여는, 만약 CG 내부 잔차(residual)가 "결정 마진(decision margin)"(정확한 궤적에서 나타나는 가장 작은 비영(non-zero) 프라이멀 또는 듀얼 값)에 비해 충분히 작다면, 불완전한 루프가 정확한 루프와 동일한 부호 결정을 내린다는 것을 증명한 것입니다. 이는 유한 종료 보증을 행렬 프리의 불완전한 체제로 전이시킵니다.
6. 정규화 및 전처리 (Regularization and Preconditioning): 리지/티코노프 분할(ridge/Tikhonov split) $A_\alpha = (1-\alpha)A + \alpha R^\top R$을 사용하여 조건수 $\kappa$를 압축하고, 원래 $A$가 계수 부족(rank-deficient) 상태이더라도 $A_\alpha$가 P-행렬(엄격한 양의 정부호 주 부분 행렬)로 유지되도록 합니다. 내부 CG 솔브를 가속화하기 위해 전처리(예: Jacobi, Nyström)가 적용됩니다.

주요 기여

• 불완전 솔브에 대한 유한 종료 보증: 본 논문은 (이전에 정확한 솔브에서만 유효했던) 블록 주 원소 피벗의 유한 종료 보증을 불완전한 행렬 프리 CG 체제로 확장했습니다. 보조정리 4.1은 내부 잔차가 결정 마진과 결합되면, 근사 루프가 정확한 자유 집합 궤적을 따라간다는 것을 보여줍니다.
• 등식 제약 조건의 직접 처리: 일반적인 등식 $Bx=c$에 대해 외부 증강 라그랑주 루프가 필요한 가용 점 방법들과 달리, 이 방법은 슈어 보완(Schur complement)을 통해 승수를 분석적으로 제거하여 등식 확장 문제를 활성 집합 프레임워크 내에서 직접 해결합니다.
• 행렬 프리 효율성: 솔버는 $A$를 구성하지 않고 작동하며, $O(n)$의 작업 메모리와 각 외부 단계당 $O(\sqrt{\kappa})$의 내부 CG 반복을 요구합니다.
• 웜 스타팅 (Warm-Starting): 본 방법은 매개변수 가족(예: 효율적 프런티어)에 대한 웜 스타팅을 지원하며, 이전 단계의 자유 집합과 해를 초기값으로 사용하여 서포트(support)가 안정적인 경우 외부 반복 횟수를 획기적으로 줄입니다.

결과

• 합성 성능: 심어진 최적점(planted optima)이 있는 합성 SPD 문제에서, 알고리즘은 최대 6번의 외부 단계 내에 최적점에 도달합니다. 총 CG 내부 반복 횟수는 조건수 $\kappa$에 대해 아선형적으로 증가하며(로그-로그 그래프에서 기울기 $\approx 0.35$), 이는 $O(\sqrt{\kappa})$ 동작을 확인시켜 줍니다.
• 퇴화 및 사이클링: 가드되지 않은 배치 피벗(unguarded batch pivots)에서 사이클링을 일으키도록 설계된 적대적 안티-상관 설계(anti-correlated designs) 패밀리에 대해, 제안된 폴백 메커니즘은 루프를 성공적으로 종료시킨 반면, 가드되지 않은 경로는 사이클링을 보였습니다.
• 계수 부족 (Rank Deficiency): 계수 부족 레짐($m < n$)에서, 정규화되지 않은 솔버는 수렴하거나 최적성을 인증하는 데 실패합니다. 작은 정규화 파라미터 $\alpha > 0$를 도입하면 P-행렬 특성이 복원되어 수렴과 KKT 인증이 보장됩니다.
• 베이스라인과의 비교:
  • 투영 기울기법 대비: NNCG는 불량 조건(ill-conditioned) 문제에서 투영 기울기법보다 $\sqrt{\kappa}$ 배 더 우수한 성능을 보입니다.
  • Lawson-Hanson 및 내부 점 방법 대비: 조립된 밀집 문제에서, NNCG(내부 직접 솔브 사용 시)는 블록 피벗이 단 자릿수 외부 단계 내에 최적 서포트에 도달하기 때문에 Lawson-Hanson보다 훨씬 빠릅니다 (예: $n=2000$에서 Lawson-Hanson보다 48배 빠름).
  • 대규모 밀집 솔버 대비: 행렬 프리 디블러링(deblurring) 응용 분야($n=65,536$)에서, 밀집 솔버(Lawson-Hanson, Clarabel)는 메모리 제약($O(n^2)$ 저장)으로 인해 실패합니다. NNCG는 $O(n)$ 메모리와 수 초 내에 이를 해결하는 반면, 밀집 솔버는 연산자를 생성조차 할 수 없습니다.
• 실제 응용: 하이퍼스펙트럴 언믹싱 문제(Cuprite scene, $n=498$ 시그니처)에서, 본 방법은 웜 스타팅을 통해 콜드 스타트 실행 대비 672배의 속도 향상을 달ometric하며, 가용 점 방법들이 임계값 처리가 필요한 근사 해를 반환하는 것과 달리 정확한 KKT 인증(단일 광물 서포트 식별)을 제공합니다.

의의 및 주장
본 논문은 NNCG가 퇴화 및 불완전한 내부 솔브가 존재하는 상황에서도 비음수 이차 계획법에 대한 무조건적인 유한 종료 보증을 제공한다고 주장합니다. 이는 크릴로프 부공간(Krylov subspace) 방법(CG)의 효율성과 활성 집합 방법의 조합론적 최적성 보증 사이의 간극을 메웁니다.

저자들은 이 방법이 응용 분야에 구애받지 않으며(application-agnostic), 외부 루프 없이도 경계 제약 조건과 일반 선형 등식을 모두 처리할 수 있음을 강조합니다. 본 방법은 비음수 직교 영역만을 다루지만(일반 박스 제약은 아님), 가용 점 방법(MPRGP 등)에 비해 정확한 KKT 인증을 제공하고 등식 제측을 네이티브하게 처리한다는 뚜렷한 장점을 가집니다. 본 연구는 "결정 대 결정(decision-for-decision)" 전이가 정확한 솔브에서 불완전한 솔브로 가능하다는 것을 입증함으로써, 주 원소 피벗의 견고함과 행렬 프리 크릴로프 솔버의 확장성을 결합할 수 있음을 보여주었습니다.