半正定单调变分不等式CPC算法的O(1/t)收敛率

半正定单调变分不等式CPC算法只需要计算迭代点的函数值,可以解决一类没有显式表达式的半正定单调变分不等式问题.最近A.Nemirovski(SIAM J Optimiz,2005,15:229-251.)给出的prox-类算法的计算复杂性分析表明了外梯度算法在满足单调Lipschitz-连续时具有O(1/t)的收敛率;随后相关文献在一定的条件下给出了投影收缩算法、交替方向法和Douglas-Rachford法的计算复杂性分析.受到上述计算复杂性工作的启发,利用半正定单调变分不等式的基本性质和柯西施瓦兹不等式,在一定的假设条件下,给出了半正定单调变分不等式CPC算法O(1/t)收敛率的证明.

On the O(1/t) Convergence Rate of CPC Method for Semidefinite Monotone Variational Inequalities

The Correction Projection and Contraction Method(CPC Method) can solve a kind of semidefinite monotone variational inequalities without the manifestation expression of function by only computing the function value at the iteration point.Recently,A.Nemirovski(SIAM J Optim,2005,15:229-251.) proposed the efficiency estimate of prox-type method,and his analysis indicates that the extragradient method has O(1/t) convergence rate for variational inequalities with Lipschitz continuous monotone operators.Subsequently,B.S.He and X.M.Yuan give out the complexity of the projection and contraction method,the alternating direction method as well as the Douglas-Rachford operator splitting method under some appropriate conditions.Inspired by the encouraging achievement in estimating convergence rate,we establish that the CPC method has O(1/t) convergence rate for semidefinite monotone variational inequality under some suitable conditions by adopting the basic properties of semidefinite monotone variational inequalities and Cauchy Schwarz inequality in this paper.