Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA class of inexact modified Newton-type iteration methods for solving the generalized absolute value equations
112
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
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.
rate research
Read More
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 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$.
In this paper, some useful necessary and sufficient conditions for the unique solution of the generalized absolute value equation (GAVE) $Ax-B|x|=b$ with $A, Bin mathbb{R}^{ntimes n}$ from the optimization field are first presented, which cover the fundamental theorem for the unique solution of the linear system $Ax=b$ with $Ain mathbb{R}^{ntimes n}$. Not only that, some new sufficient conditions for the unique solution of the GAVE are obtained, which are weaker than the previous published works.
We develop a general framework for designing conservative numerical methods based on summation by parts operators and split forms in space, combined with relaxation Runge-Kutta methods in time. We apply this framework to create new classes of fully-discrete conservative methods for several nonlinear dispersive wave equations: Benjamin-Bona-Mahony (BBM), Fornberg-Whitham, Camassa-Holm, Degasperis-Procesi, Holm-Hone, and the BBM-BBM system. These full discretizations conserve all linear invariants and one nonlinear invariant for each system. The spatial semidiscretizations include finite difference, spectral collocation, and both discontinuous and continuous finite element methods. The time discretization is essentially explicit, using relaxation Runge-Kutta methods. We implement some specific schemes from among the derived classes, and demonstrate their favorable properties through numerical tests.
For solving large-scale non-convex problems, we propose inexact variants of trust region and adaptive cubic regularization methods, which, to increase efficiency, incorporate various approximations. In particular, in addition to approximate sub-problem solves, both the Hessian and the gradient are suitably approximated. Using rather mild conditions on such approximations, we show that our proposed inexact methods achieve similar optimal worst-case iteration complexities as the exact counterparts. Our proposed algorithms, and their respective theoretical analysis, do not require knowledge of any unknowable problem-related quantities, and hence are easily implementable in practice. In the context of finite-sum problems, we then explore randomized sub-sampling methods as ways to construct the gradient and Hessian approximations and examine the empirical performance of our algorithms on some real datasets.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
