Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn inexact Douglas-Rachford splitting method for solving absolute value equations
180
0
0.0
(
0
)
Added by
Cairong Chen
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
In Wang et al. (J. Optim. Theory Appl., textbf{181}: 216--230, 2019), a class of effective modified Newton-tpye (MN) iteration methods are proposed for solving the generalized absolute value equations (GAVE) and it has been found that the MN iteration method involves the classical Picard iteration method as a special case. In the present paper, it will be claimed that a Douglas-Rachford splitting method for AVE is also a special case of the MN method. In addition, a class of inexact MN (IMN) iteration methods are developed to solve GAVE. Linear convergence of the IMN method is established and some specific sufficient conditions are presented for symmetric positive definite coefficient matrix. Numerical results are given to demonstrate the efficiency of the IMN iteration method.
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.
The SOR-like iteration method for solving the absolute value equations~(AVE) of finding a vector $x$ such that $Ax - |x| - b = 0$ with $ u = |A^{-1}|_2 < 1$ is investigated. The convergence conditions of the SOR-like iteration method proposed by Ke and Ma ([{em Appl. Math. Comput.}, 311:195--202, 2017]) are revisited and a new proof is given, which exhibits some insights in determining the convergent region and the optimal iteration parameter. Along this line, the optimal parameter which minimizes $|T_ u(omega)|_2$ with $$T_ u(omega) = left(begin{array}{cc} |1-omega| & omega^2 u |1-omega| & |1-omega| +omega^2 u end{array}right)$$ and the approximate optimal parameter which minimizes $eta_{ u}(omega) =max{|1-omega|, uomega^2}$ are explored. The optimal and approximate optimal parameters are iteration-independent and the bigger value of $ u$ is, the smaller convergent region of the iteration parameter $omega$ is. Numerical results are presented to demonstrate that the SOR-like iteration method with the optimal parameter is superior to that with the approximate optimal parameter proposed by Guo, Wu and Li ([{em Appl. Math. Lett.}, 97:107--113, 2019]). In some situation, the SOR-like itration method with the optimal parameter performs better, in terms of CPU time, than the generalized Newton method (Mangasarian, [{em Optim. Lett.}, 3:101--108, 2009]) for solving the AVE.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
