Abstrakt. Vi presenterar en ny accelererad primal-dual (APD) metod för att lösa en klass av deterministiska och stokastiska sadel point problem (SPP). Den grundläggande idén med denna algoritm är att införliva ett flerstegsaccelerationssystem i den primära metoden utan att jämna ut den objektiva funktionen. För deterministisk SPP uppnår APD-metoden samma optimala konvergenshastighet som Nesterovs utjämningsteknik. Vår stokastiska APD metod uppvisar en optimal grad av konvergens för stokastiska SPP inte bara i termer av dess beroende av antalet iteration, men också på en mängd olika problemparametrar. Såvitt vi vet är det första gången som en sådan optimal algoritm har utvecklats för stokastisk SPP i litteraturen. Dessutom, för både deterministiska och stokastiska SPP, de utvecklade APD algoritmer kan hantera situationen när den genomförbara regionen är obegränsad, så länge en sadelpunkt finns. I det obundna fallet införlivar vi det modifierade termineringskriteriet som infördes av Monteiro och Svaiter för att lösa SPP-problem som utgör monoton integration, och visar att konvergensgraden för APD-metoden beror på avståndet från utgångspunkten till uppsättningen av optimala lösningar.
REF föreslog en accelererad variant av denna algoritm när G är smidig och etablerat en optimal hastighet av O(
Optimal Primal-Dual Methods for a Class of Saddle Point Problems
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Computer Science', 'Mathematics']}