Chapter 2.3 Operations that Preserves Convexity

2.3.1 Intersection

1. If \(S_\alpha\) is convex for every \(\alpha\in\mathcal{A}\), then \(\cap_{\alpha\in\mathcal{A}}S_{\alpha}\) is convex.
2. Every closed convex set \(S\) is a (usually infinite) intersection of halfspaces.

2.3.2 Affine Functions

1. What is an affine function?

   The form \(f(x)=Ax+B\) is affine function, where \(f:\mathbb{R}^n\rightarrow\mathbb{R}^m\), \(A\in\mathbb{R}^{m\times n}\) and \(B\in\mathbb{R}^{m}\).

2. Affine function preserves convexity

   Suppose \(S\subseteq\mathbb{R}^n\) is convex, and \(f:\mathbb{R}^n\rightarrow\mathbb{R}^m\) is an affine function. Then the image of \(S\) under \(f\), i.e., \(\{f(x)\vert x\in S\}\) is convex.

3. Inverse affine function preserves convexity

   Suppose \(S\subseteq\mathbb{R}^n\) is convex, and \(f:\mathbb{R}^k\rightarrow\mathbb{R}^n\) is an affine function. Then the image of \(S\) under \(f\), i.e., \(\{x\vert f(x)\in S\}\) is convex.

4. Some affine functions. Bellow are some affine functions, the sets \(S_i\)’s are assumed to be convex.

   1. scaling: \(\{\alpha S\vert x\in S\}\), \(\alpha\in\mathbb{R}\), \(S\subseteq\mathbb{R^n}\).
   2. translating: \(\{a+S\vert x\in S\}\), \(a\in\mathbb{R}^n\), \(S\subseteq\mathbb{R^n}\).
   3. projection: \(\{x_1\in\mathbb{R}^m\vert (x_1, x_2)\in S, {\text{for some}} x_2\in\mathbb{R}^{n}\}\), \(S\in\mathbb{R}^{m\times n}\).
   4. sum: \(\{x+y\vert x\in S_1, y\in S_2\}\).
   5. partial sum: \(\{(x,y_1+y_2)\vert (x, y_1)\in S_1, (x, y_2)\in S_2\}\), where \(x\in\mathbb{R}^n, yi\in\mathbb{R}^m, S_{i}\in\mathbb{R}^{m\times n}\). If \(m=0\), partial sums becomes intersection; if \(n=0\), partial sum becomes sum.

2.3.3 Linear-fraction and perspective functions

1. perspective function.
   1. The perspective function \(P\): \(\mathbb{R}^{n+1}\rightarrow\mathbb{R}^n\), with domain \({\bf{dom}}P=\mathbb{R}^{n}\times\mathbb{R}_{++}\), is defined as: \(P(z,t)=z/t\).
   2. If \(C\subseteq {\bf{dom}}P\), then its image \(P(C)=\{P(x)\vert x\in C\}\) is convex.
   3. The inverse image of a convex set under the perspective function is also convex: If \(C\subseteq \mathbb{R}^n\) is convex, then \(P^{-1}(C)=\{(x,t)\in\mathbb{R}^{n+1}\vert x/t\in C, t>0\}\).
2. linear-fractional function.

   1. Suppose \(g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m+1}\) is affine, i.e.,:

      \[\begin{aligned} g(x)= [A^T~c]^Tx+[b^T~d]^T, \end{aligned}\]

      where \(A\in\mathbb{R}^{m\times n }, c\in\mathbb{R}^{n}, b\in\mathbb{R}^{m}\), and \(d\in\mathbb{R}\). The function \(f: \mathbb{R}^n\rightarrow\mathbb{R}^m\) given by \(f=P\circ g\): \(f(x)=Ax+b/c^Tx+d\), with \({\bf{dom}}f=\{x\vert c^Tx+d>0\}\) is called a linear-fractional (or projective) function.

   2. Linear-fractional functions preserve the convextiy.
   3. If \(C\subseteq R^{m}\) is convex, then the inverse image \(f^{-1}(C)\) is convex.