New convergence analysis of a class of smoothing Newton-type methods for second-order cone complementarity problem

1.   Introduction

We consider the second-order cone complementarity problem (SOCCP), which is to find $(x, y)\in \mathbb{R}^n\times \mathbb{R}^n$ such that

where $F:\mathbb{R}^n\rightarrow \mathbb{R}^n$ is a continuously differentiable function, $\mathcal{K}\subset\mathbb{R}^n$ is the Cartesian product of second-order cones (SOCs), that is, $\mathcal{K} = \mathcal{K}^{n_1}\times\cdots\times \mathcal{K}^{n_r}$ with $r, n_1, ..., n_r\geq1$ and $n = \sum_{i = 1}^{r}n_i$, where $\mathcal{K}^{n_i}$ are the $n_i$-dimensional second-order cone defined by

Here and below, $\|\cdot\|$ denotes the 2-norm. Since $\mathcal{K}^{1}$ is the set of nonnegative real values $\mathbb{R}_+$ (the nonnegative orthant in $\mathbb{R}$), the SOCCP includes the well-known nonlinear complementarity problem as a special case, corresponding to $n_i = 1$ for all $i = 1, 2, ..., r.$

In the last few years, the SOCCP has attracted a lot of attention due to its wide applicability in many fields (e.g., ^{[2,3,4,14,16]}). A number of numerical methods have been proposed to solve the SOCCP among which the smoothing Newton-type method is one of the most effective methods (e.g., ^{[1,5,7,9,11,12,15,18,20,21,22,23]}). The main idea of these smoothing Newton-type methods is to use a smoothing function to reformulate the concerned SOCCP as a system of smooth nonlinear equations $H(z) = 0$ and then solve it by using Newton's method. In these smoothing Newton-type methods, it has been proved that any accumulation point $z^*$ of the generated iteration sequence $\{z^k\}$ satisfies $H(z^*) = 0$. However, many papers do not analyze whether such an accumulation point exists (e.g., ^[5,15]). To ensure that such an accumulation point exists, existing smoothing Newton-type methods usually require that the solution set of the SOCCP is nonempty and bounded (e.g., ^{[7,9,11,12,18,20,21,22,23]}).

Recently, Huang, Hu and Han ^[10] presented a nonmonotone smoothing algorithm for solving the symmetric cone complementarity problem for which global convergence is established by just requiring that the solution set of the problem is nonempty. Motivated by their work, in this paper, we give a new convergence analysis of a class of smoothing Newton-type methods for the SOCCP. Specifically, we introduce a special regularized Chen-Harker-Kanzow-Smale (CHKS) smoothing function that is perturbed by $\mu^t$ where $\mu$ is the smoothing parameter and $t\in(0, 1/2]$ is a constant. By using this smoothing function, we reformulate the SOCCP as a system of smooth nonlinear equations $H_t(z) = 0$ (see, Section 3 below) and propose a class of smoothing Newton-type methods to solve it. We prove that, when the solution set of the SOCCP is only nonempty, the proposed method has the following convergence properties.

(ⅰ) It generates a bounded iteration sequence;

(ⅱ) The value of the merit function converges to zero;

(ⅲ) Any accumulation point of the generated iteration sequence is a solution of the SOCCP;

(ⅳ) It has a local quadratic convergence rate under suitable assumptions.

The paper is organized as follows. In Section 2, we introduce Euclidean Jordan algebras associated with the SOC $\mathcal{K}^n$. In Section 3, based on a special regularized CHKS smoothing function, we reformulate the SOCCP as a family of parameterized smooth nonlinear equations. In Section 4, we give a class of smoothing Newton-type methods for solving the SOCCP. In Section 5, we investigate its global and local convergence properties respectively. The numerical results are reported in Section 6. Some conclusions are given in Section 7.

