Equilibrium constrained optimization problems

https://doi.org/10.1016/j.ejor.2004.07.075Get rights and content

Abstract

We consider equilibrium constrained optimization problems, which have a general formulation that encompasses well-known models such as mathematical programs with equilibrium constraints, bilevel programs, and generalized semi-infinite programming problems. Based on the celebrated KKM lemma, we prove the existence of feasible points for the equilibrium constraints. Moreover, we analyze the topological and analytical structure of the feasible set. Alternative formulations of an equilibrium constrained optimization problem (ECOP) that are suitable for numerical purposes are also given. As an important first step for developing efficient algorithms, we provide a genericity analysis for the feasible set of a particular ECOP, for which all the functions are assumed to be linear.

Introduction

An equilibrium constrained optimization problem (ECOP) is a mathematical program, for which an embedded set of constraints is used to model the equilibrium conditions in various applications. This equilibrium concept corresponds to a desired state such as the optimality conditions for the inner problem of a bilevel optimization model, or the Nash equilibrium of a game played by rational players. For an introduction to ECOP we refer to [14], [15]. Applications of ECOP appear not only in economics (Cournot oligopoly, Stackelberg games, generalized Nash equilibrium) but also in optimum design problems in mechanics (contact problems with friction, elasticity problems with obstacles, etc., see [15]).

This paper is concerned with the analysis of some structural properties of an ECOP. In order to pursue this analysis, we frequently use standard terms from generalized convexity and set valued analysis. For an unfamiliar reader, we have added Appendix A that reviews the definitions of these terms.

Let f:Rn+mR, ϕ:Rn+2mR be real valued functions and K:RnRm a set valued mapping with closed values. A general form of an ECOP is now given byminx,yf(x,y)s.t.(x,y)Z,yK(x),ϕ(x,y,v)0,vK(x),where xRn, y,vRm and the set ZRn+m is a closed nonempty set. The constraintsϕ(x,y,v)0,vK(x),depending on the parameter x and y, are called the parametric equilibrium constraints. For notational convenience, we now introduce the so-called graph(K) (see [2]) of the set valued mapping K given bygraph(K):={(x,y)Rn+m:yK(x)}and the set ERn+m defined byE:={(x,y)Rn+m:ϕ(x,y,v)0,vK(x)}.

This notation allows us to denote the feasible set of (1.1) byF:=ZEgraph(K).Hence, we can rewrite the ECOP as follows:minx,yf(x,y)s.t.(x,y)F.

A frequently used instance of (1.2) arises when for every x the set K(x) is closed, convex, and the function ϕ is given byϕ(x,y,v):=v-y,F(x,y).

The parametric equilibrium constraints (1.2) associated with the function ϕ in (1.5) and the closed convex set K(x), are called the (parametric) Stampacchia variational inequalities. Moreover, it is well-known (see [9]) that if the function yF(x,y) in (1.5) is pseudomonotone (see Definition A.1), then the function ϕ can be replaced byϕ(x,y,v):=v-y,F(x,v).

Accordingly, the parametric equilibrium constraints defined by the function ϕ in (1.6) are known as the (parametric) Minty variational inequalities. Notice that in the literature an ECOP is called a mathematical program with equilibrium constraints (MPEC) when ϕ has the form (1.5). In this paper we have chosen the more general form (1.2) so that in addition to MPECs, our model also includes bilevel programs and semi-infinite problems.

In Section 2 of this paper, we investigate under which sufficient conditions on the set valued mapping K and the function ϕ, the set Egraph(K) is nonempty. In Section 3, we then study under which conditions on K and ϕ, the set Egraph(K) is closed and convex. In Section 4, we derive different formulations of an ECOP as a nonlinear programming problem. We are especially interested in formulations, which are suitable for numerical purposes. Finally, in Section 5 we give a genericity analysis for the structure of the feasible set of a linear ECOP (where all the problem functions are linear). This genericity analysis constitutes the first step towards developing efficient algorithms.

Section snippets

Existence of feasible solutions

In this section, we are interested in some sufficient conditions, which guarantee that the equilibrium constraints defining the set Egraph(K), allow feasible points. By the definition of the sets E and graph(K), it is clear that Egraph(K) if and only if there exists some xRn such thatV(ϕ,K(x)):={yK(x):ϕ(x,y,v)0,vK(x)}.From now on, we fix x arbitrarily, define CRm by C:=K(x) and ϕx:R2mR by ϕx(y,v):=ϕ(x,y,v), and assume that C is nonempty and convex. Recall that by our general

Structure of the feasible set

Recall from (1.3) that the feasible set of an ECOP is given byF=ZEgraph(K).In this section, we analyze the topological structure of F in order to state some conditions under which the intersection Egraph(K) is closed and convex. We start with stating the conditions for closedness.

Lemma 3

If the set valued mapping K is closed (see Definition A.6) and lower semicontinuous (see Definition A.8), and the function ϕ is upper semicontinuous, then the set Egraph(K) is closed.

Proof

Since the set graph(K) is

Formulation of an ECOP as a nonlinear program

In this section, we are interested in reformulations of ECOP, which are suitable for the numerical solution of the problems. We transform an ECOP to a problem with bilevel structure and obtain a formulation of the program as a nonlinear problem with complementarity constraints.

To deal with the equilibrium constraints (1.2) of ECOP, consider the optimization problem(Q(x,y))minvϕ(x,y,v)s.t.vK(x),depending on the parameter (x,y). Obviously (assuming that Q(x,y) is solvable), for a solution v=v(x,y

The generic structure of linear ECOP

In the present section, we reconsider the (linear) ECOP of the form LECOP. We are going to analyze the structure of LECOP from a generic point of view (structure in the general case). In [20], a genericity analysis was done for the linear bilevel problems LBL, which corresponds to the case [C1C2]=0 (see Remark 1). Since both problems LBL and LECOP have a similar structure, the genericity analysis for LECOP can be performed with similar techniques. We therefore present the results here in a

Conclusion

This paper studies a form of an equilibrium constrained optimization problem (ECOP) which contains bilevel programs (BL) and generalized semi-infinite problems (GSIP) as special instances. The relation and differences between these three types of problems is analyzed. Based on the KKM lemma, under certain convexity assumptions, the existence of feasible points can be proven. For a special linear ECOP a full genericity analysis is given which constitutes the basis for efficient algorithms to

References (25)

  • M. Aigner et al.

    Proofs from the Book

    (1999)
  • J.B. Aubin et al.

    Set Valued Analysis

    (1990)
  • M. Avriel et al.

    Generalized Concavity: Mathematical Concepts and Methods in Science and Engineering

    (1988)
  • J.F. Bard

    Practical Bilevel Optimization

    (1998)
  • R. Engelking

    Outline of General Topology

    (1968)
  • C.G. Gibson et al.

    Topological Stability of Smooth Mappings

    (1976)
  • J. Han et al.

    Solvability of variational inequality problems

    Journal of Optimization Theory and Applications

    (2004)
  • P.T. Harker et al.

    Finite-dimensional variational inequality and nonlinear complementarity problems: A survery of theory, algorithm, and applications

    Mathematical Programming

    (1990)
  • R. John

    Variational inequalities and pseudomonotone functions

  • R. John

    A note on Minty variational inequalities and generalized monotonicity

  • H.Th. Jongen et al.

    Nonlinear Optimization in Finite Dimensions

    (2000)
  • S. Karamardian

    The complementarity problem

    Mathematical Programming

    (1972)
  • Cited by (0)

    View full text