MirrotProxmethodbyNemirovski的一个著名算法

寻找鞍点 min⁡xmax⁡yf(x,y)\min_{x}\max_{y} f(x,y)minx​maxy​f(x,y)的一个著名算法

输入&＃xff1a;
$(\alpha ,ϵ)$-relaxed proximal oracle $\mathcal{O}(z)$ for gradient mapping $g$, distance generating $r$.

参数&＃xff1a;
迭代次数$K$

输出&＃xff1a;
点zˉK\bar{z}_{K}zˉK​,满足E[Gap(zˉ)]≤αΘK&＃43;ϵ\mathbb{E}[Gap(\bar{z})]\leq \frac{\alpha\Theta}{K}&＃43;\epsilonE[Gap(zˉ)]≤KαΘ​&＃43;ϵ.

初始化&＃xff1a;
z0&＃61;arg⁡min⁡r(z)z_{0}&＃61;\arg\min r(z)z0​&＃61;argminr(z)

for $k\&＃61;1,2,...,K$ do:
zk−1/2&＃61;O(zk−1)\quad z_{k-1/2}&＃61;\mathcal{O}(z_{k-1})zk−1/2​&＃61;O(zk−1​)
zk&＃61;Proxzk−1α(g(zk−1/2))\quad z_{k}&＃61;Prox^{\alpha}_{z_{k-1}}(g(z_{k-1/2}))zk​&＃61;Proxzk−1​α​(g(zk−1/2​))

return zˉK&＃61;1K∑k&＃61;1Kzk−1/2\bar{z}_{K}&＃61;\frac{1}{K}\sum_{k&＃61;1}^{K}z_{k-1/2}zˉK​&＃61;K1​∑k&＃61;1K​zk−1/2​