Computational Optimization
  • Computational Optimization
  • Basics
  • QR Factorization
  • Regularization
  • Gradients
  • Nonlinear Least-Squares
  • Gradient Descent
  • Descent Methods
  • Scaled Descent
  • Cholesky Factorization
  • Linear Constraints
  • Convex Set
  • Convex Functions
  • Global Optimal of Convex Optimization
  • Optimality for Convex Optimization
  • Projection Onto Convex Sets
  • Stochastic Gradient Descent (SGD)
Powered by GitBook
On this page

Convex Set

PreviousLinear ConstraintsNextConvex Functions

Last updated 1 year ago

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

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

Familiar Set Convex

Line: fix any Z∈RnZ\in \R^nZ∈Rn. 0≠d∈Rn0\ne d\in \R^n0=d∈Rn.

L={Z+td∣t∈R}L=\{Z+td\mid t\in\R\}L={Z+td∣t∈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}λx+(1−λ)y​=λ(z+td)+(1−λ)(z+td)=λz+(1−λ)z+λdtx+(1−λ)dty=z+(λtx+(1−λ)ty)d​

Hyperplane: Hα,β=x∈Rn∣aTx=βH_{\alpha,\beta}={x\in\R^n\mid a^Tx=\beta}Hα,β​=x∈Rn∣aTx=β. where a∈Rn\{0}&β∈R a\in \R ^n \backslash \{ 0 \} \& \beta \in \Ra∈Rn\{0}&β∈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}He,1​​={x∣eTx=1}={x∣j=1∑n​xj​=1}​

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

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

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

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

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

  3. ∥x∥=0⇔x=0\lVert x\rVert=0 \Leftrightarrow x=0∥x∥=0⇔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}\}Sn×n​≡{x∈Rn×n∣x ane PSD} is convex

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

Operations on sets that preserve convexity:

  1. Intersection

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

    Ex: the unit simplex in Rn\R^nRn 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\}Δn​:={x∈Rn∣∑j=1n​xj​=1,x≥0}

    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\}He2,0​−​={x∈Rn∣x2​≥0,x1​∈R}

    Proof: Take x,y∈∩i∈ICix,y\in\underset{i\in I}{\cap} C_ix,y∈i∈I∩​Ci​, 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]λx+(1−λ)y∈i∈I∩​Ci​,∀λ∈[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 Ix,y∈i∈I∩​Ci​⟹x,y∈Ci​∀i∈I

    Because CiC_iCi​ 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λx+(1−λ)y∈Ci​∀i⟹λx+(1−λ)y∈i∈I∩​Ci​

  2. Addition. If C1,C2,…,CmC_1,C_2,\ldots,C_mC1​,C2​,…,Cm​ are convex sets in Rn\R^nRn, 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\}C1​+C2​+…+Cm​={Z=x1​+x2​+…+xm​∣xi​∈Ci​,i=1,…,m}

    is convex.

  3. Image of a set. If C≤RnC\le \R^nC≤Rn is convex and AAA is an m×nm\times nm×n matrix, then A(c):={Ax∣x∈C}A(c):= \{Ax\mid x\in C \}A(c):={Ax∣x∈C} is convex.