一类正则化参数自由的线性约束凸优化问题的预测-校正算法

我们对文章的结构做这样的安排:第二节给出本文需要的预备知识;第三节简述单个目标函数问题(1.1)的己有算法和求解可能遇到的困难,第四节给出解决问题的预测-校正方法;第五节和第六节对问题(1.2)分别陈述己有方法的固有困难和我们提出的解决方案.最后,在第七节中,我们为提出的方法给出统一的算法框架,证明这类算法的收敛性和遍历意义下的收敛速率,同时给出我们的一些结论.

A CLASS OF PREDICTION-CORRECTION ALGORITHMS WITH FREE REGULARIZATION PARAMETERS FOR LINEARLY CONSTRAINT CONVEX OPTIMIZATION

Augmented Lagrange Method(ALM) and Alternating direction method of multipliers(ADMM)have been widely used in linearly constrained convex optimization.Take ALM as an example,the form of the sub-problem is min{f(x)+q^Tx+1/2||A(x-x^K)||^2X∈X}.In some practical applications,the above sub-problem is not so easy to be solved becaused of the structure of the matrix A.In these situation,the remedy is to use the "linearized"versions of ALM,which convert the sub-problems to the form min {f(x)+q^Tx+τ/2||x-x^k||^2|x∈x}.This can be viewed as substituting the term||A(x-x^k)||^2 by τ||x-x^2||^2.In order to ensure the convergence,the existing method needs τ to be greater than the largest eigenvalue of A^TA.Usually,this requirement will lead a slow convergence.In order to overcome this disadvantage,this paper proposes a class of new predictioncorrection method,which nees an O(n^2)load to calculate the step size in each correction step,but no more conditions are required for the parameter r>0.