Volume 2021, Issue 1 6674520

Research Article

Open Access

Jacobian Consistency of a Smoothing Function for the Weighted Second-Order Cone Complementarity Problem

Wenli Liu

School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Xiaoni Chi,

Corresponding Author

Xiaoni Chi

[email protected]

orcid.org/0000-0003-2737-5163

School of Mathematics and Computing Science, Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Qili Yang,

Qili Yang

School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Ranran Cui,

Ranran Cui

School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Wenli Liu,

Wenli Liu

School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Xiaoni Chi,

Corresponding Author

Xiaoni Chi

[email protected]

orcid.org/0000-0003-2737-5163

School of Mathematics and Computing Science, Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Qili Yang,

Qili Yang

School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

Ranran Cui,

Ranran Cui

School of Mathematics and Computing Science, Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electronic Technology, Guilin 541004, China gliet.edu.cn

Search for more papers by this author

First published: 23 January 2021

https://doi.org/10.1155/2021/6674520

Academic Editor: Guoqiang Wang

Share a link

Email
Wechat
Bluesky

Abstract

In this paper, a weighted second-order cone (SOC) complementarity function and its smoothing function are presented. Then, we derive the computable formula for the Jacobian of the smoothing function and show its Jacobian consistency. Also, we estimate the distance between the subgradient of the weighted SOC complementarity function and the gradient of its smoothing function. These results will be critical to achieve the rapid convergence of smoothing methods for weighted SOC complementarity problems.

1. Introduction

The weighted second-order cone complementarity problem (WSOCCP) is, for a given weight vector

and a continuously differentiable function F : ℝⁿ × ℝⁿ × ℝ^m⟶ℝ^n+m, to find vectors (x, s, y) ∈ ℝⁿ × ℝⁿ × ℝ^m such that

(1)

where ∘ represents the Jordan product and

is the Cartesian product of second-order cone, that is,

with

. The set

is the second-order cone (SOC) of dimension n_i defined by

(2)

and the interior of the SOC

is the set

(3)

Here ‖⋅‖ is the Euclidean norm, and

(4)

Obviously, if w = 0, WSOCCP (1) reduces to second-order cone complementarity problem (SOCCP). In this article, we may assume that r = 1 and in the following analysis, since it can easily be extended to the general case.

In order to reformulate several equilibrium problems in economics and study highly efficient algorithms to solve these problems, Potra [1] introduced the notion of a weighted complementarity problem (WCP). He showed that the Fisher market equilibrium problem can be modeled as a monotone linear WCP. Moreover, the linear programming and weighted centering (LPWC) problem, which was introduced by Anstreicher [2], can also be formulated as a monotone linear WCP. And Potra [1] analyzed two interior-point methods for solving the monotone linear WCP over the nonnegative orthant. Since then, many scholars are dedicated to investigating the theories and solution methods of WCP. Tang [3] gave a new nonmonotone smoothing-type algorithm to solve the linear WCP. Chi et al. [4] studied the existence and uniqueness of the solution for a class of WCPs.

As is well known, smoothing methods have superior theoretical and numerical performances. For solving the SOCCP by smoothing methods, we usually reformulate the SOCCP as a system of equations based on parametric smoothing functions of SOC complementarity functions [5, 6]. The smoothing parameter involved in smoothing functions may be treated as a variable [7] or a parameter with an appropriate parameter control [8]. In the latter case, the Jacobian consistency is important to achieve a rapid convergence of Newton methods or Newton-like methods. Hayashi et al. [8] proposed a combined smoothing and regularized method for monotone SOCCP, and based on the Jacobian consistency of the smoothing natural residual function, they proved that the method has global and quadratic convergence. Krejić and Rapajić [9] gave a nonmonotone Jacobian smoothing inexact Newton method for nonlinear complementarity problem and proved the global and local superlinear convergence of the method. Chen et al. [10] presented a modified Jacobian smoothing method for the nonsmooth complementarity problem and established the global and fast local convergence for the method.

