In this work, we revisit a discrete implementation of the primal-descent dual-ascent gradient method applied to saddle-point optimization problems. Through a short proof, we establish linear (exponential) convergence of the algorithm for strongly-convex cost functions with Lipschitz continuous gradients. Unlike previous studies, we provide explicit upper bounds on the step-size parameters for stable behavior and on the resulting convergence rate and highlight the importance of having two different primal and dual step-sizes. We also explain the effect of the augmented Lagrangian penalty term on the algorithm stability and performance for the distributed minimization of aggregate cost functions over multi-agent networks.
Recently many first-order primal-dual gradient algorithms have been used to solve distributed optimization problems -- see @cite_27 @cite_28 @cite_1 @cite_20 @cite_3 and references therein, which are based on augmented Lagrangian (AL) formulations and incremental updates. They have been shown to achieve linear convergence under strong-convexity even though the consensus constraint matrix is not full rank. However, the analysis techniques used to establish the convergence of these methods depend on the particular consensus constraint matrix. Moreover, unlike these works, due to our unified Lagrangian and AL framework, we clarify the effect of the AL penalty term on the performance of these types of distributed algorithms. The work @cite_17 focuses on distributed optimization problems for mean-square-error costs and studies non-incremental primal-dual methods with identical step-sizes. It was found in @cite_17 that unlike AL methods, Lagrangian methods suffer from stability issues when the individual costs are not strongly-convex. This work generalize this result to general costs; moreover, we show that Lagrangian methods can use larger step-sizes compared to AL methods and, more importantly, we show how the AL penalty term affects the convergence rate.
@cite_28 @cite_1 @cite_3 @cite_27 @cite_20 @cite_17
2969771825 2075677880 2768546550 1830979757
Augmented Lagrangian method (ALM) has been popularly used for solving constrained optimization problems. Practically, subproblems for updating primal variables in the framework of ALM usually can only be solved inexactly. The convergence and local convergence speed of ALM have been extensively studied. However, the global convergence rate of the inexact ALM is still open for problems with nonlinear inequality constraints. In this paper, we work on general convex programs with both equality and inequality constraints. For these problems, we establish the global convergence rate of the inexact ALM and estimate its iteration complexity in terms of the number of gradient evaluations to produce a primal and or primal-dual solution with a specified accuracy. We first establish an ergodic convergence rate result of the inexact ALM that uses constant penalty parameters or geometrically increasing penalty parameters. Based on the convergence rate result, we then apply Nesterov’s optimal first-order method on each primal subproblem and estimate the iteration complexity of the inexact ALM. We show that if the objective is convex, then (O( ^ -1 ) ) gradient evaluations are sufficient to guarantee a primal ( )-solution in terms of both primal objective and feasibility violation. If the objective is strongly convex, the result can be improved to (O( ^ - 1 2 | |) ). To produce a primal-dual ( )-solution, more gradient evaluations are needed for convex case, and the number is (O( ^ - 4 3 ) ), while for strongly convex case, the number is still (O( ^ - 1 2 | |) ). Finally, we establish a nonergodic convergence rate result of the inexact ALM that uses geometrically increasing penalty parameters. This result is established only for the primal problem. We show that the nonergodic iteration complexity result is in the same order as that for the ergodic result. Numerical experiments on quadratically constrained quadratic programming are conducted to compare the performance of the inexact ALM with different settings. This paper studies distributed primal-dual strategies for adaptation and learning over networks from streaming data. Two first-order methods are considered based on the Arrow-Hurwicz (AH) and augmented Lagrangian (AL) techniques. Several revealing results are discovered in relation to the performance and stability of these strategies when employed over adaptive networks. The conclusions establish that the advantages that these methods exhibit for deterministic optimization problems do not necessarily carry over to stochastic optimization problems. It is found that they have narrower stability ranges and worse steady-state mean-square-error performance than primal methods of the consensus and diffusion type. It is also found that the AH technique can become unstable under a partial observation model, while the other techniques are able to recover the unknown under this scenario. A method to enhance the performance of AL strategies is proposed by tying the selection of the step-size to their regularization parameter. It is shown that this method allows the AL algorithm to approach the performance of consensus and diffusion strategies but that it remains less stable than these other strategies. First-order methods have been popularly used for solving large-scale problems. However, many existing works only consider unconstrained problems or those with simple constraint. In this paper, we develop two first-order methods for constrained convex programs, for which the constraint set is represented by affine equations and smooth nonlinear inequalities. Both methods are based on the classic augmented Lagrangian function. They update the multipliers in the same way as the augmented Lagrangian method (ALM) but employ different primal variable updates. The first method, at each iteration, performs a single proximal gradient step to the primal variable, and the second method is a block update version of the first one. For the first method, we establish its global iterate convergence as well as global sublinear and local linear convergence, and for the second method, we show a global sublinear convergence result in expectation. Numerical experiments are carried out on the basis pursuit denoising and a convex quadratically constrained quadratic program to show the empirical performance of the proposed methods. Their numerical behaviors closely match the established theoretical results. In this paper, we consider augmented Lagrangian AL algorithms for solving large-scale nonlinear optimization problems that execute adaptive strategies for updating the penalty parameter. Our work is motivated by the recently proposed adaptive AL trust region method by [An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program. 152 2015, pp. 201–245.]. The first focal point of this paper is a new variant of the approach that employs a line search rather than a trust region strategy, where a critical algorithmic feature for the line search strategy is the use of convexified piecewise quadratic models of the AL function for computing the search directions. We prove global convergence guarantees for our line search algorithm that are on par with those for the previously proposed trust region method. A second focal point of this paper is the practical performance of the line search and trust region algorithm variants in Matlab software, as well as that of an adaptive penalty parameter updating strategy incorporated into the Lancelot software. We test these methods on problems from the CUTEst and COPS collections, as well as on challenging test problems related to optimal power flow. Our numerical experience suggests that the adaptive algorithms outperform traditional AL methods in terms of efficiency and reliability. As with traditional AL algorithms, the adaptive methods are matrix-free and thus represent a viable option for solving large-scale problems.