We investigate a kind of generalized equations involving absolute values of variables as \(|A|x-|B||x|=b\), where \(A \in R^{n\times n}\) is a symmetric matrix, \(B \in R^{n\times n}\) is a diagonal matrix, and \(b\in R^{n}\). A sufficient condition for unique solvability of the proposed generalized absolute value equations is also given. By utilizing an equivalence relation to the unconstrained optimization problem, we propose a modified HS conjugate gradient method to solve the transformed unconstrained optimization problem. Only under mild conditions, the global convergence of the given method is also established. Finally, the numerical results show the efficiency of the proposed method.
Notes
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The absolute value equation of the type
$$ Ax+B \vert x \vert =b $$
(1.1)
was investigated in [14, 22, 25‐28]. If \(\det (B)\neq 0\), then (1.1) can be reduced to the form
$$ Ax- \vert x \vert =b. $$
(1.2)
The absolute value Eq. (1.2) has also been intensively studied, e.g., see [9, 12, 13, 15‐17, 19, 30, 33, 34]. In this paper, we propose a new generalized absolute value equation (GAVE) problem of the form
$$ \vert A \vert x- \vert B \vert \vert x \vert =b, $$
(1.3)
where \(A=(a_{ij})\in R^{n\times n}\) is a symmetric matrix, \(B=(b_{ij})\in R^{n\times n}\) is a diagonal matrix, the absolute values of matrices are defined as \(|A|=(|a_{ij}|)\), \(|B|=(|b_{ij}|)\), \(i, j=1,2,\ldots,n\), \(b\in R^{n}\) and \(|x|=(|x_{1}|,|x_{2}|,\ldots,|x_{n}|)^{T}\). As we all know, the study of absolute value equations comes from linear complementarity problem. The general linear complementarity problem [5], which subsumes many mathematical programming problems, bimatrix games, and equilibrium programming problems, can be formulated as the absolute value equations of the forms such as (1.1)–(1.3). Mangasarian [14] showed that (1.1) is NP-hard. Prolopyev [22] stated the relations of (1.1) with linear complementarity problem and mixed integer programming problem. Rohn et al. [30] gave the sufficient conditions for unique solvability of AVE (1.2) and an iterative method to solve it. Mangasarian et al. [17] gave the existence and nonexistence results of (1.2) and proved the equivalence relations between (1.2) and the generalized linear complementarity problem. Hu et al. [9] proved that (1.2) can be equivalently reformulated as a standard linear complementarity problem without any assumption. In [16] and [15], Mangasarian proposed a concave minimization optimization method and a generalized Newton method, respectively. Zhang et al. [34] presented a generalized Newton method. Noor et al. [19] gave an iterative algorithm for solving (1.2). Yong [33] proposed a smoothing Newton algorithm to solve (1.2). Saheya et al. [31] focused on numerical comparisons based on four smoothing functions for (1.2). Bello Cruz et al. [2] showed the global Q-linear convergence of the inexact semi-smooth Newton method for solving (1.2). Ke et al. [10] studied a SOR-like iteration method for solving system of (1.2). Abdallah et al. [1] reformulated (1.2) as a sequence of concave minimization problems and gave a smoothing method to solve it. Cacceta et al. [4] proposed a smoothing Newton method with global and quadratic convergence for solving (1.2). Rohn [29] proved a theorem of alternatives for equation \(|Ax|-|B||x|=b\) and gave some sufficient conditions for solvability of the equation. The current research on the methods for solving (1.1) and (1.2) is based mostly on nonlinear optimization techniques. Little attention, however, has been paid so far to the nonlinear conjugate gradient method with smaller storage capacity and faster convergence speed for solving GAVE (1.3). In this paper, we propose a modified HS conjugate gradient method to compute the solution of GAVE (1.3).
This paper is organized as follows. In Sect. 2, we provide a sufficient condition for the solution of GAVE (1.3). In Sect. 3, a modified HS conjugate gradient method for solving GAVE (1.3) is given. Under mild conditions, we prove the global convergence theorem of the given method. In Sect. 4, we present numerical results of the relevant numerical experiments to show the effectiveness and the efficiency of the proposed method.
Advertisement
Throughout the paper, lowercase \(x, y, \ldots \) denote vectors, \(\beta ,\varepsilon ,\ldots \) denote parameters, uppercase letters \(A, B, \ldots \) denote matrices.
2 General absolute value equation and unconstrained optimization problem
We will start by showing that (1.3) is equivalent to an unconstrained optimization problem with an objective function that is continuously differentiable. Firstly, we introduce the relevant definition from [24, 25].
Definition 2.1
Given two matrices \(E, F \in R^{n \times n}\) and \(F \geq 0\), the set of matrices
$$ \varSigma =\bigl\{ \widetilde{A} | \vert E \vert -F \leq \widetilde{A}\leq \vert E \vert +F \bigr\} $$
is called an interval matrix. Σ is called regular if ∀Ã is nonsingular.
Theorem 2.1
Suppose that\(\widetilde{\varSigma }=\{\tilde{A}||A|-F \leq \widetilde{A}\leq |A|+F \}\)is regular and\(|B| \leq F\), then (1.3) has a unique solution.
Advertisement
Proof
By \(x^{+} = \max \{x,0\} = \frac{|x|+x}{2}\), \(x^{-} =\min \{x,0\} = \frac{|x|-x}{2}\), we get
$$ x^{+}=\bigl( \vert A \vert - \vert B \vert \bigr)^{-1}\bigl( \vert A \vert + \vert B \vert \bigr)x^{-}+\bigl( \vert A \vert - \vert B \vert \bigr)^{-1}b. $$
(2.1)
From \(|B| \leq F\), we know that \(|A|-|B|, |A|+|B| \in \widetilde{\varSigma }\) and \((|A|-|B|)^{-1}\) exists. Similar to Theorem 1 in [25], by [18, 23], we know that (2.1) has a unique solution. Hence (1.3) has a unique solution. We finish the proof. □
In the remaining part of this section, we transform (1.3) to an unconstraint optimization problem. Denote
$$ f(x)=\bigl\langle { \vert A \vert x,x}\bigr\rangle -\bigl\langle { \vert B \vert \vert x \vert ,x}\bigr\rangle -2 \langle {b,x}\rangle , $$
(2.2)
where A, B are defined similarly as (1.3). \(\langle {\cdot } \rangle \) denotes the inner product of vectors, namely \(\forall x, y \in R ^{n}\)
Suppose that matrix \(A \in R^{n \times n}\) is symmetric, then A is a positive definite matrix if and only if \(\langle x,Ax \rangle >0\) is set up for arbitrarily nonzero vector \(x \in R^{n}\).
In the remainder of this paper, we consider the matrices A and B such that \(|A|-|B|D\) is positive definite for any arbitrary matrix D. If A is symmetric and B, D are both diagonal matrices, then \(|A|-|B|D\) is symmetric. The diagonal matrix D is defined as \(D=\partial |x|=\operatorname{diag}(\operatorname{sign}(x))\), where \(\operatorname{diag}(x)\) denote a vector with components equal to 1, 0, −1 depending on whether the corresponding component of x is positive, zero, or negative.
Theorem 2.2
If matrix\(|A|-|B|D\)is a positive definite matrix, thenxis a solution of (1.3) ⇔xis a minimum of the function\(f(x)\), where\(f(x)\)is defined as (2.2).
Proof
Case I. For arbitrary \(\alpha \in R \) and \(\nu \in R^{n}\), by Taylor’s series, we get
The above strict inequality is impossible. Then we have
$$ \bigl\langle \vert A \vert x- \vert B \vert \vert x \vert -b,\nu \bigr\rangle =0. $$
And it follows that
$$ f(x)=f(x+\alpha \nu ). $$
If \(x^{*}\) satisfies \(|A|x^{*}-|B||x^{*}|=b\), then \(\langle |A|x^{*}-|B||x ^{*}|-b,\nu \rangle =0\) for arbitrary ν and \(f(x)\) cannot be made any smaller than \(f(x^{*})\). Then \(x^{*}\) minimizes f.
Case II. Suppose that \(x^{*}\) is the minimum point of \(f(x)\), then \(\forall \nu \in R^{n}\), \(\alpha \in R\), it follows that
$$ \bigl\langle \vert A \vert x^{*}- \vert B \vert \bigl\vert x^{*} \bigr\vert -b,\nu \bigr\rangle =0. $$
Then the above equation implies that
$$ \vert A \vert x^{*}- \vert B \vert \bigl\vert x^{*} \bigr\vert -b=0, $$
that is,
$$ \vert A \vert x^{*}- \vert B \vert \bigl\vert x^{*} \bigr\vert =b. $$
This shows that \(x^{*}\) is a solution of (1.3). Hence, this completes the proof. □
Therefore, GAVE (1.3) can be transformed into the following unconstrained optimization problem:
$$ \min_{x \in R} f(x), $$
where f is defined by formula (2.2). It is well known that nonlinear conjugate gradient methods such as Hestenes–Stiefel (HS) method [8], Fletcher–Reeves (FR) method [7], Polak–Ribiere–Polyak (PRP) method [20, 21], Dai–Yuan (DY) method [6], and other methods [3, 11, 32, 35, 36] are very efficient for large-scale smooth optimization problems due to their simplicity and low storage. Moreover, we notice that some modified HS conjugate gradient methods are more efficient to solve the unconstrained optimization problem than classical methods, see [11, 32]. In the next section, we give a modified HS conjugate gradient method for (1.3). To develop an efficient optimization method for (1.3), we also use the Armijo-type line search globalization technique [36].
3 Modified HS conjugate gradient method
In this section, we firstly propose the modified HS conjugate gradient method based on [11] with Armijo-type line search based on [36]. Then we present the global convergence of the given method under mild conditions.
Algorithm 3.1
(Modified HS Conjugate Gradient Method)
Step 0. Choose initial point \(x_{0}\in R^{n}\) and constants \(\delta _{1}, \delta _{2}, \rho \in (0,1)\), \(\varepsilon >0\). Let \(k:=0\).
Step 1. Denote \(g_{k}=\nabla f(x_{k})\). If \(\|g_{k}\| \leq \varepsilon \), stop. Otherwise, compute \(d_{k}\) by
where\(\forall x,y\in N\), Nis a neighborhood ofΩand\(L>0\)is a constant.
Proof
By \(g(x)=2(|A|x-|B||x|-b)\), we get
$$\begin{aligned} \bigl\Vert g(x)-g(y) \bigr\Vert &=2 \bigl\Vert \vert A \vert x- \vert B \vert \vert x \vert -b- \vert A \vert y+ \vert B \vert \vert y \vert +b \bigr\Vert \\ & =2 \bigl\Vert \vert A \vert x- \vert B \vert \vert x \vert - \vert A \vert y+ \vert B \vert \vert y \vert \bigr\Vert \\ & =2 \bigl\Vert \vert A \vert (x-y)- \vert B \vert \bigl( \vert x \vert - \vert y \vert \bigr) \bigr\Vert \\ & \leq 2 \bigl\Vert \vert A \vert (x-y) \bigr\Vert +2 \bigl\Vert \vert B \vert \bigl( \vert x \vert - \vert y \vert \bigr) \bigr\Vert \\ &\leq 2\bigl(\vert \!\Vert A\vert \!\Vert + \vert \!\Vert B\vert \!\Vert \bigr) \bigl( \Vert x-y \Vert \bigr)=L \Vert x-y \Vert . \end{aligned}$$
Denote \(L=2(|\!|\!|A|\!|\!|+|\!|\!|B|\!|\!|)\), we get this lemma. □
Remark 3.1
On account of the descent property of \(\{f(x_{k})\}\), the sequence \(\{x_{k}\}\) generated by Algorithm 3.1 is contained in Ω. Besides, it follows from Assumption 3.1 that there exists a constant \(\eta >0\) such that
The Armijo-type line search rule suggests that \(\rho ^{-1}\alpha _{k}\) does not satisfy line search condition (3.2) for k sufficiently enough, namely
Then we obtain \(\liminf_{k\in K, k\rightarrow \infty } \|g_{k}\|=0\) from (3.8), which also contradicts (3.6). The proof is completed. □
Remark 3.2
In Step 2 of Algorithm 3.1, we adopt the Armijo-type line search [36]. The following line searches are also well defined in Algorithm 3.1 since the search directions are descent. The Wolfe line search [6]
In this section, we present numerical results to show the efficiency of the modified HS conjugate gradient method (Algorithm 3.1). The numerical testing was carried out on a Lenovo PC with the use of Matlab. The following tables and figures list the numerical results for the given GAVE problems, where we set \(\varepsilon =10^{-6}\), \(\rho =0.6\), \(\rho _{1}=0.4\), \(\delta _{1}=0.4\), \(\delta _{2}=0.4\), \(t=2\).
The exact solution of Example 4.1 is \((1,1,1)^{T}\). The initial points in Algorithm 3.1 are taken randomly five times. The detailed numerical results are showed in Table 1 and Fig. 1. \(x^{*}\) denotes the numerical solution, k denotes the number of iterations, and Val denotes \(\||A|x_{k}-|B||x_{k}|-b\|_{\infty }\). From Table 1 and Fig. 1, we can see that Algorithm 3.1 is promising.
The exact solution of this example is \((1,1,1,1,1,1)^{T}\). Compute this example by Algorithm 3.1 with random initial points uniformly distributed in \((0,1)\). The results of the numerical experiments are showed in Table 2, where \(x^{*}\) denotes the numerical solution, k denotes the number of iterations, and Val denotes \(\||A|x_{k}-|B||x _{k}|-b\|_{\infty }\). From Table 2 and Fig. 2, we can see that Algorithm 3.1 is also efficient to get the solution of this kind of GAVE.
Consider GAVE (1.1), where \(A \in R^{n\times n}\) whose diagonal elements are 2n and other elements are 1, \(B \in R^{n\times n}\) whose diagonal elements are n and other elements are 0, and \(b=(2n-1)e\). The exact solution of this example is \((1,1,\ldots,1)^{T}\). We use random initial points uniformly distributed in \((0,1)\) to compute this example by Algorithm 3.1 with Armijo line search (3.10) and Algorithm 3.1 stops at iteration \(x_{k}\) if \(\||A|x_{k}-|B||x_{k}|-b\|<10^{-3}\). The results of the numerical experiments are showed in Table 3, where n denotes the dimension of the vector, \(x^{*}\) denotes the numerical solution, k denotes the number of iterations, and Val denotes \(\||A|x_{k}-|B||x _{k}|-b\|_{\infty }\). Figure 3 represents the number of iterations with \(n=300\). From Table 3 and Fig. 3, we can see that Algorithm 3.1 can also efficiently get the solution of this kind of GAVE.
Absolute value equation problem has been widely used in mathematical programming and other related areas of science and engineering. However, little attention has been paid to solving general absolute value equation problems by the nonlinear conjugate gradient method. In this paper, we provide a sufficient condition for the unique solution of general absolute value equation of the form as (1.3) and propose a modified HS conjugate gradient method to solve it. The global convergence of the nonlinear conjugate gradient method is proved under only one mild assumption. This method is also very easy to implement and is also very promising.
Availability of data and materials
Not applicable.
Competing interests
The authors declare that they have no competing interests.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
