Necessary and sufficient conditions for nonsmooth mathematical programs with equilibrium constraints

https://doi.org/10.1016/j.na.2009.11.015Get rights and content

Abstract

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Then, we derive a necessary optimality result for nonsmooth MPEC on any Asplund space. Also, under generalized convexity assumptions, we establish sufficient optimality conditions for this program in Banach spaces.

Introduction

In this paper we investigate necessary and sufficient optimality conditions for the following program, known across the literature as a mathematical program with equilibrium constraints, MPEC for short: (MPEC)minf(z)s.tg(z)0,h(z)=0,G(z)0,H(z)0,G(z),H(z)=0, where X is a Banach space, f:XR is a lower semi-continuous (lsc in brief) function, g:XRm, h:XRp, G:XRl and H:XRl are functions with lsc components. The MPEC has been receiving an increasing attention in the mathematical programming in recent years. The reader is referred to [1], [2] for applications and recent developments in theories and algorithms.

It is well known that, even with smooth data, most of the standard constraint qualifications cannot be satisfied for such a problem. As a result, new constraint qualifications have been tailored to MPECs, and also, new stationarity concepts have arisen; see, e.g., [3], [4], [5], [6], [7], [8].

Among these new stationarity notions, an important role is played by a concept associated with the generalized calculus of the Mordukhovich so called M-stationarity, [3], [7], [9], [10], [8], [11]. The most valuable property of this notion is that it requires only very weak constraint qualifications.

Ye in [8] showed that the M-stationary is a first order necessary optimality condition for smooth MPEC. Moreover, she proposed some constraint qualifications for M-stationarity to hold. Later, Flegel and Kanzow [6] proved that M-stationary holds under an MPEC variant of calmness for the case where all the functions involved except the objective function are smooth. The Mordukhovich subdifferential was used for nonsmooth terms in [6].

In [7], we introduced a nonsmooth type of M-stationary via Michel–Penot subdifferential and showed that it is a necessary condition for MPEC without requiring any smoothness assumptions. It is worth noting that in all of the references cited above the whole theory took place in a finite-dimensional area. In [12] attempts were made to derive necessary and sufficient conditions for quasiconvex differentiable MPEC with locally starshaped region in Banach spaces. Despite the differentiability and generalized convexity for the functions involved (even for necessary conditions), the MPEC results were still obtained in finite-dimensional spaces.

In this paper we extend the M-stationary notion to nonsmooth MPEC (1) in terms of the Clarke–Rockafellar subdifferential. Then, we derive new necessary and sufficient optimality conditions based on our nonsmooth MPEC M-stationary.

Our new necessary optimality result is derived by means of a general mathematical program which embeds MPEC (1). We show that M-stationary is a necessary optimality condition under an appropriate variant of the Mangasarian–Fromovitz constraint qualification. This constraint qualification has been applied in [12] to draw an M-stationary necessary condition for smooth quasiconvex MPEC in finite-dimensional setting. In this paper we obtain a similar necessary result in Asplund spaces without using any smoothness or convexity assumptions.

Convexity plays an important role in many aspects of the mathematical programming including sufficient optimality conditions. In general, MPEC is a nonconvex problem even when all of the constraint functions are affine. Hence, the necessary condition is not sufficient for optimality. Ye in [8] applied (smooth) generalized convexity conditions to prove that M-stationary is a sufficient condition for optimality. Other sufficient optimality conditions for (smooth) quasiconvex MPEC are due to Aussel and Ye [12].

Various generalizations of convexity have been made in the literature and various properties of generalized convex functions have been given; see e.g. [13], [14], [15], [16]. The notion of quasiconvexity is one of the most classical concepts in generalized convexity. Some characterizations for lsc quasiconvex functions were given in [13], [14], [15], [17]. Another important notion of generalized convexity is pseudoconvexity, which its usual definition presupposes differentiability of the involved function.

