Equilibrium constrained optimization problems
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 , be real valued functions and a set valued mapping with closed values. A general form of an ECOP is now given bywhere , and the set is a closed nonempty set. The constraintsdepending on the parameter x and y, are called the parametric equilibrium constraints. For notational convenience, we now introduce the so-called (see [2]) of the set valued mapping K given byand the set defined by
This notation allows us to denote the feasible set of (1.1) byHence, we can rewrite the ECOP as follows:
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
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 in (1.5) is pseudomonotone (see Definition A.1), then the function ϕ can be replaced by
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 is nonempty. In Section 3, we then study under which conditions on K and ϕ, the set 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 , allow feasible points. By the definition of the sets E and graph(K), it is clear that if and only if there exists some such thatFrom now on, we fix x arbitrarily, define by and by , 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 byIn this section, we analyze the topological structure of in order to state some conditions under which the intersection 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 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 problemdepending on the parameter . Obviously (assuming that is solvable), for a solution
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 (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)
- et al.
Proofs from the Book
(1999) - et al.
Set Valued Analysis
(1990) - et al.
Generalized Concavity: Mathematical Concepts and Methods in Science and Engineering
(1988) Practical Bilevel Optimization
(1998)Outline of General Topology
(1968)- et al.
Topological Stability of Smooth Mappings
(1976) - et al.
Solvability of variational inequality problems
Journal of Optimization Theory and Applications
(2004) - et al.
Finite-dimensional variational inequality and nonlinear complementarity problems: A survery of theory, algorithm, and applications
Mathematical Programming
(1990) Variational inequalities and pseudomonotone functions
A note on Minty variational inequalities and generalized monotonicity