标题： 一种具有$O(1/t)$收敛率的原始对偶型算法求解大规模约束凸规划问题 显示英文标题

标题： A Primal-Dual Type Algorithm with the $O(1/t)$ Convergence Rate for Large Scale Constrained Convex Programs

摘要： 本文研究了大规模约束凸规划问题，由于Hessian矩阵及其逆的计算和存储复杂度过高，这些问题通常无法通过内点法或其他牛顿型方法求解。相反，大规模约束凸规划问题通常通过梯度类方法或分解类方法来求解。经典的原始对偶次梯度方法（即Arrow-Hurwicz-Uzawa次梯度方法）是一种低复杂度算法，其收敛率为$O(1/\sqrt{t})$，其中$t$是迭代次数。如果目标函数和约束函数是可分离的，则拉格朗日对偶型方法可以将大规模凸规划问题分解为多个并行的小规模凸规划问题。经典的对偶梯度算法是拉格朗日对偶型方法的一个例子，其具有收敛率$O(1/\sqrt{t})$。最近，Yu和Neely（2015）提出了一种新的拉格朗日对偶型算法，其收敛速度更快，为$O(1/t)$。然而，如果目标函数或约束函数不可分离，在Yu和Neely（2015）中的拉格朗日对偶型方法的每次迭代都需要求解一个大规模无约束凸规划问题，这可能具有巨大的复杂性。本文提出了一种新的原始对偶型算法，该算法在每次迭代中仅涉及简单的梯度更新，并具有收敛率$O(1/t)$。 显示英文摘要

摘要： This paper considers large scale constrained convex programs, which are usually not solvable by interior point methods or other Newton-type methods due to the prohibitive computation and storage complexity for Hessians and matrix inversions. Instead, large scale constrained convex programs are often solved by gradient based methods or decomposition based methods. The conventional primal-dual subgradient method, aka, Arrow-Hurwicz-Uzawa subgradient method, is a low complexity algorithm with the $O(1/\sqrt{t})$ convergence rate, where $t$ is the number of iterations. If the objective and constraint functions are separable, the Lagrangian dual type method can decompose a large scale convex program into multiple parallel small scale convex programs. The classical dual gradient algorithm is an example of Lagrangian dual type methods and has convergence rate $O(1/\sqrt{t})$. Recently, a new Lagrangian dual type algorithm with faster $O(1/t)$ convergence is proposed in Yu and Neely (2015). However, if the objective or constraint functions are not separable, each iteration of the Lagrangian dual type method in Yu and Neely (2015) requires to solve a large scale unconstrained convex program, which can have huge complexity. This paper proposes a new primal-dual type algorithm, which only involves simple gradient updates at each iteration and has the $O(1/t)$ convergence rate.