OPTIMAL PRIMAL-DUAL METHODS FOR A CLASS OF SADDLE POINT PROBLEMS
OPTIMAL PRIMAL-DUAL METHODS FOR A CLASS OF SADDLE POINT PROBLEMS
复制标题
DOI：
10.1137/130919362
复制
发表时间：
2014-01-01
影响因子：
3.1
通讯作者：
Ouyang, Yuyuan
中科院分区：
文献类型：
--
作者：
Chen, Yunmei;Lan, Guanghui;Ouyang, Yuyuan
提出了一种新的求解一类确定性和随机鞍点问题的加速原-对偶（APD）方法。该算法的基本思想是在原对偶方法中引入多步加速方案，而不需要对目标函数进行平滑处理。对于确定性SPP，APD方法实现了与Nesterov平滑技术相同的最佳收敛速度。我们的随机APD方法表现出最佳的收敛速度随机SPP不仅在其依赖于迭代次数，但也对各种问题的参数。据我们所知，这是第一次，这样一个最佳的算法已被开发的随机SPP在文献中。此外，对于确定性和随机SPP，只要存在鞍点，所发展的APD算法可以处理可行域无界的情况。在无界的情况下，我们将修改后的终止准则引入Monteiro和Svaiter在解决一个SPP构成的单调包含，并证明了APD方法的收敛速度取决于从初始点到最优解集的距离。一些初步的数值结果的APD方法求解确定性和随机SPPs也包括在内。
We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPPs). The basic idea of this algorithm is to incorporate a multistep acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced by Monteiro and Svaiter in solving an SPP posed as a monotone inclusion, and demonstrate that the rate of convergence of the APD method depends on the distance from the initial point to the set of optimal solutions. Some preliminary numerical results of the APD method for solving both deterministic and stochastic SPPs are also included.