Knowlpedia

Set-valued mapping (multifunction), domain, graph, and convexity

A set-valued map assigns a subset to each point and is convex when its graph is convex.

Let X,YX,Y be vector spaces. A set-valued mapping (or multifunction) is a map

F:X⇉YF:X\rightrightarrows Y

that assigns to each x∈Xx\in X a (possibly empty) subset F(x)⊂YF(x)\subset Y.

  • The domain of FF is
dom(F):={x∈X:F(x)≠∅}.\mathrm{dom}(F):=\{x\in X: F(x)\neq\emptyset\}.
  • The graph of FF is the subset of the X×YX\times Y given by
gph(F):={(x,y)∈X×Y:y∈F(x)}.\mathrm{gph}(F):=\{(x,y)\in X\times Y: y\in F(x)\}.

The multifunction FF is called convex if its graph gph(F)\mathrm{gph}(F) is a in X×YX\times Y.

Examples
  • Single-valued affine maps are convex multifunctions: if F(x)={Ax+b}F(x)=\{Ax+b\}, then gph(F)\mathrm{gph}(F) is an affine subset of X×YX\times Y.
  • In X=Y=RX=Y=\mathbb{R}, the map F(x)=[x,∞)F(x)=[x,\infty) has a convex graph.
  • The constant map F(x)=CF(x)=C has gph(F)=X×C\mathrm{gph}(F)=X\times C, convex iff CC is convex.