The parameter-Newton iteration for the second-order cone linear complementarity problem

Peng Zhou; Teng Wang; Peng Zhou; Teng Wang

doi:10.3934/era.2022076

Electronic Research Archive

2022, Volume 30, Issue 4: 1454-1462. doi: 10.3934/era.2022076

Previous Article Next Article

Research article Special Issues

The parameter-Newton iteration for the second-order cone linear complementarity problem

Peng Zhou ^1,2,
Teng Wang ^{1
,
,}

1.
School of Mathematics and Computer Sciences, Nanchang University, China
2.
Jiangxi Institute of Economic Administrators, China

Received: 08 December 2021 Revised: 27 February 2022 Accepted: 06 March 2022 Published: 21 March 2022

In this paper, we propose the parameter-Newton (PN) method to solve the second-order linear complementarity problem (SOCLCP). The key idea of PN method is that we transfer the SOCLCP into a system of nonlinear equations by bringing in a parameter. Then we solve the system of nonlinear equations by Newton method. At last, we prove that the PN method has quadratic convergence. Compared with the bisection-Newton (BN) method, the PN method has less CPU time and higher accuracy in numerical tests.

Keywords:

second-order cone linear complementarity problem,
Newton iteration,
parameter,
higher accuracy,
quadratic convergence

Citation: Peng Zhou, Teng Wang. The parameter-Newton iteration for the second-order cone linear complementarity problem[J]. Electronic Research Archive, 2022, 30(4): 1454-1462. doi: 10.3934/era.2022076

Related Papers:

[1]	Xin Liu, Guang-Xin Huang . New error bounds for the tensor complementarity problem. Electronic Research Archive, 2022, 30(6): 2196-2204. doi: 10.3934/era.2022111
[2]	Dongmei Yu, Yifei Yuan, Yiming Zhang . A preconditioned new modulus-based matrix splitting method for solving linear complementarity problem of $ H_+ $-matrices. Electronic Research Archive, 2023, 31(1): 123-146. doi: 10.3934/era.2023007
[3]	Haiyan Song, Fei Sun . A numerical method for parabolic complementarity problem. Electronic Research Archive, 2023, 31(2): 1048-1064. doi: 10.3934/era.2023052
[4]	Shuaikang Wang, Yunzhi Jiang, Yongbin Ge . High-order compact difference methods for solving two-dimensional nonlinear wave equations. Electronic Research Archive, 2023, 31(6): 3145-3168. doi: 10.3934/era.2023159
[5]	Xuefei He, Kun Wang, Liwei Xu . Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28(4): 1503-1528. doi: 10.3934/era.2020079
[6]	Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao . A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28(4): 1439-1457. doi: 10.3934/era.2020076
[7]	Dongdong Ruan, Xiaofeng Wang . A high-order Chebyshev-type method for solving nonlinear equations: local convergence and applications. Electronic Research Archive, 2025, 33(3): 1398-1413. doi: 10.3934/era.2025065
[8]	Yijun Chen, Yaning Xie . A kernel-free boundary integral method for reaction-diffusion equations. Electronic Research Archive, 2025, 33(2): 556-581. doi: 10.3934/era.2025026
[9]	Li Yu, Xiaofeng Wang . Semi-local convergence of a sixth-order iterative method for solving nonlinear systems. Electronic Research Archive, 2025, 33(6): 3794-3810. doi: 10.3934/era.2025168
[10]	Yantong Guo, Quansheng Wu, Xiaofeng Wang . An extension of high-order Kou's method for solving nonlinear systems and its stability analysis. Electronic Research Archive, 2025, 33(3): 1566-1588. doi: 10.3934/era.2025074

Abstract

1. Introduction

The second-order cone linear complementarity problem (SOCLCP) is to find a vector ${\bf x} \in {\bf R}^{n}$ , such that

$\begin{equation} {\bf x} \in \mathcal{K}^{n}, \ {\bf z} = {\bf A}{\bf x} + {\bf q} \in \mathcal{K}^{n}, \ {\bf x}^\top {\bf z} = 0, \end{equation}$

(1.1)

where ${\bf A} \in {\bf R}^{n\times n}, \ {\bf q}\in {\bf R}^{n}$ and $\mathcal{K}^n \subset {\bf R}^{n}$ . $\mathcal{K}^{n}$ (second-order cone) is defined as following:

$\begin{equation} \mathcal{K}^{n}: = \{{\bf x}\ |\ {\bf x} = [x_{1}, {\bf \widetilde{x}}^\top]^\top\in{\bf R}^n:\ x_1\in {\bf R}_+, \ {\bf \widetilde{x}}\in {\bf R}^{n-1}\ and\ \| {\bf \widetilde{x}}\|_2 \leq x_{1}\}, \end{equation}$

