Mathematical programs with vanishing constraints [Elektronische Ressource] / vorgelegt von Tim Hoheisel

Sujets

• Mathematics

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2009
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Mathematical Programs
with
Vanishing Constraints
Tim Hoheisel
Dissertation
Department of Mathematics
University of Wu¨rzburgMathematical Programs
with
Vanishing Constraints
Dissertation zur Erlangung
des naturwissenschaftlichen Doktorgrades
der Julius-Maximilians-Universita¨t Wu¨rzburg
vorgelegt von
TIM HOHEISEL
aus
Northeim
Eingereicht am: 23. Juli 2009
1. Gutachter: Prof. Dr. Christian Kanzow, Universita¨t Wu¨rzburg
2. Gutachter: Prof. Dr. Wolfgang Achtziger, Technische Universita¨t Dortmund“... And out of the confusion
Where the river meets the sea
Something new would arrive
Something better would arrive...”
(G.M. Sumner)Acknowledgements
The doctoral thesis at hand is the result of my research during the time as a Ph.D. student at the
Department of Mathematics at the University of Wu¨rzburg. In a long-term project like this one,
there are, of course, several ups and downs, and hence one is lucky to have a solid scientific and
social environment. Therefore, I would like to take this opportunity to thank certain people who
have helped me create this dissertation, directly or indirectly.
First of all, I would like to express my deep gratitude to my supervisor Christian Kanzow for his
superb scientific guidance through the past three years. He provided me with a very interesting
and challenging research project, generously sharing his time and discussing new ideas. Moreover,
I could substantially benefit from his great experience in the field of mathematical optimization
which guided me carefully on the path which eventually led to this thesis. In addition to that,
I would like to thank him for several joint publications which, clearly, had a big impact on the
material presented here. Furthermore, through him, I got to know and collaborate with a cou-
ple of prominent researchers in my field of work like, for example, Jirˇ´ı V. Outrata and Wolfgang
Achtziger, where the latter also deserves my appreciation for agreeing to co-referee this disserta-
tion.
Apart from my supervisor there are some more persons to whom I owe my gratitude since this
whole project could hardly have been realized this way if it had not been for their support.
At this, first, I would like to thank my colleague Florian Mo¨ller for helping me with all kinds of
technical questions, very amusing discussions about strength training and, after all, for being a
really nice guy.
A very special thanks goes to my closest friends: Cedric Essi, Christian Struck, and Neela Struck
to whom I feel deeply indebted for caring through all the lows and also sharing the highs.
Last but not least, I would like to thank my parents for generous financial support during my
studies and my whole family (also including my sister Imke) for unrestrained emotional backup.
vContents
1. Introduction 1
1.1. Applications of MPVCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Comparison with MPECs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
I. Theoretical Results 10
2. Concepts and results from nonlinear programming 11
2.1. KKT conditions and constraint qualifications . . . . . . . . . . . . . . . . . . . 11
2.1.1. The Karush-Kuhn-Tucker conditions . . . . . . . . . . . . . . . . . . . 11
2.1.2. Constraint qualifications . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.3. B-stationarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2. The convex case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3. Second-order optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . 16
3. Tools for MPVC analysis 19
3.1. Some MPVC-derived problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2. Representations of the standard cones and the MPVC-linearized cone . . . . . . 21
4. Standard CQs in the context of MPVCs 24
4.1. Violation of LICQ and MFCQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2. Necessary conditions for ACQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3. Sufficient conditions for GCQ . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5. MPVC-tailored constraint qualifications 30
5.1. MPVC-counterparts of standard CQs . . . . . . . . . . . . . . . . . . . . . . . . 30
5.2. More MPVC-tailored constraint qualifications . . . . . . . . . . . . . . . . . . . 35
6. First-order optimality conditions for MPVCs 39
6.1. First-order necessary optimality conditions . . . . . . . . . . . . . . . . . . . . . 39
6.1.1. Strong stationarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
6.1.2. M-stationarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6.1.3. Weak stationarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.2. A first-order sufficient optimality condition . . . . . . . . . . . . . . . . . . . . 47
viContents
7. Second-order optimality conditions for MPVCs 53
7.1. A second-order necessary condition . . . . . . . . . . . . . . . . . . . . . . . . 54
7.2. A second-order sufficient condition . . . . . . . . . . . . . . . . . . . . . . . . . 58
8. An exact penalty result for MPVCs 61
8.1. The concept of exact penalization . . . . . . . . . . . . . . . . . . . . . . . . . 61
8.2. A generalized mathematical program . . . . . . . . . . . . . . . . . . . . . . . . 61
8.3. Deriving an exact penalty function for MPVCs . . . . . . . . . . . . . . . . . . 64
8.4. The limiting subdifferential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
8.5. An alternative proof for M-stationarity . . . . . . . . . . . . . . . . . . . . . . . 68
II. Numerical Approaches 72
9. A smoothing-regularization approach 73
9.1. Clarke’s generalized gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
9.2. Reformulation of the vanishing constraints . . . . . . . . . . . . . . . . . . . . . 74
9.3. A smoothing-regularization approach to the reformulated problem . . . . . . . . 78
9.4. Convergence results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9.5. Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
9.5.1. Academic example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.5.2. Examples in truss topology optimization . . . . . . . . . . . . . . . . . . 94
10. A relaxation approach 103
10.1. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
10.2. Convergence Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
Final remarks 117
Abbreviations 118
Notation 119
vii1. Introduction
From the ancient roots of mathematics to the latest streams of modern mathematical research,
there has always been a fruitful interplay between pure mathematical theory on the one hand and
the large field of applications in physics, chemistry, biology, engineering, or economics on the
other. At this, all kinds of mutual influences can be observed. In many cases it happens naturally
that an applicational problem leads to the genesis of a whole new discpline within mathematics;
calculus or algebra are very prominent examples of that. In turn, the converse direction, in which
a whole theory has been established without an immediate benefit outside of mathematics, finding
enormous practical application decades later, is observed just as well.
Under the label of applied mathematics all mathematical disciplines are subsumed, which are
concerned with the theoretical background and the computational solution of problems from all
fields of applications and constantly recurring inner mathematical tasks.
In particular, the disciplines of mathematical optimization and nonlinear programming, respec-
tively, being subdis ciplines of applied mathematics, deal with various kinds of minimization (or
maximization) tasks, in which an objective function has to be minimized subject to functional or
abstract constraints, from the most general to very special cases. In this thesis, however, a spe-
cial class of optimization problems which can be used as a unified framework for problems from
topology optimization, cf. Section 1.1, is investigated in depth. For these purposes consider the
optimization problem
min f (x)
s.t. g (x)≤ 0 ∀i= 1,..., m,i
h (x)= 0 ∀ j= 1,..., p, (1.1)j
H (x)≥ 0 ∀i= 1,..., l,i
G (x)H (x)≤ 0 ∀i= 1,..., l,i i
nwith continuously differentiable functions f, g, h , G, H : R → R. This type of problem isi j i i
called mathematical program with vanishing constraints, MPVC for short. On the one hand, this
terminology is due to the fact that the implicit sign constraint G (x) ≤ 0 vanishes as soon asi
H (x)= 0. On the other hand, an MPVC is closely related to another type of optimization problemi
called mathematical program with equilibrium constraints, MPEC for short, see Section 1.2 for
further details. In problem (1.1) the constraints g(x)≤ 0 and h(x)= 0 are supposed to be standard
constraints, whereas the characteristic constraints H (x)≥ 0 and G (x)H (x)≤ 0 for i = 1,..., li i i
are troublesome for reasons broadly explained in the sequel.
An MPVC is a very interesting type of problem for various reasons. First of all, it has a large field
of applications in truss topology design, see Section 1.1