线性化乘子交替方向法的迭代复杂性  

ON THE ITERATIVE COMPLEXITY OF THE LINEARIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS

作　　者：何炳生[1] He Bingsheng(Department of Mathematics, Nanjing University, Nanjing 210093)

机构地区：[1]南京大学数学系

出　　处：《高等学校计算数学学报》2019年第2期126-149,共24页Numerical Mathematics A Journal of Chinese Universities

基　　金：国家自然科学基金项目(11871029)

摘　　要：1引言本文讨论的两个可分离目标函数的线性约束凸优化问题,它的数学形式是min{θ1(x)+θ2(y)|Ax+By=b,x∈X,y∈y},(1-1)In the last 10 years,the alternating direction met hod of multipliers (ADMM) has been widely used in convex optimization.Using ADMM to solve the convex optimization problem with separable objective function and linear constraints,the general form of the subproblem is min{f(x)+1/2||Ax-p||^2|x∈X} and minmin{g(y)+1/2||By-q||^2|y∈Y}.In some practical applications,the above sub-problems are not so easy to be solved because of the concrete structure of the matrix A and B.In these cases,people use "linearization" plus "regularization" to convert the subproblems to the form min{f(x)+1/2||x-C||^2|x∈X} and minmin{g(y)+1/2||y-d||^2|y∈Y}.This type of problems is relative easy to be solved,and the modified methods are called linearized ADMM.In this paper,we study two types of linearized ADMM under the framework of variational inequalities,prove their iterative complexity both in the point-wise and ergodic sense.

关 键 词：讨论 函数 问题 

分 类 号：O221.2[理学—运筹学与控制论] O224[理学—数学]