합의 제약이 있는 볼록 최적화를 위한 확률적 미러 하강법

. 미러 하강 알고리즘은 최적화 모델의 기하학에 맞게 미러 맵을 적응시키는 것이 유익한 상황에서 효과적임이 알려져 있습니다. 그러나 분산 최적화 문제에서 미러 맵의 기하학적 효과는 이전에 다루어지지 않았습니다. 본 논문에서는 추가 잡음 하의 연속 시간에서의 정확한 분산 미러 하강 알고리즘을 연구합니다. 우리는 볼록 최적화 설정에 대해 제안된 동역학의 선형 수렴 속도를 확립합니다. 우리의 분석은 증강 라그랑지안과 그것의 기울기 추적에 대한 관계에서 동기를 얻습니다. 분산 설정에서 미러 맵의 이점을 더 탐구하기 위해 라그랑지안 이중 변수에 대해 추가 미러 맵을 가진 우리 알고리즘의 전처리 변형을 제시합니다. 이는 우리 방법이 기본 변수의 기하학과 합의 제약의 기하학에 모두 적응할 수 있게 합니다. 우리는 또한 제안된 방법을 위한 가우스-사이델 유형의 이산화 방식을 제안하고 선형 수렴 속도를 확립합니다. 특정 문제 클래스에 대해 우리는 알고리즘의 수렴 속도에 대한 그래프의 스펙트럴 속성의 영향을 완화하는 미러 맵을 식별합니다. 수치 실험을 사용하여 우리는 제약이 있는 경우와 없는 경우 모두에서 볼록 모델에 대한 방법론의 효율성을 입증합니다. 우리의 결과는 제안된 방법이 다른 방법들보다 우수하며, 특히 모델의 기하학이 표준 유클리드 노름으로 포착되지 않는 시나리오에서 뛰어남을 보여줍니다.키워드: 분산 최적화, 미러 하강, 전처리, 상호작용 입자, 확률적 최적화, MSC 코드: 65K1068, Q8760, G0768, W15