Skip to main content
main-content

Über dieses Buch

In the early fifties, applied mathematicians, engineers and economists started to pay c10se attention to the optimization problems in which another (lower-Ievel) optimization problem arises as a side constraint. One of the motivating factors was the concept of the Stackelberg solution in game theory, together with its economic applications. Other problems have been encountered in the seventies in natural sciences and engineering. Many of them are of practical importance and have been extensively studied, mainly from the theoretical point of view. Later, applications to mechanics and network design have lead to an extension of the problem formulation: Constraints in form of variation al inequalities and complementarity problems were also admitted. The term "generalized bi level programming problems" was used at first but later, probably in Harker and Pang, 1988, a different terminology was introduced: Mathematical programs with equilibrium constraints, or simply, MPECs. In this book we adhere to MPEC terminology. A large number of papers deals with MPECs but, to our knowledge, there is only one monograph (Luo et al. , 1997). This monograph concentrates on optimality conditions and numerical methods. Our book is oriented similarly, but we focus on those MPECs which can be treated by the implicit programming approach: the equilibrium constraint locally defines a certain implicit function and allows to convert the problem into a mathematical program with a nonsmooth objective.

Inhaltsverzeichnis

Frontmatter

Theory

Frontmatter

1. Introduction

Abstract
The central subject of this book is an optimization problem with a special side constraint. Its definition and some illustrative examples are displayed in Section 1.1. Section 1.2 briefly describes various optimality conditions and numerical methods. Section 1.3 states two simple existence results.
Jiři Outrata, Michal Kočvara, Jochem Zowe

2. Auxiliary Results

Abstract
This chapter collects some nontrivial results which will be needed in the rest of the book. We try to keep the presentation as self-contained as possible.
Jiři Outrata, Michal Kočvara, Jochem Zowe

3. Algorithms of Nonsmooth Optimization

Abstract
In our applications we have to deal with two types of nonsmooth problems: the minimization of a nonsmooth functional f and the solution of nonsmooth equations. This chapter presents in short two basic algorithms which can cope with the difficulty caused by the nondifferentiability. These two codes are working horses in the numerical part of this book.
Jiři Outrata, Michal Kočvara, Jochem Zowe

4. Generalized Equations

Abstract
As we will see later, variational inequalities (and complementarity problems) provide a convenient and elegant tool for characterizing manifold equilibria. The aim of this chapter is to spell out how these models can be brought into the equally useful form of a generalized equation
$$ 0 \in C\left( z \right) + {N_Q}\left( z \right),$$
(4.1)
where C[ℝ k fℝ k ] is a continuous mapping, Q a nonempty, closed, convex subset of ℝk and N Q (z) its normal cone to Q at z; cf. Definition 2.6. Q is called the feasible set of the GE (4.1). Oftentimes, the rewriting as a “nonsmooth equation” is not only possible but very helpful. While proceeding, we also collect several basic results on existence and uniqueness needed in the later chapters. Our objective is to prepare for subsequent analysis and computations.
Jiři Outrata, Michal Kočvara, Jochem Zowe

5. Stability of Solutions to Perturbed Generalized Equations

Abstract
Over the past twenty years a comprehensive theory has been developed on the stability of solutions to perturbed generalized equations, in particular on the Lipschitz behaviour of these solutions. In this chapter we present the part of this theory relevant to our later applications. We assume that the generalized equations from the previous chapter are now subjected to perturbations and we analyse the local behaviour of the associated solution maps S. Basically, we follow Robinson’s work.
Jiři Outrata, Michal Kočvara, Jochem Zowe

6. Derivatives of Solutions to Perturbed Generalized Equations