In this paper, we consider the function φ : ℝⁿ × ℝⁿ⟶ℝⁿ for WSOCCP

(5)

with a given vector

. If w = 0, φ (5) reduces to the SOC complementarity function [6] with τ = 3:

(6)

Since φ is nonsmooth, we define the following smoothing function φ_μ:

(7)

where μ ∈ ℝ is a smoothing parameter.

The main contribution of this paper is to show the Jacobian consistency of the smoothing function (7) and estimate the distance between the subgradient of the weighted SOC complementarity function (5) and the gradient of its smoothing function (7). These properties will be critical to solve weighted SOC complementarity problems by smoothing methods.

The paper is organized as follows. In Section 2, we review some concepts and properties. In Section 3, we derive the computable formula for the Jacobian of the smoothing function in WSOCCP. In Section 4, we show the Jacobian consistency of the smoothing function and estimate the distance between the gradient of smoothing function and the subgradient of the weighted SOC complementarity function. Some conclusions are reported in Section 5.

Throughout this paper, ℝ₊ denotes the set of nonnegative numbers. ℝⁿ and ℝ^m×n denote the space of n-dimensional real column vectors and the space of matrices, respectively. We use ‖⋅‖ to denote the Euclidean norm and define for a vector x or the corresponding induced matrix norm. For simplicity, we often use x = (x₀; x₁) instead of the column vector . and mean the topological interior and the boundary of the SOC , respectively. For a given set S ⊂ ℝ^m×n, convS denotes the convex hull of S in ℝ^m×n, and for any matrix X ∈ ℝ^m×n, dist(X, S) denotes inf{‖X − Y‖ : Y ∈ S}.

2. Preliminaries

In this section, we briefly recall some definitions and results about the Euclidean Jordan algebra [11] associated with the SOC and subdifferentials [12].

For any x, s ∈ ℝⁿ, their Jordan product is defined as x∘s = (x^Ts; x₀s₁ + s₀x₁), and e = (1,0, …, 0) ∈ ℝⁿ is unit element of this algebra. Given an element x = (x₀; x₁) ∈ ℝ × ℝⁿ⁻¹, we define the symmetric matrix

(8)

where I represents the (n − 1) × (n − 1) identity matrix. It is easy to verify that x∘s = L(x)s for any s ∈ ℝⁿ. Moreover, L(x) is positive definite (and hence invertible) if and only if

For each x = (x₀; x₁) ∈ ℝ × ℝⁿ⁻¹, let λ₁, λ₂ and u⁽¹⁾, u⁽²⁾ be the spectral values and the associated spectral vectors of x, given by

(9)

for i = 1,2, with any

such that

. Then, x admits a spectral factorization associated with SOC

in the form of

(10)

For any x = (x₀; x₁) ∈ ℝ × ℝⁿ⁻¹, let x^′ = (x₀; −x₁)[13]. Then, x^″ = x, (x + s)^′ = x^′ + s^′, and (cx)^′ = cx^′ for any c ∈ ℝ. Moreover, if .

Suppose that G : ℝ^m⟶ℝⁿ is a locally Lipschitzian function; then, from Rademacher’s theorem [14], G is differentiable almost everywhere. The Bouligand (B-) subdifferential and the Clarke subdifferential of G at z are defined by

(11)

where D_G denotes the set of points at which G is differentiable. Obviously, ∂G(z) = {G^′(z)} if G is continuously differentiable at z.

Definition 1 (see [12].)Let G : ℝ^m⟶ℝⁿ be a locally Lipschitzian function and G_μ : ℝ^m⟶ℝⁿ be a continuously differentiable function for any μ > 0, and for any z ∈ ℝ^m, we have lim_μ⟶0G_μ(z) = G(z). Then, G_μ satisfies the Jacobian consistency property if for any z ∈ ℝ^m, .

3. Smoothing Function

In this section, we study the properties of the smoothing function (7).

