📉Variational Analysis Unit 6 – Set-Valued Analysis & Multifunctions

Key Concepts and Definitions

• Set-valued analysis studies mathematical objects that take values as sets rather than single elements
• Multifunctions, also known as set-valued mappings, are functions that map elements of one set to subsets of another set
• The graph of a multifunction $F:X \rightrightarrows Y$ is the set $\{(x,y) \in X \times Y : y \in F(x)\}$
• The domain of a multifunction $F:X \rightrightarrows Y$ is the set $\{x \in X : F(x) \neq \emptyset\}$
• The range of a multifunction $F:X \rightrightarrows Y$ is the set $\{y \in Y : \exists x \in X, y \in F(x)\}$
• The inverse of a multifunction $F:X \rightrightarrows Y$ is the multifunction $F^{-1}:Y \rightrightarrows X$ defined by $F^{-1}(y) = \{x \in X : y \in F(x)\}$
• Continuity concepts for multifunctions include lower semicontinuity, upper semicontinuity, and continuity

Set Theory Foundations

• Set-valued analysis builds upon fundamental concepts from set theory, such as sets, subsets, unions, intersections, and Cartesian products
• The power set of a set $X$, denoted by $\mathcal{P}(X)$, is the set of all subsets of $X$
  • For example, if $X = \{1, 2, 3\}$, then $\mathcal{P}(X) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$
• The Cartesian product of two sets $X$ and $Y$, denoted by $X \times Y$, is the set of all ordered pairs $(x, y)$ where $x \in X$ and $y \in Y$
• The graph of a function $f:X \to Y$ is a subset of the Cartesian product $X \times Y$
• Set-valued analysis extends these concepts to study functions that map elements to sets rather than single elements
• The Minkowski sum of two sets $A$ and $B$ in a vector space is defined as $A + B = \{a + b : a \in A, b \in B\}$
• The Hausdorff distance between two non-empty compact sets $A$ and $B$ in a metric space $(X, d)$ is defined as $d_H(A, B) = \max\{\sup_{a \in A} \inf_{b \in B} d(a, b), \sup_{b \in B} \inf_{a \in A} d(a, b)\}$

Introduction to Multifunctions

• Multifunctions generalize the concept of single-valued functions by allowing elements to be mapped to sets rather than single elements
• A multifunction $F:X \rightrightarrows Y$ assigns to each element $x \in X$ a subset $F(x) \subseteq Y$
  • For example, let $X = \{1, 2, 3\}$ and $Y = \{a, b, c\}$. A multifunction $F:X \rightrightarrows Y$ could be defined as $F(1) = \{a, b\}, F(2) = \{b, c\}, F(3) = \{a, c\}$
• Multifunctions can be used to model various phenomena in optimization, control theory, and economics
• The graph of a multifunction provides a useful representation for studying its properties
• Operations on multifunctions include composition, inversion, and pointwise set operations (union, intersection, etc.)
• Multifunctions can be classified based on properties such as convexity, closedness, and boundedness of their graph or values

Properties of Multifunctions

• Continuity properties of multifunctions are crucial for understanding their behavior and deriving useful results
• A multifunction $F:X \rightrightarrows Y$ is lower semicontinuous at $x_0 \in X$ if for any open set $V \subseteq Y$ with $F(x_0) \cap V \neq \emptyset$, there exists a neighborhood $U$ of $x_0$ such that $F(x) \cap V \neq \emptyset$ for all $x \in U$
• A multifunction $F:X \rightrightarrows Y$ is upper semicontinuous at $x_0 \in X$ if for any open set $V \subseteq Y$ with $F(x_0) \subseteq V$, there exists a neighborhood $U$ of $x_0$ such that $F(x) \subseteq V$ for all $x \in U$
  • Intuitively, lower semicontinuity ensures that the values of $F$ do not suddenly "shrink" around $x_0$, while upper semicontinuity ensures that the values of $F$ do not suddenly "expand" around $x_0$
• A multifunction is continuous if it is both lower and upper semicontinuous
• Convexity properties of multifunctions are important in optimization and variational analysis
  • A multifunction $F:X \rightrightarrows Y$ is convex-valued if $F(x)$ is a convex set for all $x \in X$
  • A multifunction $F:X \rightrightarrows Y$ has a convex graph if its graph is a convex set in $X \times Y$
• Closedness properties of multifunctions are related to the topological structure of their graph or values
  • A multifunction $F:X \rightrightarrows Y$ is closed-valued if $F(x)$ is a closed set for all $x \in X$
  • A multifunction $F:X \rightrightarrows Y$ has a closed graph if its graph is a closed set in $X \times Y$

Continuity and Semicontinuity

• Continuity and semicontinuity are fundamental properties in the study of multifunctions and set-valued analysis
• Lower semicontinuity captures the idea that the values of a multifunction do not suddenly "shrink" at a point
  • A multifunction $F:X \rightrightarrows Y$ is lower semicontinuous at $x_0 \in X$ if for any $y_0 \in F(x_0)$ and any neighborhood $V$ of $y_0$, there exists a neighborhood $U$ of $x_0$ such that $F(x) \cap V \neq \emptyset$ for all $x \in U$
• Upper semicontinuity captures the idea that the values of a multifunction do not suddenly "expand" at a point
  • A multifunction $F:X \rightrightarrows Y$ is upper semicontinuous at $x_0 \in X$ if for any open set $V \subseteq Y$ with $F(x_0) \subseteq V$, there exists a neighborhood $U$ of $x_0$ such that $F(x) \subseteq V$ for all $x \in U$
