Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProximal gradient flow and Douglas-Rachford splitting dynamics: global exponential stability via integral quadratic constraints
103
0
0.0
(
0
)
Added by
Mihailo Jovanovic
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Many large-scale and distributed optimization problems can be brought into a composite form in which the objective function is given by the sum of a smooth term and a nonsmooth regularizer. Such problems can be solved via a proximal gradient method and its variants, thereby generalizing gradient descent to a nonsmooth setup. In this paper, we view proximal algorithms as dynamical systems and leverage techniques from control theory to study their global properties. In particular, for problems with strongly convex objective functions, we utilize the theory of integral quadratic constraints to prove the global exponential stability of the equilibrium points of the differential equations that govern the evolution of proximal gradient and Douglas-Rachford splitting flows. In our analysis, we use the fact that these algorithms can be interpreted as variable-metric gradient methods on the suitable envelopes and exploit structural properties of the nonlinear terms that arise from the gradient of the smooth part of the objective function and the proximal operator associated with the nonsmooth regularizer. We also demonstrate that these envelopes can be obtained from the augmented Lagrangian associated with the original nonsmooth problem and establish conditions for global exponential convergence even in the absence of strong convexity.
rate research
Read More
The alternating direction multiplier method (ADMM) is widely used in computer graphics for solving optimization problems that can be nonsmooth and nonconvex. It converges quickly to an approximate solution, but can take a long time to converge to a solution of high-accuracy. Previously, Anderson acceleration has been applied to ADMM, by treating it as a fixed-point iteration for the concatenation of the dual variables and a subset of the primal variables. In this paper, we note that the equivalence between ADMM and Douglas-Rachford splitting reveals that ADMM is in fact a fixed-point iteration in a lower-dimensional space. By applying Anderson acceleration to such lower-dimensional fixed-point iteration, we obtain a more effective approach for accelerating ADMM. We analyze the convergence of the proposed acceleration method on nonconvex problems, and verify its effectiveness on a variety of computer graphics problems including geometry processing and physical simulation.
Mirror descent (MD) is a powerful first-order optimization technique that subsumes several optimization algorithms including gradient descent (GD). In this work, we study the exact convergence rate of MD in both centralized and distributed cases for strongly convex and smooth problems. We view MD with a dynamical system lens and leverage quadratic constraints (QCs) to provide convergence guarantees based on the Lyapunov stability. For centralized MD, we establish a semi-definite programming (SDP) that certifies exponentially fast convergence of MD subject to a linear matrix inequality (LMI). We prove that the SDP always has a feasible solution that recovers the optimal GD rate. Next, we analyze the exponential convergence of distributed MD and characterize the rate using two LMIs. To the best of our knowledge, the exact (exponential) rate of distributed MD has not been previously explored in the literature. We present numerical results as a verification of our theory and observe that the richness of the Lyapunov function entails better (worst-case) convergence rates compared to existing works on distributed GD.
The last two decades witnessed the increasing of the interests on the absolute value equations (AVE) of finding $xinmathbb{R}^n$ such that $Ax-|x|-b=0$, where $Ain mathbb{R}^{ntimes n}$ and $bin mathbb{R}^n$. In this paper, we pay our attention on designing efficient algorithms. To this end, we reformulate AVE to a generalized linear complementarity problem (GLCP), which, among the equivalent forms, is the most economical one in the sense that it does not increase the dimension of the variables. For solving the GLCP, we propose an inexact Douglas-Rachford splitting method which can adopt a relative error tolerance. As a consequence, in the inner iteration processes, we can employ the LSQR method ([C.C. Paige and M.A. Saunders, ACM Trans. Mathe. Softw. (TOMS), 8 (1982), pp. 43--71]) to find a qualified approximate solution for each subproblem, which makes the cost per iteration very low. We prove the convergence of the algorithm and establish its global linear rate of convergence. Comparing results with the popular algorithms such as the exact generalized Newton method [O.L. Mangasarian, Optim. Lett., 1 (2007), pp. 3--8], the inexact semi-smooth Newton method [J.Y.B. Cruz, O.P. Ferreira and L.F. Prudente, Comput. Optim. Appl., 65 (2016), pp. 93--108] and the exact SOR-like method [Y.-F. Ke and C.-F. Ma, Appl. Math. Comput., 311 (2017), pp. 195--202] are reported, which indicate that the proposed algorithm is very promising. Moreover, our method also extends the range of numerically solvable of the AVE; that is, it can deal with not only the case that $|A^{-1}|<1$, the commonly used in those existing literature, but also the case where $|A^{-1}|=1$.
Douglas-Rachford splitting and its equivalent dual formulation ADMM are widely used iterative methods in composite optimization problems arising in control and machine learning applications. The performance of these algorithms depends on the choice of step size parameters, for which the optimal values are known in some specific cases, and otherwise are set heuristically. We provide a new unified method of convergence analysis and parameter selection by interpreting the algorithm as a linear dynamical system with nonlinear feedback. This approach allows us to derive a dimensionally independent matrix inequality whose feasibility is sufficient for the algorithm to converge at a specified rate. By analyzing this inequality, we are able to give performance guarantees and parameter settings of the algorithm under a variety of assumptions regarding the convexity and smoothness of the objective function. In particular, our framework enables us to obtain a new and simple proof of the O(1/k) convergence rate of the algorithm when the objective function is not strongly convex.
The Peaceman-Rachford splitting method is efficient for minimizing a convex optimization problem with a separable objective function and linear constraints. However, its convergence was not guaranteed without extra requirements. He et al. (SIAM J. Optim. 24: 1011 - 1040, 2014) proved the convergence of a strictly contractive Peaceman-Rachford splitting method by employing a suitable underdetermined relaxation factor. In this paper, we further extend the so-called strictly contractive Peaceman-Rachford splitting method by using two different relaxation factors. Besides, motivated by the recent advances on the ADMM type method with indefinite proximal terms, we employ the indefinite proximal term in the strictly contractive Peaceman-Rachford splitting method. We show that the proposed indefinite-proximal strictly contractive Peaceman-Rachford splitting method is convergent and also prove the $o(1/t)$ convergence rate in the nonergodic sense. The numerical tests on the $l_1$ regularized least square problem demonstrate the efficiency of the proposed method.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
