求解凸规划及鞍点问题定制的PPA算法及其收敛速率

On the convergence rate of customized proximal point algorithm for convex optimization and saddle-point problem

线性约束的凸优化问题和鞍点问题的一阶最优性条件是一个单调变分不等式.在变分不等式框架下求解这些问题,选取适当的矩阵G,采用G-模下的PPA算法,会使迭代过程中的子问题求解变得相当容易.本文证明这类定制的PPA算法的误差界有1/k的收敛速率.

The first-order optimality condition of linearly constrained convex optimization and saddle-point problems is a monotone variational inequality.Under the framework of variational inequality,by properly selecting a matrix G,the subproblems of proximal point algorithm under G-norm can be solved easily during the iteration progress.We derive the O（1/k） convergence rate of such customized proximal point algorithm.