Throughout the paper, $\mathbb{R}^n$ denotes the space of $n$-dimensional real column vectors. $\mathbb{R}_+^n$ ($\mathbb{R} _{++}^n$) denotes the nonnegative (positive) orthant in $\mathbb{R} ^n$. For convenience, we write $(u_1^T, ..., u_m^T)^T$ as $(u_1, ..., u_m)$ for any vectors $u_i \in \mathbb{R} ^{n_i}$. $I_n$ represents the $n\times n$ dimension identity matrix; $\langle\cdot, \cdot\rangle$ denotes the Euclidean inner product. ${\rm{int}}\mathcal{K}$ denotes the interior of $\mathcal{K}$. For any $x, y\in \mathbb{R}^n$, we write $x\succeq_{\mathcal{K}} y$ ($x\succ_{\mathcal{K}}y$) if $x-y\in\mathcal{K}$ ($x-y\in {\rm{int}}\mathcal{K}$). For any $\alpha, \beta > 0,$ $\alpha = O(\beta)$ ($\alpha = o(\beta))$ means that $\alpha/\beta$ is uniformly bounded (tends to zero) as $\beta\rightarrow0.$

2.   Euclidean Jordan algebras

For any vectors $x = (x_{1}, \bar{x})\in \mathbb{R} \times\mathbb{R} ^{n-1}$ and $y = (y_{1}, \bar{y})\in \mathbb{R} \times\mathbb{R} ^{n-1}$, their Jordan product associated with the SOC $\mathcal{K}^n$ is defined by

The identity element under this product is ${{\textbf{e}}}: = (1, 0, ..., 0)^T\in \mathbb{R}^{n}.$ A vector $x \in\mathbb{R} ^{n}$ is said to be invertible if there exists a unique $y\in\mathbb{R} ^{n}$ such that $x\circ y = {\bf{e}}$. We shall call this $y$ the inverse of $x$ and denote it by $x^{-1}$. Moreover, if $x\in \mathcal{K}^n$, then there exists a unique vector in $\mathcal{K}^n$, which we denote by $\sqrt{x}$, such that $\sqrt{x}\circ\sqrt{x} = x.$

For any $x = (x_1, \bar{x})\in \mathbb{R}\times\mathbb{R}^{n-1}$, its spectral decomposition with respect to the SOC $\mathcal{K}^n$ is

where $\lambda_1(x), \lambda_2(x)$ and $c_1, c_2$ are the spectral values and associated spectral vectors of $x$, respectively, that are given by

with any $\omega\in \mathbb{R}^{n-1}$ such that $\|\omega\| = 1.$

For any $x = (x_1, \bar{x})\in \mathbb{R}\times\mathbb{R}^{n-1}$ with spectral values $\lambda_1(x), \lambda_2(x)$ and spectral vectors $c_1, c_2$, the following results hold:

(1) $x^2: = \lambda_1(x)^2c_1+\lambda_2(x)^2c_2\in \mathcal{K}^n$ and $x^2 = x\circ x.$

(2) If $x\in \mathcal{K}^n$, then $\lambda_2(x)\geq \lambda_1(x)\geq0$ and $\sqrt{x} = \sqrt{\lambda_1(x)}c_1+\sqrt{\lambda_2(x)}c_2.$

(3) If $x\in {\rm{int}}\mathcal{K}^n$, then $\lambda_2(x)\geq \lambda_1(x) > 0$ and $x^{-1} = \lambda_1(x)^{-1}c_1+\lambda_2(x)^{-1}c_2.$

Given an element $x = (x_{1}, \bar{x})\in \mathbb{R} \times\mathbb{R} ^{n-1}$, we define the symmetric matrix

It is easy to verify that $L_xy = x\circ y, \; \forall y\in \mathbb{R}^n.$ Moreover, if $x\in {\rm{int}}\mathcal{K}^n$, then $L_x$ is invertible with

where ${{det}{(}x{)}}: = x_1^2-\|\bar{x}\|^2$ denotes the determinant of $x$.

We can also define the trace of $x = (x_1, \bar{x})\in\mathbb{R}\times \mathbb{R}^{n-1}$ by $\textbf{Tr}(x): = \lambda_{1}(x)+\lambda_{2}(x) = 2x_1.$ Then, for any $x, y\in \mathbb{R}^n$, it holds that ${\textbf{Tr}}(x\circ y) = 2x^Ty\; \; \mbox{and}\; \; {\textbf{Tr}}(\textbf{e}) = 2.$

