A coarse solution of generalized semi-infinite optimization problems via robust analysis of marginal functions and global optimization [Elektronische Ressource] / vorgelegt von Abebe Geletu W. Selassie

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_ilmenau
• Publié le: 01 janvier 2004
• Nombre de lectures: 13
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

ACOARSESOLUTIONOFGENERALIZEDSEMI-INFINITE
OPTIMIZATIONPROBLEMS
VIA
ROBUSTANALYSISOFMARGINALFUNCTIONSAND
GLOBALOPTIMIZATION.
vorgelegt von
Dipl.-Math. Abebe Geletu W. Selassie
DISSERTATION
zur Erlangung des akademischen Grades
Dr. rer. nat.
Eingereicht bei der Technischen Universit¨at Ilmenau
Juni, 2004
Tag der wissenschaftlichen Aussprache: 17.12.2004
1. Gutachter: Prof. Dr. rer. nat. habil. Armin Hoffmann.
2. Gutachter: Prof. Dr. rer. nat. habil. Gerhard-Wilhelm Weber
3. Gutachter: Prof. Dr. rer. nat. habil. Rainer Tichatschke
urn:nbn:de:gbv:ilm1-2004000167March 22, 2005To my wife Genet, and my son Abenezer and my daughter
Bethel whose love, patience and understanding carried me so
far.
March 22, 2005Table of Contents
Table of Contents iv
1 Facts from Set-Valued Analysis 8
1.1 Set-Valued Maps - General Definitions and Properties . . . . . . . . . . . . 9
1.2 Set-Valued Maps with given Structures . . . . . . . . . . . . . . . . . . . . 13
1.2.1 Regularity Conditions and their Consequences . . . . . . . . . . . . 16
1.2.2 Constraint Qualifications and their Consequences . . . . . . . . . . 19
2 A Review of Generalized Semi-infinite Optimization 23
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Structure of the Feasible Set . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1 Global Structure of the Feasible Set . . . . . . . . . . . . . . . . . . 27
2.2.2 Disjunctive Structures in GSIP . . . . . . . . . . . . . . . . . . . . 28
2.3 Convexity Structures in GSIP . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3.1 Convexity of the feasible setM . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Convex Lower Level Problem in a GSIP . . . . . . . . . . . . . . . 33
2.4 First Order Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . 35
2.5 Second Order Optimality Conditions . . . . . . . . . . . . . . . . . . . . . 44
2.5.1 Second Order Optimality with Local Reducibility . . . . . . . . . . 44
2.6 Numerical Solution Methods for GSIP . . . . . . . . . . . . . . . . . . . . 51
2.6.1 GSIP as a Bi-level Optimization Problem . . . . . . . . . . . . . . . 51
2.6.2 Iterative Linear Approximation of a GSIP . . . . . . . . . . . . . . 56
3 Robustness of Set-Valued Maps and Marginal Value Functions 58
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3 Approximatable Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4 Robustness of Set-Valued Maps . . . . . . . . . . . . . . . . . . . . . . . . 67
3.4.1 Definitions and Results . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.4.2 ε−Robustness of set-valued Maps . . . . . . . . . . . . . . . . . . . 69
3.4.3 Further Examples of Robust set-valued Maps . . . . . . . . . . . . 73
3.4.4 Piecewise Semi-continuous set-valued Maps . . . . . . . . . . . . . . 74
3.4.5 Approximatable Set-Valued-maps . . . . . . . . . . . . . . . . . . . 76
3.5 Marginal Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
March 22, 20053.5.1 Upper Robustness of Infimum . . . . . . . . . . . . . . . . . . . . . 78
3.5.2 Upper Robustness of Supremum . . . . . . . . . . . . . . . . . . . . 80
3.5.3 Upper Robustness over a Robust Partition . . . . . . . . . . . . . . 83
3.5.4 Approximatable Marginal Function . . . . . . . . . . . . . . . . . . 84
3.6 Robustness of SV-maps with given structures . . . . . . . . . . . . . . . . 86
3.6.1 The Finite Parametric Case . . . . . . . . . . . . . . . . . . . . . . 86
3.6.2 A Semi-infinite Case . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.6.3 Piecewise Semi-continuity of a SV-map with a Structure . . . . . . 98
3.6.4 Characterization of Robustness through Constraint Qualifications . 101
4 A Coarse Solution of GSIP via a Global Optimization Method 109
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.2 Problem and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.3 Minimizing Sequence and Generalized Minimizers - Definitions . . . . . . . 113
4.4 A Conceptual Penalty Method . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.4.1 Problem of Feasibility . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.4.2 Exact Penalty Approach . . . . . . . . . . . . . . . . . . . . . . . . 118
4.4.3 Coarse Global Optimization Approach . . . . . . . . . . . . . . . . 120
4.4.4 Robustness of the Admissible SetM of GSIP . . . . . . . . . . . . 123
4.4.5 Measurability of Marginal Functions . . . . . . . . . . . . . . . . . 125
4.5 Penalty Methods with Discretization . . . . . . . . . . . . . . . . . . . . . 129
4.5.1 Two Penalty Problems . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.5.2 A Discretization Method . . . . . . . . . . . . . . . . . . . . . . . . 137
4.5.3 Convergence of the discretization method for the penalization ap-
proach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5 Some Remarks on Numerical Experiments 149
Bibliography 166
March 22, 2005Acknowledgment
First and foremost, my greatest indebtedness goes to my academic advisor Prof. Armin
Hoffmann. He has spared none of his time in extending his guidance and counselling - be
it academic or otherwise. Without his constant supervision and encouragement this work
would not have been a reality.
IwouldalsoliketoexpressmydeepestgratitudetoDr. Ru¨digerReinhardandProf. Silvia
Vogel for their profound amicability, sociability and sympathy. In the same vain, I also
express my acknowledgment to Prof. Reinhardt Deumlich (of Addis Abeba University,
Dept. of Mathematics), who is always behind me wherever I go. My thanks are also due
to Dr. Tibor Csendes, for facilitating my stay at the Department of Computer Science,
¨University of Szeged, Hungary, in the summers of 2001 & 2002, through the DAAD-MOB
scholarship.
I also take this opportunity to thank Dr. Axel Wolf, Mr. Hans Mu¨ller, Mrs. Erika Voigt
and several other administrative and academic members of TU-Ilmenau, for their good
will, kindness and for setting me up with a good social and academic atmosphere.
At last, there should always be a means to an end. The means has been graciously pro-
vided to me by DAAD. Thus, my utmost appreciation also goes to the German Academic
ExchangeService(DAAD)forthefinancial, materialandmoralsupportIreceivedforthe
successful completion of my study.
Abebe Geletu.
March 22, 2005List of Symbols
General Symbols and Conventions
N set of the natural numbers
Q set of the rational numbers
R set of the real numbers
nR space of real vectors of dimension n
A,...,Z sets in a topological space
∅ empty set
a,...,z real numbers, vectors
(a ) real number sequences or netsk
a j-th component of a vector a orj
j-th element of a number sequence (a )k
ia i-th vector (of a set of vectors)
mΠ A Cartesian product of the sets A ...Ai 1 mi=1
|x| absolute value of x
kxk the Euclidean norm of x
⊤x the transpose of a vector x
{} set braces
(),{},[] parenthesis for alternative expressions
(a,b), [a,b), [a,b] open, half-open and closed intervals
n≥, >, etc. component wise comparative relations for vectors inR
f :A→B function f from the set A into the set B
−1f inverse of the function f
March 22, 20052
a∈A a belongs to (an element of) the set A
A∪B,A∩B union, intersection of the sets A and B
A\B set A without the elements of set B
int(A) interior of the set A
∂A boundary of the set A
cl(A) the closure of the set A
minA, maxA minimum and maximum element of the set A
infA, supA infimum and supremum of the set A
dist(x,A) distance from the point x to the set A
x→y convergence of x to y, or x tends to y
dom(ϕ) domain of the mapping ϕ
Graph(ϕ) graph of the mapping ϕ
+1 −1M ,M upper and lower inverse of a set-valued map, resp.
∂ϕ sub-differential of the function ϕ
D G(x,y,t) a row (column) vector for the partial derivativex
of a function of several variables w.r.t. x
? end of a proof
Abbreviations
cf. confer (meaning refer, compare or see)
et al. and others
w.r.t. with respect to
e.t.c. and so on
resp. respectivley
l.s.c. lower semi-continuous
u.s.c. upper semi-continuous
l.r. lower robust
u.r. upper robust
l.a. lower approximatable
March 22, 20053
u.a. upper approximatable
SCQ Slater Constraint Qualification
SSC Strong Slater Condition
MFCQ Mangasarian-Fromovitz constraint qualification
EMFCQ Extended Mangasarian-Fromovitz Constraint Qualification
SNH Semi-neighbourhood
SV −map Set-Valued Map
(PSIP),(GSIP),(SIP) parametric, Generalized, semi-infinite optimization problems, resp.
(BL) Bi-level optimization problem
IGOM the Integral Global Optimization Method
Reserved Symbols and Notations
M feasible set of a generalized semi-infinite programming problem
X,Y,T topological spaces
−→M : X Y a set valued map from set X to set Y
M(?) a set valued map
int A relative interior of the set A in the set BB
B the ball of radius ε> 0 and center at 0ε
essinff essential infimum of a function f
h = (h ,..