In this paper we consider a generalization of pseudoconvexity corresponding to Clarke–Rockafellar subdifferential. Subdifferential characterizations of (Clarke-)pseudoconvex functions have been investigated in several papers. For example, one can refer to [18] for locally Lipschitz functions on Banach spaces. Poliquin in [19] considered this topic for lsc functions on finite-dimensional spaces. Other results were provided by Correa–Gajardo–Thibault for lsc functions on reflexive Banach spaces [20] and on arbitrary Banach spaces [21]. We investigate certain sufficient conditions for pseudoconvexity. The key idea is to deal with some more natural conditions of a pseudoconvex function rather than applying its subdifferential. The result appears to be almost simple in practice.

The major goal of this paper is to provide sufficient optimality conditions for nonsmooth lsc MPEC on Banach spaces.

The organization of the paper is as follows. Section 2 is devoted to some preliminary results including important definitions and some initial observations. In Section 3 a necessary optimality condition is given for nonsmooth locally Lipschitz MPEC defined on Asplund spaces. Then, in Section 4 we derive some properties and characterizations of nonsmooth lsc pseudoconvex functions. Finally, in Section 5 we apply the results of Section 4 to derive sufficient optimality conditions for nonsmooth lsc MPEC in Banach spaces.

Our notation is basically standard; cf. [22]. Given a set δ{1,,n} we denote by xδR|δ| the vector consisting of those components of xi corresponding to the indices in δ. Recall that the symbol Lim supxx̄F(x){xX| sequences xkx̄ and xkwxwith xkF(xk) for all kN} stands for the sequential Painlevé–Kuratowski upper/outer limit of a set-valued mapping F:XX in the norm topology of X and weak topology of X, where N{1,2,}.

Section snippets

Preliminaries

In this section we define some basic constructions and properties from variational analysis and generalized differentiation needed in what follows.

A Banach space X is Asplund, or it has the Asplund property, if every convex continuous function ϕ:UR defined on an open convex subset U of X is Fréchet differentiable on a dense subset of U. This class includes all Banach spaces having Fréchet smooth bump functions (in particular, spaces with Fréchet smooth renorms, hence, every reflexive space);

Necessary optimality condition for the nonsmooth MPEC

In this section we prove a necessary optimality result for MPEC (1) involving locally Lipschitz functions. The program (1) can be written in several reformulations. Here we introduce a particular one which is more practical in nonsmooth and infinite-dimensional setting.

Consider a local minimizer z of (1). From complementarity term in (1), it is clear that either Gi(z), or Hi(z), or both of them must be zero. To distinguish among these cases, we divide the indices of G and H into three sets: α

Nonsmooth quasiconvex and pseudoconvex functions

In this section we investigate some properties of lsc quasiconvex functions which will be used in what follows. Also, we obtain some practical conditions insuring pseudoconvexity of a function without computing its subdifferential. Note that from now on, the space X in question is supposed to be Banach unless otherwise stated.

The function f:XR{+} is said to be quasiconvex if f(z)max{f(x),f(y)},x,yX,z(x,y), where (x,y)={x+t(yx)|t(0,1)}. Also, f is said to be pseudoconvex if xcf(x):

Sufficient optimality conditions for the nonsmooth MPEC

In this section we apply the results of Section 4 to prove sufficient optimality conditions for MPEC involving lsc functions.

Let us start with dividing the constraint index sets as the following: J+={i:λih>0},J={i:λih<0},Ig={i:gi(z)=0},β+={iβ:λiG>0,λiH>0},βG+={iβ:λiG=0,λiH>0},βG={iβ:λiG=0,λiH<0},βH+={iβ:λiG>0,λiH=0},βH={iβ:λiG<0,λiH=0},α+={iα:λiG>0},α={iα:λiG<0},γ+={iγ:λiH>0},γ={iγ:λiH<0}. Now, we are ready to state sufficient conditions for MPEC.

Theorem 5.1

Let z be an M-stationary point

References (26)

  • J.V. Outrata

    A generalized mathematical program with equilibrium constraints

    SIAM J. Control Optim.

    (2000)
  • J.V. Outrata

    Optimality conditions for a class of mathematical programs with equilibrium constraints

    Math. Oper. Res.

    (1999)
  • J.J. Ye

    Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints

    SIAM J. Optim.

    (2000)
  • Cited by (31)

    View all citing articles on Scopus
    View full text