3.   Reformulation of the SOCCP

In the following analysis, we assume that $\mathcal{K} = \mathcal{K}^n$. This does not result in any loss of generality because our analysis can be easily extended to the general case. Smoothing Newton-type methods are typically designed based on a smoothing function. Up to now, many smoothing functions for the SOCCP have been proposed. Among them, the CHKS smoothing function

is one of the most prominent smoothing functions which satisfies (see, [8,Proposition 4.1])

Chi and Liu ^[6] proposed a regularized CHKS smoothing function which is denoted as

Based on $\phi$, Chi and Liu ^[6] proposed a non-interior continuation method for solving the SOC optimization problem.

In this paper, we introduce a special regularized CHKS smoothing function which is defined by

where $t\in (0, 1/2]$ is a constant. As it will be shown later (see, Theorem 5.1 below), the parameter $t\in (0, 1/2]$ plays a key role in proving the boundedness of the generated iteration sequence.

The following theorem gives the continuously differentiable property of the function $\phi_t$, which has a proof that is similar to Theorem 2.4 in ^[6].

Theorem 3.1. Let $\phi_t(\mu, x, y)$ be defined by $\textrm{(3.1)}$. Denote $w: = \sqrt{(1-\mu^t)^2(x-y)^2+4\mu{\bf{e}}}.$ Then $\phi_t(\mu, x, y)$ is continuously differentiable at any $(\mu, x, y)\in\mathbb{R} _{++}\times \mathbb{R} ^n\times \mathbb{R} ^n$ with

Moreover, $\lim\limits_{ \mu\rightarrow 0} \phi_t(\mu, x, y) = \phi_t(0, x, y)$ and

To reformulate the SOCCP as a family of parameterized smooth equations, we introduce a class of single variable functions as follows.

Assumption 3.1. Assume that $h: \mathbb{R}\rightarrow \mathbb{R}$ is a function that satisfiesthe following conditions:

(a) $h$ is continuously differentiable with $h'(\mu) > 0$ forany $\mu > 0;$

(b) $h(\mu) = 0$ implies that $\mu = 0;$