(1.2)

where $\|\cdot\|_2$ denotes the Euclidean norm. Specially, $\mathcal{K}^{1}$ is equal to the set of nonnegative reals ${\bf R}_{+}$ . The SOCLCP is a kind of extension of linear complimentary problems(LCP). If you are interested in the LCP, please see^[1,2,3]. The SOCLCP also could reduce to the nonlinear complementarity problem (NCP), please see ^[4,5,6].

The SOCLCP plays a very important role in many research fields. For example: the problem of support vector machine with noisy data and missing data ^[7]; combination optimization problem ^[8]; engineering design ^[9,10]; convex network flow ^[11]; image processing ^[12,13]; array antenna design^[14].

What properties does the solution of the SOCLCP have? How to get the solution? These questions are very important. First of all, the problem about the unique of the solution should be solved. According to ^{[15,16,17,18]}, we get the answer. If the matrix ${\bf A}$ has the globally uniquely solvable (GUS) property, the solution of the SOCLCP is unique. Hence, many researches about how to get the unique solution arised in recent years. Here, we mainly introduce some methods in numerical algebra and optimization. For example: Hayashi et al. give the combined smoothing and regularization method ^[19] in 2005; Xiang et al. give the smoothing method ^[20] in 2009; Wang et al. give the interior-point method ^{[21,22,23,24,25]} in 2010; Fang et al. give the one-step Newton method ^[26] in 2011; Tang et al. give the smoothing Newton method ^[27] and Zhang et al. give the bisection-Newton method ^[28] in 2013; Hao et al. give the power penalty method ^[29] in 2015.

In this paper, we propose the parameter-Newton (PN) method to solve the SOCLCP. The key idea of PN method is that we transfer the SOCLCP into a system of nonlinear equations by bringing in a parameter (see Eq (3.1)). Then we solve the system of nonlinear equations by Newton method. The paper is organized as following. In Section 2, we introduce some notations and lemmas which will be used in the other sections. In Section 3, we give the details of PN method. In Section 4, we prove that the PN method has quadratic convergence. In Section 5, the numerical tests are presented. Finally, we state the conclusions and some future work in Section 6.

2. Preliminaries

In this section, we introduce some basic notations and lemmas which will be used in the other sections. First, we introduce the definition of Fréchet differentiability.

Definition 2.1. Let $\mathbb{V}$ and $\mathbb{W}$ be normed linear spaces, and $\mathbb{U}$ be an open subset of $\mathbb{V}$ . A function $\mathcal{F}:\mathbb{U}\rightarrow \mathbb{W}$ is called Fréchet differentiable at ${\bf x} \in \mathbb{U}$ , if there exists a bounded linear operator ${\bf A}: \mathbb{V}\rightarrow \mathbb{W}$ such that

$\begin{equation} \lim\limits_{\|{\bf h}\| \rightarrow 0}\frac{\| \mathcal{F}({\bf x} + {\bf h}) - \mathcal{F}({\bf x})-{\bf A}{\bf h}\|}{\|{\bf h}\|} = 0. \end{equation}$

(2.1)

Next, we give some lemmas about the norm of matrix.

Lemma 2.1. Let $\|\cdot\|_F$ denote the Euclidean norm of the matrix. Assume that matrices ${\bf A}, \ {\bf B}\in{\bf R}^{n\times n}$ and ${\bf A}$ is nonsingular. If $\| {\bf A}^{-1} \|_F \leq \alpha, \ \| {\bf A} - {\bf B} \|_F \leq \beta\ and\ \alpha \beta < 1$ , we yield that the matrix ${\bf B}$ is also nonsingular and $\| {\bf B}^{-1} \|_F \leq \frac{\alpha}{1-\alpha\beta}$ .

Proof. Let the matrix ${\bf C} = {\bf I}-{\bf A}^{-1}{\bf B}$ . Then we have

$\begin{equation} \nonumber \begin{aligned} \| {\bf C} \|_F & = \| {\bf I} - {\bf A}^{-1}{\bf B} \|_F \\ & = \|{\bf A}^{-1}({\bf A}-{\bf B})\|_F\\ &\leq \|{\bf A}^{-1}\|_F\cdot\|{\bf A}-{\bf B}\|_F\\ &\leq \alpha\beta < 1. \end{aligned} \end{equation}$

It is clear that the matrix ${\bf A}^{-1}{\bf B} = {\bf I} - {\bf C}$ is nonsingular which means the matrix ${\bf B}$ being also nonsingular. Furthermore, we yield the following inequality as