Definition 2 (see [8].)For a nondifferentiable function f : ℝ^m⟶ℝⁿ, we consider a function f_μ : ℝ^m⟶ℝⁿ with a parameter μ > 0 that has the following properties:

(i)
f_μ is differentiable for any μ > 0
(ii)
lim_μ⟶0f_μ(x) = f(x) for any x ∈ ℝ^m

Such a function f_μ is called a smoothing function of f.

Lemma 1. For any and μ ∈ ℝ, one has

(12)

Proof. We first suppose that . Then,

(13)

and hence

(14)

That is, φ_μ(x, s, w) = 0.

Conversely, suppose that φ_μ(x, s, w) = 0; then, it follows from (7) that

(15)

Upon squaring both sides of it, we obtain

(16)

Let

(17)

which implies

(18)

Therefore,

(19)

Further, it follows from Proposition 3.4 [15] that

(20)

Let

, μ ∈ ℝ, x = (x₀; x₁), s = (s₀; s₁) ∈ ℝ × ℝⁿ⁻¹, and the mapping υ^μ : ℝ²ⁿ⟶ℝ × ℝⁿ⁻¹ be defined by

(21)

For simplicity, we use υ to denote υ^μ when μ = 0, that is,

(22)

By direct calculations, we have

(23)

Therefore,

. From the definition of spectral factorization, υ^μ can be decomposed as

(24)

where λ₁(υ^μ), λ₂(υ^μ), and u₁(υ), u₂(υ) are the spectral values and the associated spectral vectors of υ^μ given by

(25)

and

(26)

for i = 1,2, where

(27)

if υ₁ ≠ 0; otherwise,

is any vector in ℝⁿ⁻¹ such that

. For any given

and any (x, s) ∈ ℝⁿ × ℝⁿ, it can be verified that

(28)

for any μ > 0, and

(29)

Given μ ∈ ℝ and x = (x₀; x₁), s = (s₀; s₁) ∈ ℝ × ℝⁿ⁻¹, we define

(30)

and when μ = 0,

(31)

The spectral factorization of ω^μ and ω is as follows:

(32)

By (29), we can partition ℝ²ⁿ as

, where

(33)

Lemma 2. For any given and any (μ, x, s) ∈ ℝ × ℝⁿ × ℝⁿ, let φ and φ_μ be defined as (5) and (7), respectively. Then, we have

(i)
The function φ_μ is continuously differentiable everywhere with any μ > 0, and its Jacobian is given by
(34)
Here if υ₁ = 0; otherwise,
(35)
with
(36)

(37)
where
(38)
(ii)
For any (x, s) ∈ ℝⁿ × ℝⁿ, we have lim_μ⟶0φ_μ(x, s, w) = φ(x, s, w). Thus, φ_μ is a smoothing function of φ.
(iii)
For any μ, ν ∈ ℝ₊,
(39)

Proof.

(i)
For any (x, s) ∈ ℝⁿ × ℝⁿ and any μ > 0, according to Corollary 5.4 [15] and (28), formula (34) holds. By Proposition 5.2 and its proof [15], we get formula (35).
(ii)
Given any x = (x₀; x₁), s = (s₀; s₁) ∈ ℝ × ℝⁿ⁻¹. For any μ > 0, we obtain from the spectral factorization of υ^μ and υ that
(40)
where
(41)
and λ_i(υ^μ) and u_i(υ) are, respectively, given by (25) and (26) for i = 1,2. It is obvious that
(42)
for i = 1,2. Then,
(43)
and lim_μ⟶0φ_μ(x, s, w) = φ(x, s, w). Thus, by (i) and Definition 2, φ_μ is a smoothing function of φ.
(iii)
By following the proof of Proposition 5.1 [15], we obtain the desired result.

Next, we study some properties of φ, which will be used in the subsequent analysis.

Lemma 3. For any , let . Then, we have

(44)

Proof. We can obtain the desired result by following the proof of Lemma 2 [16].