(c) $-\frac{h(\mu)}{h'(\mu)}\in [-\mu, 0)$ for any $\mu > 0;$

(d) $h(\mu)\geq\mu$ for any $\mu\geq0;$

(e) there exist $\eta_1\geq0$ and $\eta_2\geq0$ such that $h'(\mu)\leq\eta_1 h(\mu)+\eta_2$ for any $\mu\geq0.$

Regarding Assumption 3.1, we have the following remarks.

Remark 3.1. (ⅰ) The conditions (a)–(c) were introduced by Jiang ^[13].

(ⅱ) There are many functions satisfying Assumption 3.1, for example, $h(\mu) = \mu$, $h(\mu) = e^{\mu}-1$, $h(\mu) = e^{\mu}+\mu-1$ and so on.

(ⅲ) If $h_1$ and $h_2$ satisfy Assumption 3.1, then $\alpha h_1+\beta h_2$ satisfies Assumption 3.1 for any $\alpha, \beta\geq0$ with $\alpha+\beta = 1.$

In the rest of this paper, we let $z: = (\mu, x, y)\in\mathbb{R}\times\mathbb{R}^n\times\mathbb{R}^n$. We define the function $H_t:\mathbb{R}\times \mathbb{R}^n\times\mathbb{R}^n\rightarrow \mathbb{R}\times \mathbb{R}^n\times\mathbb{R}^n$ as

where $\phi_t$ is given in (3.1). Then, by Theorem 3.1 and Assumption 3.1 (b), we can immediately get the following theorem.

Theorem 3.2. $\textrm{(i)}$ $(x, y)$ is the solution of the $\textrm{SOCCP}$ if $H_t(z) = 0.$

$\textrm{(ii)}$ $H_t(z)$ is continuously differentiable at any $z = (\mu, x, y)\in\mathbb{R}_{++}\times \mathbb{R}^n\times\mathbb{R}^n$ with its Jacobian

where $(\phi_t(z))'_\mu$, $(\phi_t(z))'_x$ and $(\phi_t(z))'_y$ are given in Theorem $\textrm{3.1}$.

In the case of smoothing Newton-type methods, it is essential that the Jacobian matrix $H'_t(z)$ is invertible since the direction of descent should be well defined and unique to solve $H_t(z) = 0.$ To establish the nonsingularity of $H'_t(z)$, we need the monotonicity of $F$ which has been extensively used in previous studies (e.g., ^{[5,7,9,11,12,15,20,21,22]}). The function $F$ is said to be monotone if it satisfies

Under this monotonicity assumption, similarly to the proof of Theorem 5.1 in ^[12], we can establish the nonsingularity of $H'_t(z)$ as follows.

Theorem 3.3. If $F$ is monotone, then $H'_t(z)$ is nonsingular for any $z\in\mathbb{R}_{++}\times \mathbb{R}^{n}\times \mathbb{R}^{n}$.

4.   Class of smoothing Newton-type methods

Let ${H}_t(z)$ be defined by (3.2). We denote the merit function $f_t:\mathbb{R}^{1+2n}\rightarrow \mathbb{R}_+$ by

We now give our methods for solving the SOCCP.

Algorithm 4.1. (A class of smoothing Newton-type methods)

Step 0: Choose constants $\delta, \sigma\in(0, 1)$ and $\mu_0 > 0$. Choose a function $h(\mu)$ satisfying the conditions (a)–(e) in Assumption 3.1. Choose $\eta_1\geq0$ and $\eta_2\geq0$ such that $h'(\mu)\leq\eta_1 h(\mu)+\eta_2$ for any $\mu\geq0$. Choose $\gamma\in (0, 1)$ such that $\gamma\leq\mu_0$ and $\gamma(\eta_1+\eta_2) < 1$. Choose $(x^0, y^0)\in\mathbb{R}^n \times\mathbb{R}^n$ and let $z^0: = (\mu_0, x^0, y^0)$. Let $\bar{z}: = (1, 0, ..., 0)^T \in \mathbb{R}^{1+2n}$. Set $k: = 0.$

Step 1: If $\| H_t(z^k)\| = 0$, then stop. Otherwise, compute

Step 2: Compute the search direction $\Delta z^k: = (\Delta \mu_k, \Delta x^k, \Delta y^k)\in \mathbb{R}^{1+2n}$ by solving the following system

Step 3: Find a step-size $\alpha_k : = \delta^{l_k}$, where $l_k$ is the smallest nonnegative integer $l$ satisfying

Step 4: Set $z^{k+1}:=z^k+\alpha_k\Delta z^k.$ Set $k: = k+1$ and go to Step 1.

Theorem 4.1. If $F$ is monotone, then Algorithm $\textrm{4.1}$ is well-defined andcan generate an infinitesequence $\{z^k = (\mu_k, x^k, y^k)\}$ with $\mu_k > 0$ for any $k\geq0$.

Proof. Suppose that $z^k = (\mu_k, x^k, y^k)\in \mathbb{R}_{++} \times \mathbb{R}^{2n}$ for some $k$. Then, it follows from Theorem 3.3 that $H'_t(z^k)$ is nonsingular. Hence, the system (4.3) is solvable. Moreover, by (4.3), we have that

where the first inequality follows from Assumption 3.1(e). By the definition of $\zeta_k$ in (4.2), also notice that $\min\{1, a^2\}\leq a$ for any $a > 0$; additionally, we have that $\zeta_k\leq\gamma$ and $\zeta_k\leq\gamma\| H_t(z^k)\|$. This together with $h(\mu_k)\leq\| H_t(z^k)\|$ gives

By Assumption 3.1(d), we have that $f_t(z^k)\geq h(\mu_k)^2\geq\mu_k^2 > 0$. So, by (4.5) and (4.6), it holds

This implies that $\Delta z^k$ is the direction of descent of $f_t(z)$ at $z^k$. Next we show that there exists at least one nonnegative integer $l$ that satisfies (4.4). On the contrary, we suppose that for any nonnegative integer $l$,

i.e.,

Since $\mu_k > 0$, $f_t(z)$ is continuously differentiable at $z^k$. So, by letting $l\rightarrow \infty$ on both sides of (4.8), we have that $f'_t(z^k) \Delta z^k\geq0$. This contradicts (4.7). Hence, we can find the step size $\alpha_k\in(0, 1]$ in Step 3 and get the $(k+1)$th iteration point $z^{k+1} = z^k+\alpha_k \Delta z^k.$ Moreover, by the first equation in (4.3), we have that $\Delta\mu_k = -\frac{h(\mu_k)}{h'(\mu_k)}+\zeta_k$ which together with Assumption 3.1(c) gives

