A Modified Newton Method Based on the Metric Projector for Solving SOCCVI Problem ()
1. Introduction
There have been many publications about computational approaches to solve the optimization problems such as linear programming, nonlinear programming, variational inequalities, and complementarity problems, see [1] - [6] and references therein. Some complementarity functions, such as nature function and Fischer-Burmeister (FB) function, have been widely and deeply studied for dealing with nonlinear complementarity problems and variational inequality problems with polyhedral cone constraints, see the famous book by Facchiniei and Pang [7]. A lot of methods for complementarity problems, variational inequality problems and nonsmooth equations have been studied by some researchers, see [7] - [16]. Based on the above research, we used the Fischer-Burmeister operator over the second order cone to deal with second-order cone constrained variational inequality (SOCCVI) problems, see [17]. However, in [17], we have only studied the first-order necessary conditions for SOCCVI problem, and no results about the second-order sufficient conditions of SOCCVI have appeared.
In this paper, we define the second-order sufficient condition of SOCCVI based on the metric projector. Based on the second-order sufficient condition and the constraint nondegeneracy, we prove the nonsingularity of the Clarke's generalized Jacobian of the Karush-Kuhn-Tucker system, constructed by the metric projector.
The second-order cone constrained variational inequality (SOCCVI) problem is to find
satisfying
(1)
where the set Q is finitely representable and expressed as
Here
denotes the Euclidean inner product,
,
and
are continuously differentiable functions, and
is a Cartesian product of second-order cones (or Lorentz cones), expressed as
(2)
with
,
,
. We denote
and
for
. So we have the following equivalence relations
The convex second-order cone program (CSOCP):
(3)
where
,
, and
, is the special case of the SOCCVI problem. The SOCCVI can be solved by analyzing its KKT conditions:
(4)
where
is the variational inequality Lagrangian function,
and
. In [18], we also point out that the neural network approach for SOCCVI was already studied.
As mentioned earlier, this paper investigates the characterizations of the strong regularity of Karush-Kuhn-Tucker (KKT) for SOCCVI via the metric projector. In this paper, we use the sufficient condition of the nonsingularity the Clarke's generalized Jacobian of the KKT system of (1), which deduces the nonsingularity of the Clarke’s generalized Jacobian of this system and the strong regularity of the KKT point. We employ modified Newton method for solving the SOCCVI problem and obverse the numerical performance.
2. Preliminaries
In this section, we organize some basic knowledge points. Most of these basic knowledge points can be found in [19].
We briefly recall some concepts associated with SOC, which are helpful for understanding the target problems and our analysis techniques. For any two vectors
and
in
, we use the Euclidean inner product
, and the norm
is induced by this inner product, i.e.,
. And we define their Jordan product as
. Then,
together with the element
give rise to a Jordan algebra. Note that
means
and
means the usual componentwise addition of vectors. It is known that
for all
. Moreover, if
, then there exists a unique vector in
, denoted by
, such that
. We also denote
. Any
has the following spectral decomposition:
(5)
where
are the spectral values and the associated spectral vectors of a, given by
(6)
for
, where c is any vector in
satisfying
.
Suppose
having the spectral decomposition as (5), then the merit projector of u onto
, denoted by
, is
(7)
here
. we have
(8)
Lemma 2.1. Let the metric projection operator
is directionally differentiable at x for any
,
where
.
We recall from Lemma 2.5 in [20] the characterization of the tangent cone of a second-order cone at a point in it.
Lemma 2.2. Consider the second-order cone
and let
. Then, the tangent cone and the second-order tangent cone of
at a are
and
For the convenience of discussions, we need the definition of the tangent cone, regular and normal cone of a closed set at a point, all the concepts are taken from [21].
Definition 2.1. For a closed set
and a point
, define the following sets: the tangent (Bouligand) cone
theregular (Frchet)normal cone
thelimiting (in the sense of Mordukhovich)normal cone
If K is a closed convex set, then
.
Let
and N be finite-dimensional real Hilbert spaces and f is a mapping from
to N. If f is Fréchet differentiable at
, then we use
(respectively,
) to denote the Fréchet derivative of f at
(respectively, the partial Fréchet derivative of f at
with respect to a). And let
be the adjoint of
(respectively,
), where the adjoint operator
satisfies the following formula: if the operation is consistent, then
. If f is twice Fréchet differentiable at
, we define
3. The Optimality Condition and Nonsingularity Theorem
Let
be the Lagrangian of (1), where
. Let
be a locally optimal solution to (1). Then,
satisfies the following Karush-Kuhn-Tucker condition. Using the NR function and the definition of the normal cone, the KKT condition can be expressed as
Mimicking the arguments described as in [17], we can verify that the KKT system (4) is equivalent to the following unconstrained smooth minimization problem:
(9)
where
and
is given by
with
. In other words,
is a smooth merit function for the KKT system (4).
By [20], we give the following definition and theorem.
Definition 3.1. Let
be a feasible point of (1) such that
. We say that the second-order sufficient condition holds at
if
(10)
Theorem 3.1. Let
is the KKT point of (1). Assume that
(i)
;
(ii) thesecond-order sufficient condition (10)holds;
(iii)
holds;
(iv) thefollowing constraint nondegeneracy holds,
(11)
then
is nonsingular.
Proof. It follows from
that
is differentiable at
. Let
. we have
(12)
Let
(We need to show
,
,
). We get
(13)
which implies that
. From the first line of (12), we get that
(14)
Define the index sets:
If
,
, we have
Note that
and
From
, we can deduce that
Hence
Condition (iii) of Theorem 3.1 means
and
is a linear space. Therefore,
In addition, by Lemma 2.3 and (13), we can deduce that
(15)
where
. From (15), we have
that is
where
.
Case (I). If
, we have
(16)
When
,
. Now we need to prove that
and
(17)
From
, we have
where
and
. Hence
(18)
(16) and (18) imply
which means
.
It follows from (16) that
(19)
Therefore, we can deduce that
which is
(20)
From (20), we get
Hence, (17) holds.
Case II. Let
. From the second equation of (13), we can get that
It follows from the projection of the second-order cone that
Case III. Let
. From the second equation of (13), we can get that
Then
.
To sum up the above three situations,
implies
From (12) and (13), we assume that
(21)
(22)
(23)
By (21) and (22), we have
For
,
(24)
By (19), we get
(25)
Since
(26)
and
(27)
From (25), (26) and (27), we get that
that is
(28)
Note that
(29)
It follows from (24), (28) and (29) that
(30)
From (30) and (14), we have
From the second-order sufficient condition, we have
. Hence, from (21), we deduce
(23) and condition (iv) of Theorem 3.1 imply
,
. Therefore,
is nonsingular.
4. A Modified Newton Method and Numerical Experiments
In this section, we use a modified Newton algorithm to solve the unconstrained smooth minimization problem (9).
The presented algorithm is actually a counterpart in the case of second order cone constrained VI problems of ( [7], Algorithm 9.1.10), which is used to solve polyhedral cone constrained VI problems. Note that although
is nonsmooth, the merit function
is continuously differentiable if f is, see ( [7], Proposition 1.5.3). In the following proposition we give the relationship between the merit function and the KKT condition.
Proposition 4.1. Suppose that
and
are continuously differentiable. If
is nonsingular, then every stationary point of the merit function
is a KKT triple of the SOCCVI.
The proof of Proposition 4.1 is similar to that of Proposition 4.1 in [17], so we omit it here.
Algorithm 4.1
Data Given
,
,
and
.
Step 1 Set
.
Step 2 If
is a stationary point of
stop.
Step 3 Find a solution
of the system
(31)
If the system (31) is not solvable or if the condition
(32)
is not satisfied, (re)set
.
Step 4 Find the smallest nonnegative integer
such that, with
,
(33)
set
.
Step 5 Set
and
; go to step 2.
The superlinear convergence of Algorithm 4.1 can be obtained by reference to Algorithm 4.1 in [17]. To demonstrate effectiveness of the Newton method, some illustrative SOCCVI problems are tested. Observe that all the trajectories were successfully able to converge to the SOCCVI solution.
5. Numerical Experiments
Example 5.1. Consider the SOCCVI problem (1) where
and
This problem has a solution
. It can be verified that the Lagrangian function for this example is
The gradient of the Lagrangian function is
where I is the identity mapping and
is the gradient of
. For example 5.1, Table 1 is a comparison chart of the results of different complementarity functions.
In our simulations, the initial points are
,
, and the stopping criterion is set at
. The trajectories of Algorithm 4.1 for the above problems are shown in Figure 1 and Figure 2.
Example 5.2. Consider the SOCCVI problem (1) where
Table 1. The results of Example 5.1.
Figure 1. Transient behavior of x in Example 5.1 with
and
.
Figure 2. Convergence behavior of the error
for Example 5.1.
and
This problem has an approximate solution
. It can be verified that the Lagrangian function for this example is
The gradient of the Lagrangian function is
where I is the identity mapping and
is the gradient of
. For example 5.2, Table 2 is a comparison chart of the results of different complementarity functions.
In our simulations, the initial points are
,
, and the stopping criterion is set at
. The trajectories of Algorithm 4.1 for the above problems are shown in Figure 3 and Figure 4.
Table 2. The results of Example 5.2.
Figure 3. Transient behavior of x in Example 5.2 with
and
.
Figure 4. Convergence behavior of the error
for Example 5.2.
Table 3. The results of Example 5.3.
Example 5.3. Consider the SOCCVI problem (1) where
and
For example 5.3, Table 3 is a comparison chart of the results of different complementarity functions.
This problem has a solution
. In our simulations, the initial points are
,
, and the stopping criterion is set at
. The trajectories of Algorithm 4.1 for the above problems are shown in Figure 5 and Figure 6.
Example 5.4. Consider the SOCCVI problem (1) where
Figure 5. Transient behavior of x in Example 5.3 with
and
.
Figure 6. Convergence behavior of the error
for Example 5.3.
and
This problem has a solution
. In our simulations, the initial points are
,
, and the stopping criterion is set at
. Comparison of decay rates of
for the two complementary function (FB function and NR function) in Figure 7 The error plots shown in Figure 7 reveal that the NR function and FB function have almost the same convergence rates.
Figure 7. Convergence behavior of the error
for Example 4.
6. Conclusion
In this paper, we target the second-order cone constrained variational inequality (SOCCVI) problem by using the modified Newton algorithm which is applied in [17], based on the metric projector. We have established that for a locally optimal solution to a SOCCVI problem, the nonsingularity of the Clarke’s generalized Jacobian of the KKT system, constructed by the metric projector, is equivalent to the second-order sufficient condition and constraint nondegeneracy. Three numerical simulations are conducted which show the efficiency of the Newton algorithm. This paper improves our previous work [17].
Founding
This work is supported by National Natural Science Foundation of China (Grant No.11301348).