Lemma 4. For any x = (x₀; x₁), s = (s₀; s₁) ∈ ℝ × ℝⁿ⁻¹, let . Then, one has

(45)

(46)

(47)

(48)

(49)

where

. Moreover, the following equivalence holds:

(50)

Proof. Since

(51)

from Lemma 3, we have

(52)

It follows from these equalities that the results in (45)–(47) hold. Since , we have λ₁(υ) = 0, i.e.,

(53)

By the last relation and (45)–(47), we obtain that (49) holds. To prove (48), we only need to verify x₀υ₁ = υ₀x₁ and by the symmetry of x and s in υ. From (45)–(47) and (49),

(54)

From (51), the equivalence is also true.

4. Jacobian Consistency

In this section, we will show the Jacobian consistency property and estimate the distance between the gradient of the smoothing function (7) and the subgradient of the WSOCCP complementarity function (5). For any μ ∈ ℝ,

, let z≔(x, s, y) ∈ ℝⁿ × ℝⁿ × ℝ^m. Based on smoothing function (7), we define Φ_μ : ℝⁿ × ℝⁿ × ℝ^m⟶ℝ^2n+m by

(55)

(56)

From (1) and (56) and Lemma 1,

(57)

Since the function Φ(z) is typically nonsmooth, Newton’s method cannot be applied to the system Φ(z) = 0 directly. Thus, we can approximately solve the smooth system Φ_μ(z) = 0 at each iteration and make ‖Φ_μ(z)‖ decrease gradually by reducing μ to zero. First, we show that the function Φ_μ(z) satisfies the Jacobian consistency.

Lemma 5. For any arbitrary but fixed vector , we have for any (μ, x, s) ∈ ℝ × ℝⁿ × ℝⁿ,

(58)

where

(59)

Proof. By (34) and the symmetry of x and s, it suffices to prove

(60)

Case 1. If (x, s) ∈ ℐ, it follows from (25) that

(61)

Therefore,

(62)

Case 2. If (x, s) ∈ ℬ, it is easy to prove (51), and

(63)

Thus, we obtain the following from (25):

(64)

(65)

For any μ ≠ 0, we may get from (35) that L⁻¹(ω^μ) = L₁(υ^μ) + L₂(υ^μ). We first prove for any μ ≠ 0,

(66)

Let

(67)

Based on (36), (48), and (64), we have

(68)

Next, we prove lim_μ⟶0L₂(υ^μ) = J. From (37), (64), and (65), we have

(69)

Combining (68) and (69) yields

(70)

Case 3. If , it follows from Lemma 4 that (x, s, w) = (0,0,0) and

(71)

Lemma 6. For any arbitrary but fixed vector , we have for any (x, s) ∈ ℝⁿ × ℝⁿ,

(72)

where

(73)

and J is defined by (59).

Proof. By Proposition 5.2 [15] and the chain rule for differentiation, the complementarity function φ is continuously differentiable at any (x, s) ∈ ℐ with

(74)

Thus, it suffices to consider the two cases: (x, s) ∈ ℬ and .

For any (x, s) ∈ ℬ or , let with sufficiently small μ ≠ 0, and define

(75)

Then, we have

(76)

(77)

Obviously, when μ⟶0, we have for i = 1,2. Then by (7), it suffices to show

(78)

if φ is differentiable at

Case 4. If (x, s) ∈ ℬ, we obtain , and from (45), (46), and (48),

(79)

The last relation together with υ₀ > 0 implies that for sufficiently small μ, we have

(80)

For sufficiently small μ ≠ 0, we obtain from (77) and (80),

(81)

(82)

It follows from (81) and (82) that , and hence φ is differentiable at .

Now we will prove

(83)

where

, in which

and

are given by (36) and (37) with

and

replacing υ^μ and

, respectively. By the expression of

and (80),

(84)

By (45), (46), (48), and (84), we have

(85)

Thus, from (36) and (81),

(86)

It follows from (73)–(84) that as μ⟶0,

(87)

Then, by following the proof of Case 5 in Lemma 5, we have

