Nonsmooth Equations in Optimization: Regularity, Calculus, Methods and Applications (Nonconvex Optimization and Its Applications, 60)

✍ Scribed by Diethard Klatte, B. Kummer

• Publisher: Springer
• Year: 2002
• Tongue: English
• Leaves: 362
• Edition: 2002
• Category: Library

✦ Synopsis

Many questions dealing with solvability, stability and solution methods for va- ational inequalities or equilibrium, optimization and complementarity problems lead to the analysis of certain (perturbed) equations. This often requires a - formulation of the initial model being under consideration. Due to the specific of the original problem, the resulting equation is usually either not differ- tiable (even if the data of the original model are smooth), or it does not satisfy the assumptions of the classical implicit function theorem. This phenomenon is the main reason why a considerable analytical inst- ment dealing with generalized equations (i.e., with finding zeros of multivalued mappings) and nonsmooth equations (i.e., the defining functions are not c- tinuously differentiable) has been developed during the last 20 years, and that under very different viewpoints and assumptions. In this theory, the classical hypotheses of convex analysis, in particular, monotonicity and convexity, have been weakened or dropped, and the scope of possible applications seems to be quite large. Briefly, this discipline is often called nonsmooth analysis, sometimes also variational analysis. Our book fits into this discipline, however, our main intention is to develop the analytical theory in close connection with the needs of applications in optimization and related subjects. Main Topics of the Book 1. Extended analysis of Lipschitz functions and their generalized derivatives, including ”Newton maps” and regularity of multivalued mappings. 2. Principle of successive approximation under metric regularity and its - plication to implicit functions.

✦ Table of Contents

Contents
Introduction
List of Results
Basic Notation
1 Basic Concepts
1.1 Formal Settings
1.2 Multifunctions and Derivatives
1.3 Particular Locally Lipschitz Functions and Related Definitions
Generalized Jacobians of Locally Lipschitz Functions
Pseudo-Smoothness and D°f
Piecewise C[sup(1)] Functions
NCP Functions
1.4 Definitions of Regularity
Definitions of Lipschitz Properties
Regularity Definitions
Functions and Multifunctions
1.5 Related Definitions
Types of Semicontinuity
Metric, Pseudo-, Upper Regularity; Openness with Linear Rate
Calmness and Upper Regularity at a Set
1.6 First Motivations
Parametric Global Minimizers
Parametric Local Minimizers
Epi-Convergence
2 Regularity and Consequences
2.1 Upper Regularity at Points and Sets
Characterization by Increasing Functions
Optimality Conditions
Linear Inequality Systems with Variable Matrix
Application to Lagrange Multipliers
Upper Regularity and Newton’s Method
2.2 Pseudo-Regularity
2.2.1 The Family of Inverse Functions
2.2.2 Ekeland Points and Uniform Lower Semicontinuity
2.2.3 Special Multifunctions
2.2.4 Intersection Maps and Extension of MFCQ
3 Characterizations of Regularity by Derivatives
3.1 Strong Regularity and Thibault’s Limit Sets
3.2 Upper Regularity and Contingent Derivatives
3.3 Pseudo-Regularity and Generalized Derivatives
Contingent Derivatives
Coderivatives
Vertical Normals
4 Nonlinear Variations and Implicit Functions
4.1 Successive Approximation and Persistence of Pseudo-Regularity
4.2 Persistence of Upper Regularity
Persistence Based on Kakutani’s Fixed Point Theorem
Persistence Based on Growth Conditions
4.3 Implicit Functions
5 Closed Mappings in Finite Dimension
5.1 Closed Multifunctions in Finite Dimension
5.1.1 Summary of Regularity Conditions via Derivatives
5.1.2 Regularity of the Convex Subdifferential
5.2 Continuous and Locally Lipschitz Functions
5.2.1 Pseudo-Regularity and Exact Penalization
5.2.2 Special Statements for m = n
5.2.3 Continuous Selections of Pseudo-Lipschitz Maps
5.3 Implicit Lipschitz Functions on R[sup(n)]
6 Analysis of Generalized Derivatives
6.1 General Properties for Abstract and Polyhedral Mappings
6.2 Derivatives for Lipschitz Functions in Finite Dimension
6.3 Relations between and Tf and ∂f
6.4 Chain Rules of Equation Type
6.4.1 Chain Rules for Tf and Cf with f ε C[sup(0,1)]
6.4.2 Newton Maps and Semismoothness
6.5 Mean Value Theorems, Taylor Expansion and Quadratic Growth
6.6 Contingent Derivatives of Implicit (Multi–) Functions and Stationary Points
6.6.1 Contingent Derivative of an Implicit (Multi-)Function
6.6.2 Contingent Derivative of a General Stationary Point Map: Topological Assumptions
7 Critical Points and Generalized Kojima–Functions
7.1 Motivation and Definition
KKT Points and Critical Points in Kojima’s Sense
Generalized Kojima–Functions – Definition
7.2 Examples and Canonical Parametrizations
The Subdifferential of a Convex Maximum Function
Complementarity Problems
Generalized Equations
Nash Equilibria
Piecewise Affine Bijections
7.3 Derivatives and Regularity of Generalized Kojima–Functions
Properties of N
Formulas for Generalized Derivatives
Regularity Characterizations by Stability Systems
Geometrical Interpretation
7.4 Discussion of Particular Cases
7.4.1 The Case of Smooth Data
7.4.2 Strong Regularity of Complementarity Problems
7.4.3 Reversed Inequalities
7.5 Pseudo–Regularity versus Strong Regularity
8 Parametric Optimization Problems
8.1 The Basic Model
8.2 Critical Points under Perturbations
8.2.1 Strong Regularity
8.2.2 Local Upper Lipschitz Continuity
8.3 Stationary and Optimal Solutions under Perturbations
8.3.1 Contingent Derivative of the Stationary Point Map
8.3.2 Local Upper Lipschitz Continuity
8.3.3 Upper Regularity
8.3.4 Strongly Regular and Pseudo-Lipschitz Stationary Points
8.4 Taylor Expansion of Critical Values
8.4.1 Marginal Map under Canonical Perturbations
8.4.2 Marginal Map under Nonlinear Perturbations
9 Derivatives and Regularity of Further Nonsmooth Maps
9.1 Generalized Derivatives for Positively Homogeneous Functions
9.2 NCP Functions
9.3 The C-Derivative of the Max-Function Subdifferential
10 Newton’s Method for Lipschitz Equations
10.1 Linear Auxiliary Problems
10.1.1 Dense Subsets and Approximations of M
10.1.2 Particular Settings
10.1.3 Realizations for locPC[sup(1)] and NCP Functions
10.2 The Usual Newton Method for PC[sup(1)] Functions
10.3 Nonlinear Auxiliary Problems
10.3.1 Convergence
10.3.2 Necessity of the Conditions
11 Particular Newton Realizations and Solution Methods
11.1 Perturbed Kojima Systems
Quadratic Penalties
Logarithmic Barriers
11.2 Particular Newton Realizations and SQP-Models
12 Basic Examples and Exercises
12.1 Basic Examples
12.2 Exercises
Appendix
Ekeland’s Variational Principle
Approximation by Directional Derivatives
Proof of TF = T(NM) = NTM + TNM
Constraint Qualifications
Bibliography
Index
A
B
C
D
E
F
G
H
I
K
L
M
N
O
P
Q
R
S
T
U
V
W
Z