Thus, we can conclude that if $z^k\in\mathbb{R}_{++}\times \mathbb{R}^{2n}$ for some $k$, then $z^{k+1}$ can be generated by Algorithm 4.1 with $z^{k+1}\in \mathbb{R}_{++}\times \mathbb{R}^{2n}$. Since $z^0 = (\mu_0, x^0, y^0)\in \mathbb{R}_{++} \times \mathbb{R}^{2n}$, by mathematical induction, we prove the theorem.

5.   Convergence analysis

In this section, we establish the global and local quadratic convergence of Algorithm 4.1 under the assumption that the solution set of the SOCCP is nonempty, without requiring its boundedness.

Lemma 5.1. Let $\phi_t$ be defined by $\textrm{(3.1)}$. For any $(\mu, x, y, c)\in\mathbb{R}_{++} \times\mathbb{R}^n\times \mathbb{R}^n\times \mathbb{R}^n$, one has

Proof. By Lemma 4.1 in ^[10], for any $(\mu, a, b, c)\in\mathbb{R}_{++} \times \mathbb{R}^n\times \mathbb{R}^n\times \mathbb{R}^n$, we have that

Since $\phi_t$ can be rewritten as

we obtain the desired result.

Lemma 5.2. Suppose that $F$ is monotone and $\{z^k = (\mu_k, x^k, y^k)\}$ is theiteration sequence generated by Algorithm $\textrm{4.1}$. Then for all $k\ge0,$

Proof. By Step 0, we have that $\mu_0\geq\gamma\geq\gamma\min\{1, f_t(z^0)\}$. Suppose that $\mu_k\geq\gamma\min\{1, f_t(z^k)\}$ for some $k$. Then, from (4.2) and (4.9) it follows that

where the last inequality holds because $\{ f_t(z^k)\}$ is monotonically decreasing as given by Step 3. So, by mathematical induction, we prove the lemma.

Theorem 5.1. Suppose that $F$ is monotone and the solution set of the $\textrm{SOCCP}$ is nonempty. Then theiteration sequence $\{z^k = (\mu_k, x^k, y^k)\}$ generated by Algorithm $\textrm{4.1}$ is bounded.

Proof. By Theorem 4.1, we have that $z^k = (\mu_k, x^k, y^k)\in \mathbb{R}_{++} \times \mathbb{R}^{2n}$ for all $k\geq0.$ Moreover, since the sequence $\{ f_t(z^k)\}$ is monotonically decreasing, we have that $f_t(z^k)\leq f_t(z^0)$ for any $k\geq0$. Now we assume $\|z^k\|\rightarrow \infty$ as $k\rightarrow \infty$ and we will thus derive a contradiction. Since

where the second inequality holds by Assumption 3.1 (d), we have that $\|(x^k, y^k)\|\rightarrow \infty$ as $k\rightarrow \infty$. For any $t\in(0, 1/2],$ we define

Then, from (4.1), we have the following for any $k\geq0$

For any $k\geq0$, by (5.1), if $f_t(z^k)\geq1$, then $\mu_k\geq\gamma$; therefore,

And if $f_t(z^k) < 1$, then $\mu_k\geq\gamma f_t(z^k)$ which gives

By (5.4), (5.5) and (5.6), the sequence $\{(a^k, b^k)\}$ is uniformly bounded. Since the solution set of the SOCCP is nonempty, there exists a solution of the SOCCP, denoted by $(x^*, y^*)\in \mathbb{R}^n\times\mathbb{R}^n$, such that

Now we construct another sequence $\{(\hat{x}^k, \hat{y}^k)\}$ given

