Convex Set

Definition. A set C⊆RnC\subseteq \R^n is convex if for any points x,y∈Cx,y\in C and λ∈[0,1]\lambda \in [0,1].

λx+(1−λ)y∈C\lambda x+(1-\lambda)y\in C

Familiar Set Convex

Line: fix any Z∈RnZ\in \R^n. 0≠d∈Rn0\ne d\in \R^n.

L={Z+td∣t∈R}L=\{Z+td\mid t\in\R\}

Proof:

λx+(1−λ)y=λ(z+td)+(1−λ)(z+td)=λz+(1−λ)z+λdtx+(1−λ)dty=z+(λtx+(1−λ)ty)d\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α,β=x∈Rn∣aTx=βH_{\alpha,\beta}={x\in\R^n\mid a^Tx=\beta}. where a∈Rn\{0}&β∈R a\in \R ^n \backslash \{ 0 \} \& \beta \in \R

Ex:

He,1={x∣eTx=1}={x∣∑j=1nxj=1}\begin{aligned}H_{e,1}&= \{x\mid e^Tx=1 \} \\ &= \{x\mid \sum_{j=1}^n x_j=1 \}\end{aligned}

Halfspace: Hα,β−={x∈Rn∣aTx≤β}H^-_{\alpha,\beta}= \{x\in \R^n\mid a^Tx\le \beta \}(0≠a∈Rn,β∈R)(0\ne a\in\R^n, \beta\in \R)

Norm balls: B□={x∈Rn∣∥x−C∥□≤r}B_\square = \{x\in\R^n\mid \lVert x-C\rVert_\square\le r \}, where C∈RnC\in\R^n (center) and r∈R+r\in \R_+ is radius

Proof: A norm ∥⋅∥:Rn→R+\lVert \cdot \rVert:\R^n \to \R_+ satisfies the following

  1. ∥αx∥=∥α∥⋅∥x∥,∀α∈R\lVert \alpha x\rVert =\lVert \alpha\rVert \cdot \lVert x\rVert, \forall \alpha \in \R

  2. ∥x+y∥≤∥x∥+∥y∥\lVert x+y\rVert \le \lVert x\rVert +\lVert y\rVert

  3. ∥x∥=0⇔x=0\lVert x\rVert=0 \Leftrightarrow x=0

Example: The set of positive semidefinite matrices

Sn×n≡{x∈Rn×n∣x ane PSD}S_{n\times n}\equiv \{x\in \R^{n\times n}\mid x \text{ ane PSD}\} is convex

Z=λx+(1−λ)yZ=\lambda x+(1-\lambda)y, where X,Y∈Sn×nX,Y \in S_{n\times n} then ZZ is positive semidefinite.

Operations on sets that preserve convexity:

  1. Intersection

    For any collection of convex sets Ci∈RnC_i \in\R^n, i∈Ii \in I, then ∩i∈ICi\underset{i\in I}{\cap}C_i is convex. The union does not preserve convexity.

    Ex: the unit simplex in Rn\R^n is the set Δn:={x∈Rn∣∑j=1nxj=1,x≥0}\Delta_n := \{x\in \R^n\mid\sum_{j=1}^nx_j=1,x\ge0\}

    He2,0−={x∈Rn∣x2≥0,x1∈R}H^-_{e_{2,0}}=\{x\in \R^n\mid x_2\ge 0,x_1\in \R\}

    Proof: Take x,y∈∩i∈ICix,y\in\underset{i\in I}{\cap} C_i, show λx+(1−λ)y∈∩i∈ICi,∀λ∈[0,1]\lambda x+(1-\lambda)y\in \underset{i\in I}{\cap} C_i ,\forall \lambda \in [0,1].

    Because x,y∈∩i∈ICi  ⟹  x,y∈Ci∀i∈Ix,y \in \underset{i\in I}{\cap} C_i \implies x,y\in C_i \forall i\in I

    Because CiC_i convex λx+(1−λ)y∈Ci∀i  ⟹  λx+(1−λ)y∈∩i∈ICi\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 C1,C2,…,CmC_1,C_2,\ldots,C_m are convex sets in Rn\R^n, then the set addition

    C1+C2+…+Cm={Z=x1+x2+…+xm∣xi∈Ci,i=1,…,m}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≤RnC\le \R^n is convex and AA is an m×nm\times n matrix, then A(c):={Ax∣x∈C}A(c):= \{Ax\mid x\in C \} is convex.

PreviousLinear ConstraintsNextConvex Functions

Last updated