Abstract
In this chapter we use directional derivatives (Section 6.1) and generalized Jacobians (Section 6.2) to describe the local behaviour of the solution maps S for the perturbed generalized equations from Chapter 5. We restrict ourselves to the case of polyhedral feasible sets and assume further that the strong regularity condition holds. Similarly as in the preceding chapter, we successively analyze the GEs (5.1), (5.24) and (5.41). The transformation of the GEs into the equivalent nonsmooth equations will be a decisive tool in our approach. Further we will prove that under strong regularity the respective selections of the solution maps of the studied GEs are semismooth (Section 6.3). This semismoothness is a crucial prerequisite to apply the numerical methods of Chapter 3.
Jiři Outrata, Michal Kočvara, Jochem Zowe

7. Optimality Conditions and a Solution Method

Abstract
In this chapter we apply the preceding theory to establish first-order necessary optimality conditions and to construct an efficient and robust numerical method for the solution of the considered MPECs. This numerical method will extensively be used in the second (“applied”) part of the book.
Jiři Outrata, Michal Kočvara, Jochem Zowe

Applications

Frontmatter

8. Introduction

Abstract
The idea to use the implicit programming approach in optimum shape design problems is in fact quite old. It was extensively used for solving problems with equilibrium constraints given by variational equations. In this case it is straightforward to plug the unique solution of the equation into the objective function and compute derivatives of such a composite function by means of the implicit-function theorem. If the equilibrium problem is more complicated, e.g., it is a variational inequality, this technique becomes less straightforward. In classic shape optimization, one circumvents the difficulty (switch from equality to inequality) by means of the regularization technique.
Jiři Outrata, Michal Kočvara, Jochem Zowe

9. Membrane with Obstacle

Abstract
We start the application part of the book with a classic example of an elliptic variational inequality—an elastic membrane with an obstacle. First, we describe the state problem and then, in the subsequent sections, three shape optimization problems of graded complexity.
Jiři Outrata, Michal Kočvara, Jochem Zowe

10. Elasticity Problems with Internal Obstacles

Abstract
Although the membrane problems discussed in the previous chapter have practical applications, they are usually considered as only model problems. Truly interesting practical examples arise from modelling of two- and three-dimensional elastic bodies. Their behaviour is again described by elliptic variational equations or inequalities.
Jiři Outrata, Michal Kočvara, Jochem Zowe

11. Contact Problem with Coulomb Friction

Abstract
In the previous two chapters we have introduced problems with obstacles and the problem of linear elasticity. The goal of this chapter is to combine those two and to introduce probably the most important ”nonsmooth“ problem of mechanics: the problem of an elastic body in contact with a rigid obstacle. A simple way how to define this problem is to restrict the normal displacement of certain boundary points in the elasticity problem by means of the unilateral contact constraints known from Chapter 9. This leads to a formulation known as contact problem without friction; in most cases, this formulation does not fully reflect the physical reality. To achieve this, one has to take into account the friction between the body and the obstacle—this friction restricts the tangential component of the displacement on the ”contact boundary“. There are several models of contact problems with friction (cf., e.g., Klarbring, 1986; Lemaitre and Chaboche, 1994). The most realistic one is probably the model of Coulomb friction. In the following sections we will introduce this model, derive its reciprocal (dual) formulation which leads to a quasi-variational inequality and apply the nonsmooth Newton’s method of Chapter 3 to the numerical solution of a suitable discrete approximation. We further show that the discretized problem can be formulated as a linear complementarity problem which, again, can be solved by the nonsmooth Newton’s method. Finally, we formulate a design problem; the control (design) variable is the coefficient of friction (a property of the material) and the goal to maximize the tangential adhesion between the body and the obstacle. This design problem is an MPEC with an LCP as equilibrium constraint.
Jiři Outrata, Michal Kočvara, Jochem Zowe

12. Economic Applications

Abstract
Central to many aspects of economic analysis (and even political theory) is the concept of equilibrium. Similarly as in mechanics, formal characterizations of this concept typically come as complementarity problems or variational inequalities.
Jiři Outrata, Michal Kočvara, Jochem Zowe

Backmatter

Weitere Informationen