> For the complete documentation index, see [llms.txt](https://muhans-notebook.gitbook.io/computational-optimization/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://muhans-notebook.gitbook.io/computational-optimization/convex-set.md).
# Convex Set
***Definition.*** A set $$C\subseteq \R^n$$ is convex if for any points $$x,y\in C$$ and $$\lambda \in \[0,1]$$.
$$
\lambda x+(1-\lambda)y\in C
$$
Familiar Set Convex
Line: fix any $$Z\in \R^n$$. $$0\ne d\in \R^n$$.
$$
L={Z+td\mid t\in\R}
$$
Proof:
$$\begin{aligned}\lambda x+(1-\lambda)y&=\lambda(z+td)+(1-\lambda)(z+td) \ &=\lambda z+(1-\lambda)z+\lambda d tx+(1-\lambda)dty \ &=z+(\lambda tx+(1-\lambda)ty)d\end{aligned}$$
Hyperplane: $$H\_{\alpha,\beta}={x\in\R^n\mid a^Tx=\beta}$$. where $$a\in \R ^n \backslash { 0 } & \beta \in \R$$
Ex:
$$\begin{aligned}H\_{e,1}&= {x\mid e^Tx=1 } \ &= {x\mid \sum\_{j=1}^n x\_j=1 }\end{aligned}$$
Halfspace: $$H^-\_{\alpha,\beta}= {x\in \R^n\mid a^Tx\le \beta }$$$$(0\ne a\in\R^n, \beta\in \R)$$
Norm balls: $$B\_\square = {x\in\R^n\mid \lVert x-C\rVert\_\square\le r }$$, where $$C\in\R^n$$ (center) and $$r\in \R\_+$$ is radius
Proof: A norm $$\lVert \cdot \rVert:\R^n \to \R\_+$$ satisfies the following
1. $$\lVert \alpha x\rVert =\lVert \alpha\rVert \cdot \lVert x\rVert, \forall \alpha \in \R$$
2. $$\lVert x+y\rVert \le \lVert x\rVert +\lVert y\rVert$$
3. $$\lVert x\rVert=0 \Leftrightarrow x=0$$
Example: The set of positive semidefinite matrices
$$S\_{n\times n}\equiv {x\in \R^{n\times n}\mid x \text{ ane PSD}}$$ is convex
$$Z=\lambda x+(1-\lambda)y$$, where $$X,Y \in S\_{n\times n}$$ then $$Z$$ is positive semidefinite.
#### Operations on sets that preserve convexity:
1. **Intersection**
For any collection of convex sets $$C\_i \in\R^n$$, $$i \in I$$, then $$\underset{i\in I}{\cap}C\_i$$ is convex. The union does not preserve convexity.
Ex: the unit simplex in $$\R^n$$ is the set $$\Delta\_n := {x\in \R^n\mid\sum\_{j=1}^nx\_j=1,x\ge0}$$
$$
H^-*{e*{2,0}}={x\in \R^n\mid x\_2\ge 0,x\_1\in \R}
$$
Proof: Take $$x,y\in\underset{i\in I}{\cap} C\_i$$, show $$\lambda x+(1-\lambda)y\in \underset{i\in I}{\cap} C\_i ,\forall \lambda \in \[0,1]$$.
Because $$x,y \in \underset{i\in I}{\cap} C\_i \implies x,y\in C\_i \forall i\in I$$
Because $$C\_i$$ convex $$\lambda x+(1-\lambda)y\in C\_i \forall i \implies \lambda x+(1-\lambda)y\in \underset{i\in I}{\cap} C\_i$$
2. **Addition.** If $$C\_1,C\_2,\ldots,C\_m$$ are convex sets in $$\R^n$$, then the set addition
$$
C\_1+C\_2+\ldots+C\_m={Z=x\_1+x\_2+\ldots+x\_m\mid x\_i\in C\_i, i=1,\ldots,m}
$$
is convex.
3. **Image of a set.** If $$C\le \R^n$$ is convex and $$A$$ is an $$m\times n$$ matrix, then $$A(c):= {Ax\mid x\in C }$$ is convex.