• Continuity for multifunctions requires both lower and upper semicontinuity
  • A multifunction is continuous if it is both lower semicontinuous and upper semicontinuous at every point in its domain
• Semicontinuity and continuity can be characterized using sequences and the graph of the multifunction
  • A multifunction $F:X \rightrightarrows Y$ is lower semicontinuous at $x_0 \in X$ if and only if for any sequence $\{x_n\}$ converging to $x_0$ and any $y_0 \in F(x_0)$, there exists a sequence $\{y_n\}$ converging to $y_0$ such that $y_n \in F(x_n)$ for all $n$
  • A multifunction $F:X \rightrightarrows Y$ is upper semicontinuous at $x_0 \in X$ if and only if for any sequence $\{x_n\}$ converging to $x_0$ and any sequence $\{y_n\}$ with $y_n \in F(x_n)$, there exists a subsequence of $\{y_n\}$ converging to some $y_0 \in F(x_0)$
• Semicontinuity and continuity are preserved under various operations on multifunctions, such as composition and inversion

Fixed Point Theorems

• Fixed point theorems are powerful tools in set-valued analysis and have numerous applications in optimization, game theory, and economics
• A fixed point of a multifunction $F:X \rightrightarrows X$ is an element $x \in X$ such that $x \in F(x)$
• The Kakutani fixed point theorem is a generalization of the Brouwer fixed point theorem for multifunctions
  • It states that if $K$ is a non-empty, compact, and convex subset of a Euclidean space and $F:K \rightrightarrows K$ is an upper semicontinuous multifunction with non-empty, closed, and convex values, then $F$ has a fixed point
• The Nadler fixed point theorem is an extension of the Banach contraction principle for multifunctions
  • It states that if $(X, d)$ is a complete metric space and $F:X \rightrightarrows X$ is a contraction multifunction (i.e., there exists $\alpha \in [0, 1)$ such that $d_H(F(x), F(y)) \leq \alpha d(x, y)$ for all $x, y \in X$), then $F$ has a fixed point
• Other important fixed point theorems for multifunctions include the Bohnenblust-Karlin fixed point theorem and the Himmelberg fixed point theorem
• Fixed point theorems for multifunctions have been used to prove the existence of equilibria in game theory and economics, as well as to study the stability of dynamical systems

Applications in Optimization

• Set-valued analysis and multifunctions have numerous applications in optimization theory and practice
• Multifunctions can be used to model constraints, objectives, and solution mappings in optimization problems
  • For example, the feasible set of an optimization problem can be represented as a multifunction that maps the decision variables to the set of feasible solutions
• Generalized equations, which involve multifunctions, provide a unified framework for studying optimality conditions and variational inequalities
  • A generalized equation is a problem of the form $0 \in F(x)$, where $F:X \rightrightarrows Y$ is a multifunction
  • Optimality conditions for various classes of optimization problems can be formulated as generalized equations
• Set-valued optimization extends classical optimization theory by considering set-valued objectives and constraints
  • In set-valued optimization, the goal is to find efficient or minimal elements with respect to a partial order on sets (e.g., the Pareto order)
• Variational inequalities, which involve multifunctions, are closely related to optimization problems and have applications in economics, game theory, and mechanics
  • A variational inequality problem is to find $x^* \in K$ such that $\langle F(x^*), x - x^*\rangle \geq 0$ for all $x \in K$, where $K$ is a non-empty, closed, and convex subset of a Hilbert space and $F:K \rightrightarrows K$ is a multifunction
• Subdifferential calculus, which involves set-valued mappings, is a powerful tool for studying nonsmooth optimization problems
  • The subdifferential of a nonsmooth function at a point is a set-valued mapping that generalizes the concept of the gradient for smooth functions

Advanced Topics and Current Research

• Set-valued analysis and multifunctions continue to be active areas of research with numerous advanced topics and open problems
• Equilibrium problems, which generalize optimization problems and variational inequalities, involve finding fixed points of multifunctions
  • An equilibrium problem is to find $x^* \in K$ such that $f(x^*, y) \geq 0$ for all $y \in K$, where $K$ is a non-empty, closed, and convex subset of a Hilbert space and $f:K \times K \to \mathbb{R}$ is an equilibrium bifunction
• Set-valued differential equations and inclusions extend the theory of ordinary differential equations to multifunctions
  • A set-valued differential equation is a problem of the form $\dot{x}(t) \in F(t, x(t))$, where $F:[0, T] \times \mathbb{R}^n \rightrightarrows \mathbb{R}^n$ is a multifunction
  • Set-valued differential equations have applications in control theory, robotics, and economics
• Viability theory studies the evolution of systems subject to state constraints using set-valued analysis and multifunctions
  • The viability kernel of a set $K$ with respect to a multifunction $F$ is the largest subset of $K$ such that for any initial condition in this subset, there exists a solution to the set-valued differential equation that remains in $K$ for all time
• Stochastic set-valued analysis extends the theory of multifunctions to random sets and stochastic processes
  • Random sets are set-valued mappings defined on a probability space, and they have applications in statistics, econometrics, and image analysis
• Fuzzy set-valued analysis combines the concepts of fuzzy sets and multifunctions to study uncertainty and vagueness in mathematical models
  • Fuzzy multifunctions assign to each element of the domain a fuzzy subset of the codomain, allowing for gradual membership and imprecise values
• Current research in set-valued analysis and multifunctions focuses on topics such as generalized differentiation, set-valued optimization, equilibrium problems, and applications in various fields, including economics, control theory, and machine learning