$\begin{equation} \nonumber \begin{aligned} \| {\bf B}^{-1} \|_F & = \|({\bf I}-{\bf C})^{-1}{\bf A}^{-1}\|_F\\ &\leq \| ({\bf I} - {\bf C})^{-1}\|_F\cdot \| {\bf A}^{-1}\|_F\\ & = \alpha\left\|\lim\limits_{n\rightarrow \infty}({\bf I}+{\bf C}+\cdots+{\bf C}^n)\right\|_F\\ &\leq\alpha\lim\limits_{n\rightarrow \infty}(1+\|{\bf C}\|_F+\cdots+\|{\bf C}\|_F^n)\\ & = \frac{\alpha}{1 - \| {\bf C}\|_F}\\ &\leq \frac{\alpha }{1-\alpha\beta}. \end{aligned} \end{equation}$

Here, we introduce some other notations which will be used in the following part of the paper. The $bd(\mathcal{K}^n)$ and the $int(\mathcal{K}^n)$ stand for the boundary and the interior of $\mathcal{K}^n$ . The matrix ${\bf J}_n = diag\{1, \ -1, \ \cdots, \ -1\} = diag\{1, -{\bf I}_{n-1}\}$ .

Lemma 2.2. ^[18] For the SOCLCP, the matrix ${\bf A}$ has the GUS property if and only if it satisfies the following assumptions:

(i) The matrix ${\bf A}{\bf J}_{n}$ has nonnegative eigenvalues and there exists $\tau > 0$ such that all nonnegative eigenvalues of ${\bf A} {\bf J}_{n}$ are equal to $\tau$ . Moreover, $rank({\bf A}{\bf J}_{n}-\tau {\bf I}_{n}) = n-1$ . There exists ${\bf w} \in int(\mathcal{K}^n)$ such that ${\bf w}$ is the eigenvector of ${\bf A} {\bf J}_{n}$ associated with $\tau$ ;

(ii) There exists ${\bf v} \in int(\mathcal{K}^n)$ such that ${\bf v}$ is the eigenvector of ${\bf A}^{\top} {\bf J}_{n}$ associated with $\tau$ ;

iii)

$\begin{equation*} {\bf a}^{\top}{\bf A} {\bf a} \geq 0, \quad \forall {\bf a} \in b d(\mathcal{K}^n); \end{equation*}$

(iv)

$\begin{equation*} {\bf a}^{\top} {\bf A}^{-1} {\bf a} \geq 0, \quad \forall {\bf a} \in bd(\mathcal{K}^n). \end{equation*}$

According to the above lemma, the positive definite (not necessarily symmetric) matrix ${\bf A}$ has the GUS property. Next, we introduce two important conclusions of the solution to the SOCLCP when the matrix ${\bf A}$ has the GUS property.

Lemma 2.3. ^[28] Suppose that ${\bf A}$ has the GUS property and $\tau > 0$ is the positive eigenvalue of ${\bf A}^\top{\bf J}_n$ with the unit eigenvector ${\bf v}\in int(\mathcal{K}^n)$ . Then the solution ${\bf x}$ to the SOCLCP is locally a continuously differentiable function of ${\bf q}$ .

Lemma 2.4. ^[28] Suppose that ${\bf A}$ has the GUS property and $\tau$ is the unique positive eigenvalue of ${\bf A}{\bf J}_n$ . Then for any $0 < \rho\neq\tau$ and for all nonzero vector ${\bf a}\in bd(\mathcal{K}^n)$ , we have