(88)

Therefore, we obtain from (86) and (88) that

(89)

Next we will prove

(90)

By (45), (46), (48), (81), and (84), we have

(91)

and then

(92)

Therefore, we obtain from (88) and (92) that

(93)

Case 5. If , it follows from Lemma 4 that (x, s, w) = (0,0,0). Thus, , , and

(94)

Now we show the Jacobian consistency of the function Φ_μ (56) and then estimate an upper bound of the parameter μ > 0 for the predicted accuracy of the distance between the gradient of Φ_μ (56) and the subgradient of Φ (55).

Theorem 1. The following results hold. (i) The function Φ_μ defined by (56) with μ > 0 satisfies the Jacobian consistency. (ii) For given τ > 0 and any point z≔(x, s, y) ∈ ℝ^2n+m, let ρ(x, s) be any function such that

(95)

and let

be defined by

(96)

Then, for any μ ∈ ℝ such that , we have

(97)

Proof. By (56), it suffices to show the Jacobian consistency of φ_μ with μ > 0. Define

(98)

where

(99)

for i = 1,2, J and Z are defined by (59) and (73). Let

(100)

It follows from Lemma 5 and Lemma 6 that

(101)

and V¹, V² ∈ ∂_Bφ(x, s, w). Hence,

(102)

which together with Definition 1 and Lemma 2 implies the Jacobian consistency of φ_μ with μ > 0. (ii) For any z≔(x, s, y) ∈ ℝ^2n+m, it follows from the proof of Theorem 1(i) that

(103)

Thus, we obtain from (34) and (100) that

(104)

Then, similar to the proof of Proposition 4.1 [13], we have

(105)

where g_μ : ℝ²ⁿ⟶ℝ₊ is given by

(106)

Hence, by following the proof of Theorem 4.1 [13], the result holds.

5. Conclusions

In this paper, we show the Jacobian consistency of the smoothing function φ_μ for WSOCCP, which will play a key role in analyzing the rapid convergence of smoothing methods. Moreover, in order to adjust a parameter appropriately in smoothing methods, we estimate the distance between the gradient of the smoothing function φ_μ and the subgradient of the weighted SOC complementarity function φ.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (no. 11861026), Guangxi Key Laboratory of Cryptography and Information Security (no. GCIS201819), and Guangxi Key Laboratory of Automatic Detecting Technology and Instruments, China (no. YQ18112).

Open Research

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

References