By (5.3), we have that $\phi_t(\mu_k, x^k, y^k) = 2\mu_k^tb^k$. Thus, from Lemma 5.1 it follows that

By (5.7), (5.8) and (5.9), and also using the fact that $\langle p, q\rangle\geq0$ holds for any $p\succeq_{\mathcal{K}}0$ and $q\succeq_{\mathcal{K}}0$ (see, [10,Lemma 2.3]), we have that

which together with (5.3), (5.7) and the monotonicity of $F$ gives

where

Furthermore, by (5.2) and (5.10), we have that

which together with $\|(x^k, y^k)\|\rightarrow \infty$ as $k\rightarrow \infty$ gives

Since $\{(a^k, b^k)\}$ is bounded and $0 < \mu_k\leq \sqrt{f_t(z^0)}$ for any $k\geq0$, the sequences $\{p(\mu_k^t, a^k, b^k)\}$ and $\{q(\mu_k^t, a^k, b^k)\}$ are all bounded. Also notice that the sequences $\Big\{\frac{x^k}{\|(x^k, y^k)\|}\Big\}$ and $\Big\{\frac{y^k}{\|(x^k, y^k)\|}\Big\}$ are all bounded. Thus, we have that

which is in contradiction to (5.11). The proof is completed.

Remark 5.1. In the proof of Theorem 5.1, the second inequality in (5.6) is essential and it only holds for $t\in (0, 1/2]$. This is why we replace the parameter $\mu$ by $\mu^t$ ($t\in (0, 1/2]$) for the CHKS function in (3.1).

Theorem 5.2. Suppose that $F$ is monotone and the solution set of the $\textrm{SOCCP}$ is nonempty. Let $\{z^k = (\mu_k, x^k, y^k)\}$ be the iteration sequence generated byAlgorithm $\textrm{4.1}$. Then

Proof. Since $\{ f_t(z^k)\}$ is monotonically decreasing, it is convergent. So, there exists a constant $f^*\ge0$ such that

Now we assume $f^* > 0$ and will thus derive a contradiction. Since the sequence $\{z^k = (\mu_k, x^k, y^k)\}$ is bounded, it has at least one accumulation point, denoted by $z^*: = (\mu^*, x^*, y^*)$. Then there exists an infinite subsequence $\{z^k\}_{k\in K}\subset\{z^k\}$ such that $\lim\limits_{k\in K, k\rightarrow \infty} z^k = z^*$. We now divide the proof into the following two parts.

Part 1. Assume that $\alpha_k\geq c$ for all $k\in K$, where $c > 0$ is a fixed constant. Then from Steps 3 and 4, we have the following for all $k\in K$

By letting $k\rightarrow \infty$ with $k\in K$ on both sides of the inequality (5.13), we have that $f^*\leq (1-\sigma c^2) f^*$ which gives $f^* = 0.$ This contradicts the assumption $f^* > 0$.

Part 2. Assume that there exists an infinite subset $\bar{K}\subset K$ such that $\lim\limits_{k\in \bar{K}, k\rightarrow \infty} \alpha_k = 0$. Then, by the line search criterion (4.4), we have the following for all $k\in \bar{K}$

i.e.,

By (5.1), we have that $\mu^*\geq\gamma\min\{1, f^*\} > 0.$ Thus, $f_t(z)$ is continuously differentiable at $z^*$. By letting $k\rightarrow \infty$ with $k\in \bar{K}$ on both sides of the inequality (5.14), we have that

where $\Delta z^*: = { H}_t'(z^{*})^{-1}[-{ H}_t(z^*)+\zeta^*h'(\mu^*)\bar{z}]$. On the other hand, from Step 3 it follows that

By letting $k\rightarrow \infty$ with $k\in \bar{K}$ on both sides of the inequality (5.16), we have that

Hence, we can conclude from (5.15) and (5.17) that $f'_t(z^*)\Delta z^* = 0.$ By (4.3), we have the following for all $k\geq0$