$\begin{equation} {\bf a}^\top({\bf A}-\rho{\bf J}_n)^{-1}{\bf a}\left\{\begin{array}{ll} > 0, &if\ 0 < \rho < \tau, \\ < 0, &if\ \rho > \tau.\\ \end{array} \right. \end{equation}$

(2.2)

For a given ${\bf A}$ with the GUS property and a vector ${\bf q}\in{\bf R}^n$ , our main interest in this paper is to find the unique solution for the SOCCLP. There are two special cases that can be handled very easily: ${\bf q}\in\mathcal{K}^n$ and: ${\bf q}\in-{\bf A}\mathcal{K}^n$ . The former gives the solution ${\bf x} = {\bf 0}$ whereas the latter leads to the solution ${\bf x} = -{\bf A}^{-1}{\bf q}$ . The case ${\bf q}\notin-{\bf A}\mathcal{K}^n\cup\mathcal{K}^n$ is the main topic which will be dicussed in next section.

3. The parameter-Newton method

In ^[18], Yang et al. prove that when ${\bf q} \not\in -{\bf A}\mathcal {K}^{n} \cup \mathcal {K}^{n}$ , the exact solution ${\bf x}_*$ and ${\bf z}_* = {\bf A}{\bf x}_*+{\bf q}$ are belong to the $bd(\mathcal{K}^{n})$ . Adding ${\bf x}_*^\top {\bf z}_* = 0$ , we yield that ${\bf z}_* = \lambda_* {\bf J}_n{\bf x}_*$ where $\lambda_*$ is a positive parameter. The problem (1.1) could be transformed into the following system of nonlinear equations:

$\begin{equation} \mathcal{F}({\bf x}, \lambda): = \left \{ \begin{aligned} &({\bf A}-\lambda{\bf J}_n){\bf x} + {\bf q} \\ &\frac{1}{2}{\bf x}^\top {\bf J}_n {\bf x} \end{aligned} \right. = {\bf 0} \end{equation}$

(3.1)

Then we use Newton iteration to solve (3.1). It is easy to get the iteration equation:

$\begin{equation} \left( \begin{array}{cc} {\bf A} - \lambda_{k} {\bf J}_n & -{\bf J}_n{\bf x}_{k}\\ {\bf x}_{k}^\top{\bf J}_n & 0 \end{array} \right) \left( \begin{array}{cc} {\bf x}_{k+1} \\ \lambda_{k+1} \end{array} \right) = \left( \begin{array}{cc} -\lambda_{k}{\bf J}_n {\bf x}_{k} - {\bf q}\\ \frac{1}{2}{\bf x}_{k}^\top{\bf J}_n {\bf x}_{k} \end{array} \right). \end{equation}$

(3.2)

We combine our described techniques and present the complete PN algorithm in Algorithm 1.

Algorithm 1 The parameter-Newton method (The PN method)

INPUT: The matrix

${\bf A} \in {\bf R}^{n \times n}$ with GUS property, a vector

${\bf q} \in {\bf R}^{n}$ , the initial vector

${\bf x}_{0} = (1, \ 0, \ \cdots, \ 0)^\top$ ,

$\lambda_0 = 1$ and a relative tolerance

$\epsilon$ .
OUTPUT: The solution

${\bf x}_*$ .
Case 1: If

${\bf q} \in \mathcal{K}^{n}$ then

${\bf x}_* = {\bf 0}$ ;
Case 2: If

$-{\bf A}^{-1}{\bf q} \in \mathcal{K}^{n}$ then

${\bf x}_* = -{\bf A}^{-1}{\bf q}$ ;
Case 3: If

${\bf q} \not\in -{\bf A}\mathcal {K}^{n} \cup \mathcal {K}^{n}$ then
while (

$\frac{\|{\bf x}_{k+1}-{\bf x}_k\|_2}{\|{\bf x}_k\|_2}\geq\epsilon$ )
Solve equation (3.2);
If the first element of

${\bf x}_{k+1}$ is negative, then let it equal

$\|{\bf \widetilde{x}}_{k+1}\|_2$ ;
If

$\lambda_{k+1} < 0$ , then let

$\lambda_{k+1} = -\lambda_{k+1}$ ;
end while
% We use GMRES in Case 3 to solve the Eq (3.2).

4. The convergence of the PN method

In this section, we prove that the convergence of the PN method has quadratic convergence.

Theorem 4.1. Suppose that the sequence $\{{\bf x}_{k}\}$ is produced by the PN method, then the sequence has quadratic convergence.

Proof. First of all, we need to prove the following conclusion.

When ${\bf A}$ has the GUS property, then for any ${\bf q} \notin -{\bf A}\mathcal{K}^{n} \cup \mathcal{K}^{n}$ , the coefficient matrix of Eq (3.2) is nonsingular at the solution pair $({\bf x}_*, \ \lambda_*)$ .

Suppose there exists a vector $({\bf a}^\top, \ b)^\top\in {\bf R}^{n+1}$ satisfying

$\begin{equation} \nonumber \left( \begin{array}{cc} {\bf A} - \lambda_*{\bf J}_n & -{\bf J}_n{\bf x}_{*} \\ {\bf x}_{*}^\top{\bf J}_n & 0 \\ \end{array} \right)\left( \begin{array}{c} {\bf a} \\ b \\ \end{array} \right) = {\bf 0}. \end{equation}$

In case $\lambda_{*} = \tau$ , Lemma 3 indicates $({\bf a}^\top, \ b)^\top = {\bf 0}$ . If $\lambda_{*} \neq\tau$ , then it follows that ${\bf A}-\lambda_*{\bf J}_n$ is nonsingular and thus one has

$\begin{equation} {\bf a} = b({\bf A}-\lambda_*{\bf J}_n)^{-1}({\bf J}_n{\bf x}_*), \end{equation}$

(4.1)

and

$\begin{equation} 0 = b({\bf J}_n{\bf x}_*)^\top({\bf A}-\lambda_*{\bf J}_n)^{-1}({\bf J}_n{\bf x}_*). \end{equation}$

(4.2)

This relation together with Lemma 4 implies $b = 0$ which leads to ${\bf a} = {\bf 0}$ . Therefore, the conclusion follows.

Furthermore, at the neighborhood of the solution pair $({\bf x}_*, \ \lambda_*)$ , the matrix

$\begin{equation*} \mathcal{F}'({\bf x}, \lambda): = \left( \begin{array}{cc} {\bf A} - \lambda {\bf J}_n & -{\bf J}_n{\bf x} \\ {\bf x}^\top {\bf J}_n & 0 \\ \end{array} \right) \end{equation*}$

is nonsingular.

Next, we prove the following inequality

$\begin{equation} \| \mathcal{F}'({\bf x}_{k}, \ \lambda_k) - \mathcal{F}'({\bf x}_{*}, \ \lambda_*) \| _{F} \leq \sqrt{n}(\| {\bf x}_k - {\bf x}_{*} \|^2 _{F}+(\lambda_k-\lambda_*)^2)^{\frac12}. \end{equation}$

(4.3)

We yield that

$\begin{equation} \nonumber \begin{split} &\| \mathcal{F}'({\bf x}_{k}, \ \lambda_k) - \mathcal{F}'({\bf x}_{*}, \ \lambda_*) \| _{F} \\ = &\left\|\left( \begin{array}{cc} {\bf A} - \lambda_{k} {\bf J}_n & -{\bf J}_n{\bf x}_{k} \\ {\bf x}_{k}^\top {\bf J}_n & 0 \\ \end{array} \right) - \left( \begin{array}{cc} {\bf A} - \lambda_{*} {\bf J}_n & -{\bf J}_n{\bf x}_{*} \\ {\bf x}_{*}^\top {\bf J}_n& 0 \\ \end{array} \right)\right\|_{F}\\ = & \left\| \left( \begin{array}{cc} \lambda_{k}{\bf J}_n - \lambda_{*}{\bf J}_n & {\bf J}_n{\bf x}_{k} - {\bf J}_n{\bf x}_{*} \\ -{\bf x}_{k}^\top {\bf J}_n+ {\bf x}_{*}^\top {\bf J}_n& 0 \\ \end{array} \right) \right\|_{F}. \end{split} \end{equation}$

Let

$\begin{equation} \nonumber {\bf M} = \left( \begin{array}{cc} \lambda_{k}{\bf J}_n - \lambda_{*}{\bf J}_n & {\bf J}_n{\bf x}_{k} - {\bf J}_n{\bf x}_{*} \\ -{\bf x}_{k}^\top {\bf J}_n + {\bf x}_{*}^\top {\bf J}_n& 0 \\ \end{array} \right), \end{equation}$

we get that

$\begin{equation} \nonumber \| \mathcal{F}'({\bf x}_{k}, \ \lambda_k) - \mathcal{F}'({\bf x}_{*}, \ \lambda_*) \|^2 _{F} = \| {\bf M} \|^{2}_{F} = tr({\bf M}^\top{\bf M}). \end{equation}$

By direct computing, we have that

$\begin{equation} \nonumber \begin{split} {\bf M}^\top {\bf M} & = \left( \begin{array}{cc} \lambda_{k}{\bf J}_n- \lambda_{*}{\bf J}_n & -{\bf J}_n{\bf x}_{k} + {\bf J}_n{\bf x}_{*} \\ {\bf x}_{k}^\top {\bf J}_n - {\bf x}_{*}^\top {\bf J}_n& 0 \\ \end{array} \right) \left( \begin{array}{cc} \lambda_{k}{\bf J}_n - \lambda_{*}{\bf J}_n & {\bf J}_n{\bf x}_{k} - {\bf J}_n{\bf x}_{*} \\ -{\bf x}_{k}^\top {\bf J}_n + {\bf x}_{*}^\top {\bf J}_n & 0 \\ \end{array} \right) \\ & = \left( \begin{array}{cc} (\lambda_{k}{\bf J}_n - \lambda_{*}{\bf J}_n)^{2} + (-{\bf J}_n{\bf x}_{k} + {\bf J}_n{\bf x}_{*})(-{\bf x}_{k}^\top {\bf J}_n + {\bf x}_{*}^\top {\bf J}_n) & (\lambda_{k}{\bf J}_n - \lambda_{*}{\bf J}_n)({\bf J}_n{\bf x}_{k} - {\bf J}_n{\bf x}_{*}) \\ ({\bf x}_{k}^\top {\bf J}_n - {\bf x}_{*}^\top {\bf J}_n)(\lambda_{k}{\bf J}_n - \lambda_{*}{\bf J}_n) & ({\bf x}_{k}^\top {\bf J}_n - {\bf x}_{*}^\top {\bf J}_n)({\bf J}_n{\bf x}_{k} - {\bf J}_n{\bf x}_{*}) \\ \end{array} \right) \\ & = \left( \begin{array}{cc} (\lambda_{k} - \lambda_{*})^{2}{\bf I}_{n} + (-{\bf x}_{k} + {\bf x}_{*})(-{\bf x}_{k}^\top + {\bf x}_{*}^\top ) & (\lambda_{k} - \lambda_{*})({\bf x}_{k} - {\bf x}_{*}) \\ (\lambda_{k} - \lambda_{*})({\bf x}_{k}^\top - {\bf x}_{*}^\top ) & ({\bf x}_{k}^\top - {\bf x}_{*}^\top )({\bf x}_{k} - {\bf x}_{*}) \\ \end{array} \right). \\ \end{split} \end{equation}$

Therefore, we yield

$\begin{equation} \begin{split} tr({\bf M}^\top {\bf M}) & = tr[(\lambda_{k} - \lambda_{*})^{2}{\bf I}_{n} + (-{\bf x}_{k} + {\bf x}_{*})(-{\bf x}_{k}^\top + {\bf x}_{*}^\top )] + ({\bf x}_{k}^\top - {\bf x}_{*}^\top )({\bf x}_{k} - {\bf x}_{*}) \\ & = n(\lambda_{k} - \lambda_{*})^{2} + tr[(-{\bf x}_{k} + {\bf x}_{*})(-{\bf x}_{k}^\top + {\bf x}_{*}^\top )] + ({\bf x}_{k}^\top - {\bf x}_{*}^\top )({\bf x}_{k} - {\bf x}_{*}) \\ & = n(\lambda_{k} - \lambda_{*})^{2} + 2({\bf x}_{k}^\top - {\bf x}_{*}^\top )({\bf x}_{k} - {\bf x}_{*}). \end{split} \end{equation}$

(4.4)

Similarly,

$\begin{equation} \| {\bf x}_k - {\bf x}_{*} \|^2 _{F}+(\lambda_k-\lambda_*)^2 = ({\bf x}_{k} - {\bf x}_{*})^\top({\bf x}_{k} - {\bf x}_{*}) + (\lambda_{k}-\lambda_{*})^{2}. \end{equation}$

(4.5)

Getting (4.4) and (4.5) together, we prove the inequality (4.3).

Now, the proof of the theorem is finished.

5. Numerical results

In this section, we will present the numerical experiments of the PN method. It is known that there exist various methods for solving the SOCLCP. In order to evaluate the numerical performance and demonstrate clearly the efficiency of the PN method for solving the SOCLCP, we will also present the numerical results from the bisection-Newton (BN) method ^[28]. All of our tests are carried out in MATLAB (R2015b) on a PC with Intel(R) Core(TM) m3-7Y30 CPU @ 1.00GHz and 4GB memory.

Example 5.1. The matrix ${\bf N} \in {\bf R}^{n \times n}$ is a large sparse random matrix. We set that the dimension $n$ equals 1000, 3000, 5000. The density of matrix ${\bf N}$ is 0.5, 1 and 5%. The matrix ${\bf A} = {\bf N}^\top {\bf N}$ has the GUS property. The vector ${\bf q}$ is also a random vector.

We make the initial vector ${\bf x}_0 = (1, \ 0, \ \cdots, \ 0)^\top$ and parameter $\lambda_0 = 1$ . We set the relative tolerance $\epsilon = 10^{-6}$ . The results of the numerical test are prensented in the Table 1. In this table, we summarize the average numbers of iterations (labelled as Iter) for every method. The corresponding CPU times (labelled as CPU, the unit as second) of each method are also summarized. To check the accuracy (labelled as Err) of the computed solution, we define

$\begin{equation} ac = |{\bf x}^{\top}{\bf z}| + |{\bf x}_1 - \|\widetilde{{\bf x}}\|_{2}| + | {\bf z_1} - \|\widetilde{{\bf z}}\|_{2}|. \end{equation}$

(5.1)

Table 1. The results of PN method and BN method.

n	density	Iter		CPU(s)		Err
n	density	PN	BN	PN	BN	PN	BN
1000	0.5%	19	27	0.26	0.17	8.27e-10	3.11e-06
	1%	19	27	0.78	0.10	8.71e-10	7.81e-06
	5%	19	27	0.50	0.06	9.06e-13	7.16e-06
3000	0.5%	19	31	2.23	6.18	1.43e-08	2.14e-06
	1%	20	31	2.04	5.20	7.37e-08	6.37e-06
	5%	19	31	1.85	3.20	5.87e-09	2.60e-06
5000	0.5%	25	33	10.26	21.32	8.94e-08	1.56e-06
	1%	22	32	10.78	25.37	1.79e-08	8.40e-07
	5%	22	33	10.50	21.09	1.21e-07	6.92e-06

| Show Table

DownLoad: CSV

6. Conclusions and future work

In this paper, we propose the parameter-Newton method for solving the second-order cone linear complementarity problem. We prove that our algorithm has quadratic convergence at least. Numerical results also show that the PN method is more efficient when ${\bf A}$ is a large, sparse and symmetric positive definite matrix. Since the Eq (3.2) being the saddle point problem, we will use some other numerical methods to sovle it in future.

Conflict of interest

The authors declare there is no conflicts of interest.

References

[1]	A. Alfred, Variational inequalities over the cone of semidefinite positive symmetric matrices and over the Lorentz cone, Optim. Method Softw., 18 (2003), 359–376. https://doi.org/10.1080/1055678031000122586 doi: 10.1080/1055678031000122586
[2]	M. Kojima, S. Shindoh, S. Hara, Interior-point methods for the monotone semidfinite linear complementarity problem in symmetric matrices, SIAM J. Optim., 7 (1997), 86–125. https://doi.org/10.1137/S1052623494269035 doi: 10.1137/S1052623494269035
[3]	A. Yoshise, Interior point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones, SIAM J. Optim., 17 (2006), 1129–1153. https://doi.org/10.1137/04061427X doi: 10.1137/04061427X
[4]	S. Hayashi, N. Yamashita, M. Fukushima, Robust Nash equilibria and second-order cone complementarity problems, J. Nonlinear Convex Anal., 6 (2005), 283–296.
[5]	X. D. Chen, D. Sun, J. Sun, Complementarity functions and numerical experiments on some smoothing Newton methods for second-order-cone complementarity problems, Comput. Optim. Appl., 25 (2003), 39–56. https://doi.org/10.1023/A:1022996819381 doi: 10.1023/A:1022996819381
[6]	S. L. Miguel, V. Lieven, B. Stephen, L. Herve, Applications of second-order cone programming, Linear Algebra Appl., 284 (1998), 193–228. https://doi.org/10.1016/S0024-3795(98)10032-0 doi: 10.1016/S0024-3795(98)10032-0
[7]	P. K. Shivaswamy, C. Bhattacharyya, A. J. Smola, Second order cone programming approaches for handling missing and uncertain data, J. Mach. Learn. Res., 7 (2006), 1283–1314.
[8]	S. Kim, M. Kojima, M. Yamashita, Second order cone programming relaxation of a positive semidefinite constraint, Optim. Method Software, 18 (2003), 535–541. https://doi.org/10.1080/1055678031000148696 doi: 10.1080/1055678031000148696
[9]	T. Sasakawa, T. Tsuchiya, Optimal magnetic shield design with second-order cone programming, SIAM J. Sci. Comput., 24 (2003), 1930–1950. https://doi.org/10.1137/S1064827500380350 doi: 10.1137/S1064827500380350
[10]	S. Yan, Y. L. Ma, Optimal design and verification of temporal and spatial filters using second-order cone programming approach, Sci. China Ser. F Inf. Sci., 49 (2006), 235–253. https://doi.org/10.1007/s11432-006-0235-3 doi: 10.1007/s11432-006-0235-3
[11]	Y. Kanno, M. Ohsaki, Contact analysis of cable networks by using second-order cone programming, SIAM J. Sci. Comput., 27 (2006), 2032–2052. https://doi.org/10.1137/S1064827503431946 doi: 10.1137/S1064827503431946
[12]	X. Peng, I. King, Robust BMPM training based on second-order cone programming and its application in medical diagnosis, Neural Netw., 21 (2008), 450–457. https://doi.org/10.1016/j.neunet.2007.12.051 doi: 10.1016/j.neunet.2007.12.051
[13]	D. Goldfarb, W. T. Yin, Second-order cone programming methods for total variation-based image restoration, SIAM J. Sci. Comput., 27 (2005), 622–645. https://doi.org/10.1137/040608982 doi: 10.1137/040608982
[14]	S. Yan, Y. L. Ma, Robust supergain beamforming for circular array via second order cone programm, Appl. Acoust., 66 (2005), 1018–1032. https://doi.org/10.1016/j.apacoust.2005.01.003 doi: 10.1016/j.apacoust.2005.01.003
[15]	M. Fukushima, Z. Q. Luo, P. Tseng, Smoothing functions for second-order cone complementarity problems, SIAM J. Optim., 12 (2001), 436–460. https://doi.org/10.1137/S1052623400380365 doi: 10.1137/S1052623400380365
[16]	M. S. Gowda, Y. Song, On semidfinite linear complementarity problems, Math. Program., 88 (2000), 575–587. https://doi.org/10.1007/PL00011387 doi: 10.1007/PL00011387
[17]	M. S. Gowda, R. Sznajder, Automorphism invariance of P-matrix and GUS properties of linear transformations on Euclidean Jordan algebras, Math. Oper. Res., 31 (2006), 109–123. https://doi.org/10.1287/moor.1050.0182 doi: 10.1287/moor.1050.0182
[18]	W. H. Yang, Y. Yuan, The GUS-property of second-order cone linear complementarity problems, Math. Comput., 141 (2013), 295–317. https://doi.org/10.1007/s10107-012-0523-1 doi: 10.1007/s10107-012-0523-1
[19]	S. Hayashi, N. Yamashita, M. Fukushima, A combined smoothing and regularization method for monotone second-order cone complementarity problems, SIAM J. Optim., 15 (2005), 593–615. https://doi.org/10.1137/S1052623403421516 doi: 10.1137/S1052623403421516
[20]	S. Z. Xiang, Y. L. San, H. L. Zhen, A smoothing method for second order cone complementarity problem, J. Comput. Appl. Math., 228 (2009), 83–91. https://doi.org/10.1016/j.cam.2008.08.040 doi: 10.1016/j.cam.2008.08.040
[21]	B. Kheirfam, N. M. Amiri, A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, Optim. Lett., 8 (2014), 1017–1029. https://doi.org/10.1007/s11590-013-0618-5 doi: 10.1007/s11590-013-0618-5
[22]	G. Q. Wang, D. T. Zhu, A class of polynomial interior-point algorithms for the Cartesian $P_{}(\kappa)$ second-order cone linear complementarity problem, Nonlinear Anal., Theory, Methods Appl.*, 73 (2010), 3705–3722. https://doi.org/10.1007/s10957-011-9938-8 doi: 10.1007/s10957-011-9938-8
[23]	G. Q. Wang, Y. Q. Bai, A class of polynomial interior-point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones, J. Optim. Theory Appl., 152 (2012), 739–772. https://doi.org/10.1007/s10957-011-9938-8 doi: 10.1007/s10957-011-9938-8
[24]	G. Lesaja, G. Q. Wang, D. T. Zhu, Interior-point methods for Cartesian $P_{}(\kappa)$ -linear complementarity problems over symmetric cones based on the eligible kernel functions, Optim. Methods Software*, 27 (2012), 827–843. https://doi.org/10.1080/10556788.2012.670858 doi: 10.1080/10556788.2012.670858
[25]	G. Q. Wang, G. Lesaja, Full Nesterov-Todd step feasible interior-point method for the Cartesian $P_{}(\kappa)$ -SCLCP, Optim. Methods Software*, 28 (2013), 600–618. https://doi.org/10.1080/10556788.2013.781600 doi: 10.1080/10556788.2013.781600
[26]	L. Fang, C. Y. Han, A new one-step smoothing newton method for the second-order cone complementarity problem, Math. Meth. Appl. Sci., 34 (2011), 347–359. https://doi.org/10.1002/mma.1366 doi: 10.1002/mma.1366
[27]	J. Y. Tang, G. P. He, D. Li, F. Liang, J. C. Zhou, A smoothing Newton method for the second-order cone complementarity problem, J. Optim. Theory Appl., 58 (2013), 223–247. https://doi.org/10.1007/s10492-013-0011-9 doi: 10.1007/s10492-013-0011-9
[28]	L. H Zhang, W. H. Yang, An efficient algorithm for second-order cone linear complementarity problems, Math. Comput., 83 (2013), 1701–1726. https://doi.org/10.1090/S0025-5718-2013-02795-0 doi: 10.1090/S0025-5718-2013-02795-0
[29]	Z. J. Hao, Z. P. Wan, X. N. Chi, A power penalty method for second-order cone linear complementarity problems, Oper. Res. Lett., 43 (2015), 137–142. https://doi.org/10.1016/j.orl.2014.12.012 doi: 10.1016/j.orl.2014.12.012

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Electronic Research Archive

1.1 1.7

Metrics

Article views(2039) PDF downloads(63) Cited by(0)

Preview PDF

Download XML

Export Citation

Article outline

Show full outline

Figures and Tables

Tables(1)

Electronic Research Archive

The parameter-Newton iteration for the second-order cone linear complementarity problem

Related Papers:

Abstract

1. Introduction

2. Preliminaries

3. The parameter-Newton method

4. The convergence of the PN method

5. Numerical results

6. Conclusions and future work

Conflict of interest

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Catalog

Electronic Research Archive

The parameter-Newton iteration for the second-order cone linear complementarity problem

Related Papers:

Abstract

1. Introduction

2. Preliminaries

3. The parameter-Newton method

4. The convergence of the PN method

5. Numerical results

6. Conclusions and future work

Conflict of interest

References

Reader Comments

通讯作者: 陈斌, bchen63@163.com

Metrics

Figures and Tables

Other Articles By Authors

Related pages

Tools

Export File

Citation

Format

Content

Catalog