An Overview and Comparison of Spectral Bundle Methods for Primal and Dual Semidefinite Programs

기술 요약: 프라이멀 및 듀얼 준정부호 계획법을 위한 스펙트럼 번들 방법론

문제 정의
준정부호 계획법(Semidefinite Programs, SDPs)은 양의 준정부호(positive semidefinite, PSD) 행렬의 원뿔 위에서 선형 제약 조건을 갖는 선형 목적 함수를 포함하는 기초적인 볼록 최적화 문제 클래스이다. 2차 내부점 방법(interior-point methods, IPMs)은 임의의 정밀도로 SDP를 다항 시간 내에 해결할 수 있지만, 밀집되고 조건수가 나쁜 선형 시스템을 풀어야 하는 대규모 실제 응용 분야에 적용할 때 계산 및 메모리 병목 현상을 겪는 경우가 많다. 1차 방법(first-order methods, FOMs)은 확장 가능한 대안으로 부상하였으며, 특히 스펙트럼 번들 방법(spectral bundle methods)은 저계수(low-rank) 해를 갖는 대규모 SDP에 매우 효과적이다.

역사적으로 헬름베르트(Helmberg)와 렌들(Rendl)에 의해 개척된 스펙트럼 번들 방법은 오직 SDP의 듀얼(dual) 형태를 해결하기 위해서만 개발되어 왔다. 이러한 방법들은 프라이멀(primal) SDP가 저계수 해를 가질 때 탁월한 성능을 발휘하며, 이는 조합 최적화 및 위상 복원(phase retrieval) 분야에서 흔히 나타나는 시나리오이다. 그러나 모멘트/합의 제곱(moment/sum-of-squares, SOS) 최적화 및 다항식 최적화와 같이 듀얼 해가 저계수인 경우가 자연스럽게 발생하는 많은 응용 분야에서는 기존의 듀얼 형태 스펙트럼 번들 방법이 최적이 아닌 수렴도와 효율성을 보일 수 있다. 본 논문은 프라이멀 SDP를 위해 특별히 설계된 스펙트럼 번들 방법을 개발하고 분석함으로써 이 간극을 메우고자 한다.

방법론
저자들은 프라이멀 SDP를 직접 해결하기 위해 설계된 $(r_p, r_c)$-SBMP라 명명된 새로운 계열의 스펙트럼 번들 방법을 제안한다. 이 방법론은 기존의 듀얼 스펙트럼 번들 방법(denote as $(r_p, r_c)$-SBMD)의 구조와 평행하게, 프라이멀과 듀얼 SDP 사이의 우아한 쌍대성을 반영한다.

1. 정확한 페널티화(Exact Penalization): 제약이 있는 프라이멀 SDP를 정확한 페널티 방법(exact penalty method)을 사용하여 제약이 없는(또는 단순 제약이 있는) 비매끄러운(nonsmooth) 최적화 문제로 재구성한다. 준정부호 제약 $X \succeq 0$은 $-X$의 최대 고유값을 포함하는 페널티 항을 통해 목적 함수 안으로 이동된다.
2. 번들 프레임워크(Bundle Framework): 알고리즘은 비매끄러운 목적 함수의 하부 근사 모델(lower approximation model)을 구축하는 일반적인 번들 방법 프레임워크를 채택한다. 표준 서브그레이디언트(subgradient) 방법과 달리, 번들 방법은 수렴을 개선하기 위해 정규화 전략(proximal step)을 통합한다.
3. 스펙트럼 근사(Spectral Approximation): 핵심 혁신은 스펙트럼 정보를 사용하여 특화된 하부 근사 모델을 구축하는 것이다. 각 반복(iteration)마다 알고리즘은 직교 정규 벡터 집합($P_t$)과 가중치 행렬($\bar{W}_t$)을 유지한다. 근사 모델은 다음을 활용한다:
   • 현재 정보 ($r_c$): 현재 반복물(프라이멀 방법의 경우 $-X$의)의 상위 $r_c$개 고유벡터.
   • 과거 정보 ($r_p$): 이전 반복물로부터 얻은 스펙트럼 정보의 압축된 축적.
     이를 통해 알고리즘은 매 반복마다 전체 차원의 문제가 아닌 작은 규모의 부문제(quadratic SDP, 차원 $r = r_p + r_c \ll n$)를 풀 수 있다.
4. 업데이트 전략: 알고리즘은 실제 목적 함수의 감소량이 예측된 임계값에 도달하는지 여부에 따라 참조점(프라이멀 변수)을 반복적으로 업데이트한다(하강 단계 vs. null 단계). 스펙트럼 행렬은 최적해의 영공간(null space)을 포착하도록 업데이트된다.

