Distributed and Decentralized Optimization Algorithms via Consensus ALADIN

기술 요약: 합의 ALADIN 을 통한 분산 및 탈중앙화 최적화 알고리즘

문제 정식화
본 논문은 스마트 그리드, 최적 제어, 머신러닝과 같은 응용 분야에서 중요한 구성 요소인 분산 및 탈중앙화 합의 최적화의 과제를 다룹니다. 핵심 문제는 $N$개의 에이전트가 각각 국소 목적 함수 $f_i(x_i)$를 보유하며, 이러한 함수들의 합을 최소화하면서 모든 국소 변수 $x_i$가 글로벌 변수 $z$와 합의에 도달하도록 보장하는 것 (즉, $x_i = z$) 입니다. 저자들은 두 가지 설정을 구분합니다:

1. 중앙집중식: 정보를 집계하고 조정 하위 문제를 해결하기 위한 중앙 조정자가 존재합니다.
2. 탈중앙화: 중앙 조정자가 존재하지 않으며, 에이전트들은 방향성 그래프를 통해 즉각적인 이웃과만 통신합니다. 또한, 탈중앙화 설정에는 양자화된 통신이 포함되는데, 여기서 메시지는 제한된 대역폭과 양자화 수준 ($\Delta$) 에 노출되어 정보 교환에 잠재적인 오류를 초래합니다.

본 논문은 특히 증강 라그랑지 기반 교대 방향 비정확 뉴턴 (ALADIN) 프레임워크를 합의 문제로 확장하는 것을 목표로 합니다. ALADIN 은 분산 자원 할당에서 성공을 거두었지만, 합의 최적화에 직접 적용할 때는 합의 변수에 대한 글로벌 목적 함수의 부재 (직접 헤시안 정의 방지), 중앙 조정자 또는 비방향성 그래프에 대한 의존성, 그리고 2 차 정보 전송의 높은 대역폭 비용과 같은 구조적 어려움에 직면합니다.

방법론
저자들은 표준 ALADIN 에서 사용하는 일반적인 결합 2 차 계획법 (QP) 을 합의 특화 QP 로 대체하는 합의 ALADIN (C-ALADIN) 프레임워크를 제안합니다. 방법론은 1 차 및 2 차 구현을 각각 제공하는 중앙집중식 및 탈중앙화 변형으로 나뉩니다.

1. 중앙집중식 C-ALADIN:

   • 2 차 변형 (알고리즘 1): 에이전트들은 국소 증강 라그랑지 하위 문제를 해결하고 업데이트된 1 차 변수만 조정자에게 전송합니다. 조정자는 수신된 데이터를 기반으로 BFGS 업데이트를 사용하여 기울기와 헤시안 근사치를 재구성하여 2 차 정보의 직접 전송을 피합니다. 대규모 합의 QP 에 대한 폐쇄형 해가 유도되어 계산 복잡성이 크게 감소합니다.
   • 1 차 변형: 헤시안 근사가 어려운 시나리오의 경우, 헤시안 행렬을 스케일링된 단위 행렬 ($B_i = \rho I$) 로 대체합니다. 이는 업데이트 규칙을 합의 ADMM 과 유사한 형태로 단순화하지만 ALADIN 구조는 유지합니다.

2. 양자화된 통신을 갖춘 탈중앙화 C-ALADIN:

   • 1 차 (식 27): 에이전트들은 국소 최적화를 수행한 후 유한 시간 양자화 평균 합의 (FQAC) 프로토콜 (알고리즘 2) 을 사용하여 글로벌 변수와 기울기를 추정합니다. 이 프로토콜은 방향성 그래프에서 작동하며 비대칭 미드라이즈 양자화기를 사용합니다.
   • 2 차 (알고리즘 3 및 4): 비볼록 문제를 위해 두 가지 변형이 제안됩니다:
     • 이중 레벨 (알고리즘 3): 내부 루프에서 탈중앙화 1 차 C-ALADIN 을 사용하여 합의 QP 를 해결합니다.
     • 근사 (알고리즘 4): FQAC 프로토콜을 통해 1 차 변수와 기울기의 평균을 추정하고 로컬에서 BFGS 헤시안 근사를 복구함으로써 헤시안 행렬의 부정확한 집계를 사용합니다.

