확장 가능한 반정방정식 프로그래밍을 향하여: 최적 메트릭 ADMM과 최악의 성능 보장

반정방정식 프로그래밍(SDP)의 많은 용도와 내부 점 방법(IPMs)을 통한 보편적인 해법에도 불구하고, 실제 대규모 문제에 거의 적용되지 않습니다. 이는 주로 데이터 크기에 따라 나쁜 지수적으로 증가하는 IPMs의 계산 비용 때문입니다. ADMM과 같은 1차 알고리즘이 이 문제를 완화할 수 있지만, 확장성 개선은 미흡한 것으로 보입니다. 이 연구에서는 비유클리드 메트릭 공간을 활용하여 ADMM의 추가 가속화를 달성하는 것을 목표로 하며, 모든 것을 닫힌 형태의 표현으로 유지합니다. 효율성 증가는 스칼라 스텝 크기에 비해 변수 메트릭의 추가 자유도에서 나오며, 이는 추가적인 불안정 구조를 포착할 수 있게 해줍니다. 응용 면에서는 이중화 과정 후 자연스럽게 SDP 형태로 나타나는 이차 제한 이차 프로그램(QCQP)을 고려합니다. 반정방정식 이완으로 알려진 이 기술은 다양한 분야에서 특히 무선 통신에 중요하게 사용됩니다. 수치적으로, 우리는 확장성 속성이 상당히 개선되었음을 관찰합니다. 데이터 생성 과정에 따라, 추가 가속은 스칼라 매개변수 효율 한계를 쉽게 초과할 수 있으며, 데이터 조건이 악화될수록 이점이 빠르게 증가합니다.