주요 기여

• 프라이멀 스펙트럼 번들 방법: 본 논문은 프라이멀 SDP를 명시적으로 해결하기 위해 설계된 최초의 스펙트럼 번들 방법 계열인 $(r_p, r_c)$-SBMP를 소개한다. 이는 기존의 듀얼 중심 방법들을 보완한다.
• 수렴 분석:
  • 아선형 수렴(Sublinear Convergence): 저자들은 표준 가정(Slater 조건 및 제약 조건의 선형 독립성) 하에서 비용 값 격차, 프라이멀 타당성, 듀얼 타당성 및 듀얼리티 격차에 대해 $O(1/\epsilon^3)$ 수렴 속도를 입증한다.
  • 선형 수렴(Linear Convergence): 엄격한 상보성(strict complementarity) 가정 하에, 그리고 현재 고유벡터의 수($r_c$)가 듀얼 최적해의 영공간 차원을 초과할 때, 이 방법은 $O(1/\epsilon)$의 선형 수렴 속도를 달enc한다.
• 쌍대성 및 대칭성: 논문은 프라이멀과 듀얼 공식 간의 상세한 비교를 제공하며, 매개변수 및 수렴 동작의 대칭성을 강조한다. 또한 알고리즘 선택이 특정 SDP 인스턴스의 랭크 특성에 따라 달라져야 함을 명확히 한다:
  • 기존 듀얼 방법($(r_p, r_c)$-SBMD)은 프라이멀 해가 저계수일 때 최적이다.
  • 새로운 프라이멀 방법($(r_p, r_c)$-SBMP)은 듀얼 해가 저계수일 때 최적이다.
• 오픈 소스 구현: 저자들은 프라이멀 및 듀얼 스펙트럼 번들 방법 모두에 대한 오픈 소스 MATLAB 구현을 제공하여, 기존 구현들이 쉽게 접근 가능하지 않았던 간극을 메운다.

결과
이론적 결과는 대규모 문제들에 대한 광범 sel한 수치 실험을 통해 검증되었다:

1. 무작위 SDP: 알려진 저계수 프라이멀 또는 듀얼 해를 갖는 무작위 생성 SDP에 대한 실험은, 저계수 특성에 일치하는 알고리즘(예: 저계수 듀얼를 위한 SBMP)이 빠른 선형 수렴을 달성하는 반면, 일치하지 않는 알고리즘은 느린 아선형 수렴을 보임을 확인시켜 준다.
2. Max-Cut 문제: 일반적으로 저계수 프라이멀 해를 갖는 Max-Cut 완화 문제의 경우, 듀얼 스펙트럼 번들 방법(SBMD)이 정확도와 수렴 속도 측면에서 프라이멀 방법을 크게 앞선다.
3. 다항식 최적화 (SOS): 일반적으로 저계수 듀얼 해를 허용하는 다항식 최적화의 SOS 완화 문제에 대해, 새로운 프라이멀 스펙트럼 번들 방법(SBMP)이 우수한 성능을 보여준다.
   • 베이스라인과의 비교: 구(sphere) 위의 4차 다항식 최적화 문제를 해결함에 있어, $(r_p, r_c)$-SBMP는 내부점 방법(SDPT3, MOSEK) 및 기타 1차 방법(CDCS, SDPNAL+)을 포함한 최첨단 솔버들을 지속적으로 능가하였다.
   • 확장성: SDPT3는 메모리 제약으로 인해 실패하였고 MOSEK은 더 큰 인스턴스에서 어려움을 겪었으나, SBMP는 테스트된 모든 인스턴스를 높은 정확도로 합리적인 시간 내에 해결하였으며, 종종 CDCS보다 10배 더 빠르고 SDPNAL+보다 더 나은 듀얼리티 격차 성능을 보였다.

의의
본 논문은 $(r_p, r_c)$-SBMP의 개발이 기존의 스펙트럼 번들 방법으로는 효율적으로 처리하기 어려웠던 특정 클래스의 대규모 SDP를 해결하기 위한 중요한 도구를 제공한다고 주장한다. 듀얼 해의 저계수 구조(SOS 및 모멘트 문제에서 흔함)를 활용함으로써, 이 새로운 방법은 최첨단 수준의 효율성과 확장성을 달성한다. 본 연구는 프라이멀 및 듀얼 스펙트럼 번들 방법에 대한 대칭적인 이론적 프레임워크를 확립하여, 실무자들이 자신의 특정 SDP 공식의 랭크 특성에 기반하여 알고리즘을 선택할 수 있는 명확한 가이드라인을 제공한다. 오픈 소스 공개는 최적화 커뮤니티에서 이러한 방법들의 채택을 더욱 촉진한다.