By letting $k\rightarrow \infty$ with $k\in \bar{K}$ on both sides of the inequality (5.18), and also using $f'_t(z^*)\Delta z^* = 0$, we have that $2[1-\gamma(\eta_1+\eta_2)] f^*\le0$ which together with $\gamma(\eta_1+\eta_2) < 1$ yields $f^* = 0$. This also contradicts the assumption $f^* > 0$. We complete the proof.

Theorem 5.3. Suppose that $F$ is monotone and the solution set of the $\textrm{SOCCP}$ is nonempty. Then any accumulationpoint of the iteration sequence $\{z^k\}$ generated by Algorithm $\textrm{4.1}$ is a solution of $f_t(z) = 0$.

Proof. The theorem holds under the conditions of (5.12) and the continuity of $f_t$.

Similar to the proof of Theorem 8 in ^[19], we obtain the local superlinear and quadratic convergence of Algorithm 4.1 as follows.

Theorem 5.4. Suppose that $F$ is monotone and the solution set of the $\textrm{SOCCP}$ is nonempty. Suppose that $z^*$ is an accumulationpoint of the infinite sequence $\{z^k\}$ generated by Algorithm $\textrm{4.1}$. Suppose that $H$ is semismoothat $z^*$ and that all $V\in \partial H(z^*)$ are nonsingular. Then the whole sequence $\{z^k\}$ converges to $z^*$ and $\|z^{k+1}-z^*\| = o(\|z^k-z^*\|).$ Furthermore, if $H$ is strongly semismooth at $z^*$, then $\|z^{k+1}-z^*\| = O(\|z^k-z^*\|^2).$

6.   Numerical experiments

In this section, we discuss how we applied Algorithm 4.1 to solve some SOCCPs. All experiments were performed on a personal computer with 1.96 GB of memory and a Pentium(R) Dual-Core processor 2.93 GHz. The program codes were written in Matlab and run in a Matlab 7.1 environment. For the experiments, we chose $h(\mu) = e^\mu-1$, $\mu_0 = 10^{-2}, \gamma = 10^{-4}, \sigma = 10^{-3}, \delta = 0.8$ and $t = 0.5$. We applied $\| H_t(z^k)\|\leq10^{-5}$ as the stopping criterion.

Example 6.1. Consider the following linear SOCCP:

where

Obviously, $F$ is monotone. It is easy to see that $x = (\alpha+1, \alpha)^T$ and $y = (0, 0)^T$ is the solution of the SOCCP for any $\alpha\geq-0.5$. Thus, the solution set of the SOCCP is unbounded. For the experiments, we chose the starting points as follows: (1) $x^0 = {\textbf{rand}}(2, 1), \; y^0 = {\textbf{rand}}(2, 1);$ (2) $x^0 = 100\times{\textbf{rand}}(2, 1), \; y^0 = 100\times{\textbf{rand}}(2, 1);$ (3) $x^0 = 10\times{\textbf{rand}}(2, 1), \; y^0 = Mx^0+q;$ (4) $x^0 = -10\times{\textbf{rand}}(2, 1), \; y^0 = Mx^0+q.$ The numerical results are listed in Table 1 where $\bf{ ST}$ denotes the starting point, $\bf {IT}$ denotes the number of iterations, $\bf {HK}$ denotes the value of $\| H_t(z)\|$ when Algorithm 4.1 terminates and $\bf {SOL}$ denotes the solution obtained via Algorithm 4.1.

Example 6.2. Consider the following linear SOCCP:

where

In this example, $F$ is also monotone. It is easy to see that $x = (\alpha, \alpha, 0)$ and $y = (0, 0, 0)$ is the solution of the SOCCP for any $\alpha\geq0$. Thus, the solution set of the SOCCP is also unbounded. A main difference between Example 6.1 and Example 6.2 is that the SOCCP considered in Example 6.2 does not have a strictly complementary solution. For the experiments, the starting points were chosen as follows: (1) $x^0 = y^0 = (1, 1, 1);$ (2) $x^0 = y^0 = (10, 10, 10);$ (3) $x^0 = y^0 = (1000, 1000, 1000);$ (4) $x^0 = (1, 1, 1), \; y^0 = Mx^0+q;$ (5) $x^0 = -(1, 1, 1), \; y^0 = Mx^0+q;$ (6) $x^0 = (10, 10, 10), \; y^0 = Mx^0+q;$ (7) $x^0 = -(10, 10, 10), \; y^0 = Mx^0+q.$ The testing results are listed in Table 2.

