Some Convexificators-Based Optimality Conditions for Nonsmooth Mathematical Program with Vanishing Constraints ()
1. Introduction
We consider the following mathematical program with vanishing constraints
(1.1)
where
and
are the given functions.
The MPVC problem was firstly introduced by Achtziger and Kanzow [1], and it originated from the optimization topology design problems in mechanical structures [1]. The current researches show that the robot motion planning problem [2], the economic dispatch problem [3] and the nonlinear integer optimal control [4] [5] can all be transformed into the MPVC problem. As pointed out in [1], the major difficulty in solving problem (1) is that it does not satisfy most of the standard constraint qualifications, including linearly independent constraint qualification (LICQ for short) and Mangasarian-Fromovitz constraint qualification (MFCQ for short) at any interesting feasible point so that the standard optimization methods are likely to fail for this problem. The MPVC can be formulated as a mathematical program with equilibrium constraints (MPEC for short) and vice versa. However, the formulation has certain disadvantages like the introduction of additional solutions, the large dimension and so on. In [6], the MPVC can be formulated as a nonsmooth MPEC, but the reformulation violates the MPEC type constraint qualifications, which causes some trouble when solving the MPEC formulation by the suitable algorithms. These observations motivate us to consider it as an independent class of interesting optimization problems. The MPVC has attracted much attention in recent years. Several theoretical properties and different numerical approaches for MPVC can be found in [1] - [25].
It is well known that convexifactor is one of the important tools of nonsmooth analysis; the concept of convexificator was firstly introduced by Demyanov [26] in 1994 as a generalization of the notation of upper convex and lower concave approximation. It can be viewed as a weaker version of the notion of subdifferential. Indeed, the convexificator is in general a closed set unlike the well-known subdifferentials which are convex and compact sets. Moreover, for a locally Lipschitz function, most known subdifferentials are convexificators and these known subdifferentials may contain the convex hull of a convexificator [27]. Therefore, from the viewpoint of optimization and applications, the optimality conditions using convexificators are sharper than those using Clarke, Michel-Penot subdifferentials, etc. Convexificators were further studied by Demyanov and Jeyakumar [28], Jeyakumar and Luc [27], Dutta and Chandra [29] [30], etc. Recently, the notion of convexificators has been used to extend various results in nonsmooth analysis; see, e.g., [31] [32] [33] [34]. For nonsmooth optimization problems, various convexificators-based results with respect to the Fritz-John type and the Karush-Kuhn-Tucker type necessary optimality conditions have been developed in [32] [33] [34] [35] [36]. Very recently, Ansari, Movahedian and Nobakhtian [37] deal with constraint qualifications, stationary concepts and optimality conditions for a nonsmooth mathematical program with equilibrium constraints by using the notion of convexificators. However, the corresponding results about the nonsmooth mathematical program with vanishing constraints can be very few. Until recently, based on the Clarke subdifferential, Kazemi and Kanzi [21] study a broad class of mathematical programming with non-differentiable vanishing constraints. They firstly propose some various qualification conditions for this problem. Then, these constraint qualifications are applied to obtain, under different conditions, several stationary conditions of Karush-Kuhn-Tucker type.
In this paper, different from [21], by utilizing the concept of convexificators which is weaker than the Clarke subdifferential, we introduce the generalized standard Abadie constraint qualification and the generalized MPVC Abadie constraint qualification, and define the generalized stationary conditions for the nonsmooth MPVC. We derive the necessary and sufficient optimality conditions for nonsmooth MPVC under the generalized standard Abadie constraint qualification and some generalized convexity assumptions.
The rest of the paper is organized as follows. Section 2 contains the preliminaries and basic definitions which are used in the sequel. In Section 3, some necessary and sufficient optimality conditions are derived for nonsmooth MPVC based on the notion of convexificators. We close with some final remarks in the end.
2. Prelimilaries
In this section, we will give some basic definitions, which will be used in the sequel.
Let
be a nonempty subset contains the origin. The convex hull of S, the closure of S and the convex cone generated by S is denoted by
and
, respectively. The negative polar cone is defined by
.
Let
, the contingent cone
to S at x is defined by
Let
be an extended real valued function. The lower and upper Dini directional derivatives of f at x in the direction v are defined, respectively, by
and
Definition 2.1 [27] A function
is said to admit an upper convexificator,
at
if
is a closed set and for every
,
Definition 2.2 [27] A function
is said to admit a lower convexificator,
at
if
is a closed set and for every
,
A closed set
is said to be a convexificator of f at x if it is both upper and lower convexificator of f at x.
Definition 2.3 [30] A function
is said to admit an upper semi-regular convexificator,
at
if
is a closed set and for every
,
If the equality holds in the above inequality,then
is called as an upper regular convexificator of f at x.
Definition 2.4 [30] Let
be an extended real valued function that has an upper semi-regular convexificator at
. Then f is said to be
(i)
convex at
if for every
,
.
(ii)
pseudoconvex at
if for every
,
(iii)
quasiconvex at
if for every
,
3. Optimality Conditions for Nonsmooth Mathematical Program with Vanishing Constraints
In this section, we will develop several optimality conditions for nonsmooth MPVC in terms of the concept of convexificator. It is worth mentioning that since the upper convexificator is not necessary unique, all the new definitions given in this section depend on the the choice of the convexificator.
First, we introduce some notations. For the problem (1), we denote the feasible region by X, that is,
For
, we define the following index sets:
Now, we assume that all the functions have an upper convexificator at
. For the above index sets, we introduce the following notations:
Utilizing the above notations, motivated by [37], we are ready to introduce the Abadie type constraint qualification in the form of convexificator which is very important to establish the optimality conditions.
Definition 3.1. Let
, and assume that all of the functions have an upper convexificator at
. We say that the generalized standard Abadie constraint qualification (GS ACQ for short) holds at
if at least one of the dual sets used in the definition of
is nonzero and
.
Definition 3.2. Let
, and assume that all of the functions have an upper convexificator at
. We say that the generalized MPVC Abadie constraint qualification (GMPVC ACQ for short) holds at
if at least one of the dual sets used in the definition of
is nonzero and
.
Remark 3.1. Since
, the GS ACQ implies the GMPVC ACQ.
Following the procedure in this section, we will formulate several extended version of stationary concepts for MPVC in the context of convexificator.
Definition 3.3. A feasible point
of MPVC is called as a generalized weakly stationary point (GW stationary point) if there are vectors
and
such that the following conditions hold true:
(3.1)
(3.2)
(3.3)
Definition 3.4. A feasible point
of MPVC is called as a generalized T stationary point (GT stationary point for short) if there are vectors
and
such that (3.1)-(3.3) and the following conditions hold true:
Definition 3.5. A feasible point
of MPVC is called as a generalized M stationary point (GM stationary point for short) if there are vectors
and
such that (3.1)-(3.3) and the following conditions hold true:
Definition 3.6. A feasible point
of MPVC is called as a generalized S stationary point (GS stationary point for short) if there are vectors
and
such that (3.1)-(3.3) and the following conditions hold true:
Remark 3.2. If all the functions are differentiable, then these notions reduce to the stationary concepts defined in [25]. Directly from the definitions, we get the following relationships between these stationary concepts.
On the other hand,it is obviously that the above stationary concepts include the ones of Karush-Kuhn?C Tucker type which are proposed by Kazemi et al in [21] as a special case.
In the rest of this section, we will focus our attention to the necessary and sufficient optimality conditions for the nonsmooth MPVC under the framework of convexificator. The following theorem is the first main result of this paper. We will see that this result is proved under very weak assumptions. Only the objective function is assumed to be Lipschitz, while the other functions do not satisfy any type of continuity.
Theorem 3.1. Let
be a local optimal solution of MPVC (1.1). Suppose that f is a locally Lipschitz at
which admits a bounded upper semi-regular convexificator
. Assume that GS-ACQ holds at
and the cone
(3.4)
is closed. Then
is a GS stationary point.
Proof. Firstly, we will prove that
(3.5)
Assume that (3.5) does not hold, one has
. In view of
being a bounded upper semi-regular convexificator, we know that
is compact and convex. Since K is a closed convex set, thus utilizing the convex separation theorem, there exists a nonzero vector
and a real number
satisfying
(*)
Notice that
is a cone, this implies that
and
(3.6)
By the definition of upper semi-regular convexificator and (3.6), one gets
. Hence, there is a
such that
(3.7)
On the other hand, using the relationships (*) and
, we obtain
This implies that
(3.8)
This is to say
Taking into account GS-ACQ at
, we obtain
. Thus, there exist the sequences
and
such that
, where N denotes the natural number set. On the other hand, since f is Lipschitz near
with the modulus
, we have for all sufficiently large k,
(3.9)
Combining (3.7) and (3.9), we get for all sufficiently large k,
which contradicts the local optimality of
. Thus, (3.5) is true. This implies that there exist the nonnegative multipliers
,
,
,
,
such that
(3.10)
Let
, we obtain from (3.10),
This shows that
is a GS stationary point and the proof is complete.
Since the constraint functions admitting a bounded upper semi-regular convexificator assure that the set K in (3.4) is closed, we immediately obtain the following corollary of Theorem 3.1.
Corollary 3.1. Let
be a local optimal solution of MPVC (1.1). Suppose that f is a locally Lipschitz function at
. Assume also that f and the constraint functions admit a bounded upper semi-regular convexificator. If the GS-ACQ holds at
, then
is a GS stationary point.
Now, we provide the following example to illustrate Theorem 3.1, this example is a modified version of Example 4.7 in [37].
Example 3.1. Consider the following two-dimension nonsmooth MPVC problem:
Obviously, 0 is the global optimal solution of the above problem and we have
Moreover, we obtain the following bounded upper semi-regular convexificators for these functions
Hence, we get
This implies that the GS-ACQ is satisfied at 0 and K is closed. By taking
, one gets
This shows that the GS-stationarity of 0.
The next result shows that the GM-stationarity is a necessary optimality condition for MPVC if GMPVC ACQ is satisfied at a local optimal solution of MPVC.
Theorem 3.2. Let
be a local optimal solution of MPVC (1.1). Suppose that f is a locally Lipschitz at
, and assume that f and the constraint functions admit a bounded upper semi-regular convexificator. If the GMPVC-ACQ holds at
, then
is a GM stationary point.
Proof. Firstly, we claim that
(3.11)
Suppose that (3.11) does not hold. Since
is compact and convex, and
is closed and convex, similar to the proof of Theorem 3.1, we can find a nonzero vector
and the sequences
and
such that for all sufficiently large k,
which contradicts the local optimality of
. Thus (11) holds true. This implies that there exist the nonnegative multipliers
,
,
,
,
,
such that
(3.12)
Let
, we obtain from (3.12),
This shows that
is a GM stationary point and the proof is complete.
Next, we will show that the GW stationarity is a global or local sufficient optimality condition under certain generalized convexity assumptions.
Theorem 3.3. Let
be a feasible GW stationary point of MPVC (1.1) and define the following index sets:
Assume that f is
pseudoconvex and
,
and
are
quasiconvex at
. Then the following assertions hold true:
(i) If
, then
is a global optimal solution of MPVC.
(ii) If
and
are continuous and
quasiconvex at
, and
, then
is a local optimal solution of MPVC.
(iii)If
and
are continuous and
quasiconvex at
, and
is an interior point relative to the set
, then
is a local optimal solution of MPVC.
Proof. Let
be an arbitrary feasible point of (1.1). Since
for
, by
quasiconvexity of
at
, we get
(3.13)
Similarly, we get
(3.14)
(i) We multiply each inequality in (3.14) by
,
,
, respectively, and adding, we get
Since
, taking into account the GW stationarity of
, one gets
This implies that there exists
such that
. The
pseudoconvexity of f at
shows that
for all
. Hence,
is a global optimal solution of MPVC.
(ii) For any
, since
, the continuity of
implies that
for all feasible points x which is sufficiently close to
. This shows that
for such x. Hence, for x which is sufficiently close to
, one has
Utilizing the
quasiconvexity of
at
, we deduce that for the feasible point x which is sufficiently close to
,
(3.15)
Similarly, one gets, for the feasible point x which is sufficiently close to
,
(3.16)
Similar to the proof of case (i), we can find
such that
. The
pseudoconvexity of f at
shows that
for all feasible point x which is sufficiently close to
. Hence,
is a local optimal solution of MPVC.
(iii) Taking into account that
is an interior point relative to the set
, we know that, for the feasible point x which is sufficiently close to
,
By the
quasiconvexity of the above functions at
, we have
(3.17)
Multiplying (3.13)-(3.17) by
,
,
,
,
, respectively, and adding, we get
This implies that there exists
such that
. The
pseudoconvexity of f at
shows that
for all feasible points x which is sufficiently close to
. Hence,
is a local optimal solution of MPVC.
4. Concluding Remarks
In this paper, under the framework of convexificator, by introducing two generalized MPVC type constraint qualifications and the stationary concepts, we derive the necessary and sufficient optimality conditions for the nonsmooth MPVC using the notion of convexificators. As the future work, some other generalized MPVC type constraint qualifications under the framework of convexificator will be investigated.
Founding
This work was supported in part by NNSF (No. 11461015, 11961011, 11761014) of China and Guangxi Natural Science Foundation (2015GXNSFAA139010, 2016GXNSFFA380009, 2017GXNSFAA198243) and Guangxi Key Laboratory of Automatic Detecting Technology (No. YQ17117).