주요 기여
본 논문은 다음과 같은 구체적인 기여를 문헌에 제공합니다:

• C-ALADIN 프레임워크: 자원 할당 스타일 결합을 자연스러운 합의 QP 로 대체하는 합의 제약을 위한 맞춤형 ALADIN 형식을 도입합니다.
• 효율적인 2 차 방법: 조정자 (중앙집중식) 또는 로컬 추정 (탈중앙화) 에서 정보를 재구성하여 직접 헤시안 전송을 피하는 2 차 C-ALADIN 을 개발하여 빠른 국소 수렴성을 유지하면서 통신 오버헤드를 줄입니다.
• 방향성 그래프를 통한 탈중앙화: 중앙 조정자 없이 작동하고 방향성 통신 토폴로지에서 기능하는 완전한 탈중앙화 변형을 제안합니다.
• 양자화된 통신: 양자화된 유한 시간 합의 프로토콜을 ALADIN 프레임워크에 통합하여 대역폭 제약 하에서 작동할 수 있도록 합니다.
• 수렴 보장:
  • 볼록 문제에 대해 전역 수렴을 확립합니다 (중앙집중식 및 탈중앙화 모두).
  • 비볼록 문제에 대해 국소 수렴을 확립합니다.
  • 탈중앙화 양자화 사례의 경우, 반복문이 양자화 수준 $\Delta$에 의해 결정된 최적점의 근방으로 수렴함을 증명합니다.

결과
볼록 (분산 최소제곱) 및 비볼록 (센서 할당) 문제에 대해 수치 시뮬레이션이 수행되었습니다.

• 볼록 사례: 제안된 1 차 C-ALADIN 은 합의 ADMM 및 기타 최첨단 방법 (예: Pull-FTERC, AsyAD-ADMM) 에 비해 가속화된 수렴을 보여주었습니다. 탈중앙화 양자화 버전은 통신 효율성 (양자화를 통한 대역폭 감소) 과 해의 정확성 사이의 유리한 균형을 달성했습니다.
• 비볼록 사례: 2 차 변형 (알고리즘 1, 3, 4) 은 정상점의 근방으로 성공적으로 수렴했습니다. 반면, 1 차 변형은 이 설정에서 발산하여 비볼록 합의에 대한 2 차 정보의 필요성을 강조했습니다. 탈중앙화 2 차 변형 (알고리즘 3 및 4) 은 중앙집중식 알고리즘 1 과 비교 가능한 수렴 속도를 유지한 반면, GIANT 와 같은 기존 방법은 테스트된 특정 비볼록 사례에서 수렴하지 못했습니다.
• 양자화 영향: 결과는 더 작은 양자화 수준 ($\Delta$) 이 더 높은 정확도를 산출하는 반면, 더 큰 수준은 대역폭 사용을 줄인다는 것을 확인했으며, 이는 유도된 이론적 오차 경계와 일치합니다.

의의 및 주장
본 논문은 C-ALADIN 이 합의 제약을 위한 ALADIN 맞춤화, 방향성 그래프를 통한 탈중앙화 허용, 양자화된 통신 지원을 통해 이전에 분리되어 있던 세 가지 과제를 통합함으로써 기존 문헌의 중요한 공백을 메운다고 주장합니다. 저자들은 기존 탈중앙화 접근법에 비해 통신 및 계산 비용을 크게 줄이면서도 2 차 방법의 빠른 수렴 특성을 유지한다고 주장합니다.

이 연구는 전형적인 ALADIN 이 재형식을 통해 이론적으로 이러한 문제를 해결할 수 있지만, 그러한 접근 방식은 상당한 구현 복잡성과 오버헤드를 초래한다고 강조합니다. C-ALADIN 은 더 자연스럽고 효율적인 구조적 대안을 제공합니다. 본 논문은 제안된 알고리즘이 제한된 통신 대역폭과 비볼록 목적 함수가 있는 환경에서 대규모 분산 최적화를 위한 강력한 솔루션을 제공한다고 결론지으며, 수렴 속도에 대한 페널티 매개변수 $\rho$의 영향에 대한 이론적 특성화는 향후 연구의 미해결 과제로 남아 있음을 인정합니다.