Example 6.3. Consider the following nonlinear SOCCP:

where $\mathcal{K} = \mathcal{K}^3\times \mathcal{K}^2$ and $F : \mathbb{R}^5\rightarrow \mathbb{R}^5$ is given by

From ^[9], $F$ is monotone. Via Algorithm 4.1, we obtain one solution $x^* \approx (0.2324, -0.0731,$ $0.2206, 0.5339, -0.5339)^T$. We test this problem by implementing the starting point $x^0 = y^0$ as follows: $(1)\; (0, ..., 0)^T;$ $(2)\; (1, ..., 1)^T; \; (3)\; (-1, ..., -1)^T; \; (4)\; (10, ..., 10)^T;$ $(5)\; (-10, ..., -10)^T;$ $(6)\; (100, ..., 100)^T;$ $(7)\; (-100,$ $..., -100)^T$. For the purpose of comparison, we also implemented the smoothing Newton-type method developed by Narushima, Sagara and Ogasawara ^[17] to solve this test problem, which has been designed based on the following Fischer-Burmeister smoothing function:

The numerical results are listed in Table 3.

Example 6.4. Consider the following nonlinear SOCCP:

where $\mathcal{K} = \mathcal{K}^4$ and $F : \mathbb{R}^4\rightarrow \mathbb{R}^4$ is given by

Via Algorithm 4.1, we obtain one solution $x^*\approx(0.3278, -0.1893, -0.1893, -0.1893)^T.$ We tested this problem by implementing the starting point $x^0 = y^0$ as follows: $(1)\; (0, ..., 0)^T; (2)\; (1, ..., 1)^T; (3)\; (-1, ..., -1)^T;$ $(4)\; (2, ..., 2)^T; (5)\; (-2, ..., -2)^T; (6)\; (4, ..., 4)^T; (7)\; (-4, ..., -4)^T;$ $(8)\; (5, ..., 5)^T; (9)\; (-5, ..., -5)^T;$ $(10)\; (10, ..., 10)^T; \; (11)\; (-10, ..., -10)^T$. The numerical results are listed in Table 4, where $*$ denotes that the algorithm fails to get an optimizer in the short CPU time.

From Tables 1 and 2, we can find that Algorithm 4.1 can solve all of the tested problems in very few iterations. Moreover, the numbers of iterations were slightly different for different starting points. From Tables 3 and 4, we may see that our algorithm has some advantages over the smoothing Newton-type algorithm presented in ^[17]. Although the reported numerical results are preliminary, they demonstrate that the proposed algorithm is promising for solving SOCCPs even though the solution sets of these problems are unbounded.

7.   Concluding remarks

Based on the regularized CHKS smoothing function $\phi_t$ in (3.1), we have proposed a class of smoothing Newton-type methods for solving the SOCCP. Unlike many smoothing Newton-type methods, which usually require the boundedness of the solution set, our method is globally and locally superlinearly/quadratically convergent when the solution set of the SOCCP is only nonempty, and it does not require its boundedness.

In the reformulation of the SOCCP, we need a function $h$ that satisfies the conditions (a)–(e) in Assumption 3.1. Some comments on these conditions are explained as follows. The condition (a) ensures that $H_t(z)$ is smooth and $\frac{h(\mu)}{h'(\mu)}$ is well-defined. The condition (b) guarantees that $H_t(z) = 0$ gives $\mu = 0$ and that $(x, y)$ is a solution of the SOCCP. The conditions (c) and (d) ensure that the sequence $\{\mu_k\}$ generated by Algorithm 4.1 is positive and bounded. The condition (e) ensures that the search direction is the direction of descent of the merit function.

Acknowledgements

This work has been supported by the Natural Science Foundation of Henan Province (222300420520) and Key Scientific Research Projects of Higher Education of Henan Province (22A110020). We are very grateful to the referees for their valuable comments and suggestions on the paper as they have considerably improved the paper.

Conflict of interest

The authors declare no conflict of interest.