1 Potra F. A., Weighted complementarity problems---a new paradigm for computing equilibria, SIAM Journal on Optimization. (2012) 22, no. 4, 1634–1654, https://doi.org/10.1137/110837310, 2-s2.0-84871544664.
10.1137/110837310
Web of Science® Google Scholar
2 Anstreicher K., Interior-point algorithms for a generalization of linear programming and weighted centring, Optimization Methods and Software. (2012) 27, no. 4-5, 605–612, https://doi.org/10.1080/10556788.2011.644791, 2-s2.0-84862690631.
10.1080/10556788.2011.644791
Web of Science® Google Scholar
3 Tang J., A variant nonmonotone smoothing algorithm with improved numerical results for large-scale LWCPs, Computational and Applied Mathematics. (2018) 37, no. 3, 3927–3936, https://doi.org/10.1007/s40314-017-0554-6, 2-s2.0-85049783205.
10.1007/s40314-017-0554-6
Web of Science® Google Scholar
4 Chi X., Gowda M. S., and Tao J., The weighted horizontal linear complementarity problem on a Euclidean Jordan algebra, Journal of Global Optimization. (2019) 73, no. 1, 153–169, https://doi.org/10.1007/s10898-018-0689-z, 2-s2.0-85049987969.
10.1007/s10898-018-0689-z
Web of Science® Google Scholar
5 Pan S. and Chen J.-S., A semismooth Newton method for SOCCPs based on a one-parametric class of SOC complementarity functions, Computational Optimization and Applications. (2010) 45, no. 1, 59–88, https://doi.org/10.1007/s10589-008-9166-9, 2-s2.0-77249176804.
10.1007/s10589-008-9166-9
Web of Science® Google Scholar
6 Chen J.-S. and Pan S., A one-parametric class of merit functions for the second-order cone complementarity problem, Computational Optimization and Applications. (2010) 45, no. 3, 581–606, https://doi.org/10.1007/s10589-008-9182-9, 2-s2.0-77950521302.
10.1007/s10589-008-9182-9
Web of Science® Google Scholar
7 Qi L., Sun D., and Zhou G., A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities, Mathematical Programming. (2000) 87, no. 1, 1–35, https://doi.org/10.1007/s101079900127, 2-s2.0-0002287357.
10.1007/s101079900127
Web of Science® Google Scholar
8 Hayashi S., Yamashita N., and Fukushima M., A combined smoothing and regularization method for monotone second-order cone complementarity problems, SIAM Journal on Optimization. (2005) 15, no. 2, 593–615, https://doi.org/10.1137/s1052623403421516, 2-s2.0-18744383641.
10.1137/S1052623403421516
Web of Science® Google Scholar
9 Krejić N. and Rapajić S., Globally convergent jacobian smoothing inexact Newton methods for NCP, Computational Optimization and Applications. (2008) 41, no. 2, 243–261.
10.1007/s10589-007-9104-2
Web of Science® Google Scholar
10 Chen P., Zhang P., Zhu X X. et al., Modified Jacobian smoothing method for nonsmooth complementarity problems, Computational Optimization and Applications. (2020) 75, no. 1, 205–305, https://doi.org/10.1007/s10589-019-00136-3.
10.1007/s10589-019-00136-3
Web of Science® Google Scholar
11 Faraut J. and Korányi A., Analysis on Symmetric Cones, 1994, Oxford University Press, New York, NY, USA.
10.1093/oso/9780198534778.001.0001
Web of Science® Google Scholar
12 Chen X., Qi L., and Sun D., Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Mathematics of Computation. (1998) 67, no. 222, 519–541, https://doi.org/10.1090/s0025-5718-98-00932-6.
10.1090/S0025-5718-98-00932-6
Web of Science® Google Scholar
13 Ogasawara H. and Narushima Y., The Jacobian consistency of a smoothed Fischer-Burmeister function associated with second-order cones, Journal of Mathematical Analysis and Applications. (2012) 394, no. 1, 231–247, https://doi.org/10.1016/j.jmaa.2012.04.050, 2-s2.0-84861661061.
10.1016/j.jmaa.2012.04.050
Web of Science® Google Scholar
14 Clarke F., Optimization and Nonsmooth Analysis, 1983, John Wiley & Sons, New York, NY, USA.
Google Scholar
15 Fukushima M., Luo Z., and Tseng P., Smoothing functions for second-order-cone complementarity problems, SIAM Journal on Optimization. (2001) 12, no. 2, 436–460.
10.1137/S1052623400380365
Web of Science® Google Scholar
16 Chen J. and Tseng P., An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Mathematical ProgrammingD. (2005) 104, no. 2-3, 293–327, https://doi.org/10.1007/s10107-005-0617-0, 2-s2.0-27244436420.
10.1007/s10107-005-0617-0
Web of Science® Google Scholar

All articles

Jacobian Consistency of a Smoothing Function for the Weighted Second-Order Cone Complementarity Problem

Abstract

1. Introduction

2. Preliminaries

3. Smoothing Function

4. Jacobian Consistency

5. Conclusions

Conflicts of Interest

Acknowledgments

Open Research

Data Availability

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Jacobian Consistency of a Smoothing Function for the Weighted Second-Order Cone Complementarity Problem

Abstract

1. Introduction

2. Preliminaries

3. Smoothing Function

4. Jacobian Consistency

5. Conclusions

Conflicts of Interest

Acknowledgments

Open Research

Data Availability

References

References

Related

Information