I am taking Convex Optimization this semester (2021 Spring). The notes are based on my understanding of the course materials provided by Prof. Zhouchen Lin. The notes only offer concise definition and formulas with few proofs and examples.

In this chapter, we introduce convexity. We define convex sets first and will discuss convex functions in the next chapter. We go from affine sets to convex sets and cones. Later on, we will talk about some operations that could preserve convexity. Also, we will discuss about how to separate two convex sets.

Convex Sets#

Table of Contents:

Affine and convex sets#


  • Line segment

    The line passing through two given points $ \mathbf{x}{1}, \mathbf{x}{2}$ can be described parametrically by θ\theta:

    y=θx1+(1θ)x2=x2+θ(x1x2)\mathbf{y}=\theta \mathbf{x}_{1}+(1-\theta) \mathbf{x}_{2} = \mathbf{x}_{2}+\theta( \mathbf{x}_{1}- \mathbf{x}_{2})

  • Affine sets

    A set is affine if for any $ \mathbf{x}{1}, \mathbf{x}{2}\in {C}, \theta\in\mathbb{R}$, we have θx1+(1θ)x2C\theta \mathbf{x}_{1}+(1-\theta) \mathbf{x}_{2}\in{C}.

    e.g. The solution set of a linear equation is an affine set:

    Ax1=b,Ax2=bA(θx1+(1θ)x2)=b\mathbf{Ax}_1=\mathbf{b}, \mathbf{Ax}_2=\mathbf{b}\Rightarrow \mathbf{A}(\theta \mathbf{x}_{1}+(1-\theta) \mathbf{x}_{2})=\mathbf{b}

    In reverse, every affine set can be expressed as the solution set of a system of linear equations.

  • Affine hull

    Given a set C\mathcal{C}, generalize to finite(to ensure the affine combination to be finite) multiple points and we have its affine hull:

    affC={θ1x1++θkxkx1,,xkC,θ1++θk=1}\operatorname{aff} C=\left\{\theta_{1} \mathbf{x}_{1}+\ldots+\theta_{k} \mathbf{x}_{k} \mid \mathbf{x}_{1}, \ldots, \mathbf{x}_{k} \in C, \theta_{1}+\ldots+\theta_{k}=1\right\}

    We can define relative interior and relative boundary of an affine set. By relative, we mean that when dimC<dimB(x,r)\text{dim} {C} < \text{dim} {B}(\mathbf{x}, r), only B(x,r)affCCB(\mathbf{x}, r) \cap \operatorname{aff} {C} \subseteq {C} is required (not the whole ball).


  • Convex sets

    A set is convex if for any x1,x2C,0θ1\mathbf{x}_{1}, \mathbf{x}_{2}\in {C}, 0\le\theta\le 1, we have θx1+(1θ)x2C\theta \mathbf{x}_{1}+(1-\theta) \mathbf{x}_{2}\in{C}. (i.e. line segment between any 2 points lies in the set)

    • Not necessary to be closed
    • \empty is also convex
  • Practice. How to determine whether a set is convex?

    1. By definition

      Example: {xRnαaxβ}\left\{\mathbf{x} \in \mathbb{R}^{n} \mid \alpha \leq \mathbf{a}^{\top} \mathbf{x} \leq \beta\right\} is convex:

      a(θx1+(1θ)x2)=θax1+(1θ)ax2θαθax1θβ,(1θ)α(1θ)ax2(1θ)βαa(θx1+(1θ)x2)β\mathbf{a}^\top(\theta \mathbf{x}_{1}+(1-\theta) \mathbf{x}_{2}) = \theta\mathbf{a^\top}\mathbf{x}_{1}+(1-\theta)\mathbf{a^\top}\mathbf{x}_{2}\\\theta\alpha\le \theta\mathbf{a^\top}\mathbf{x}_{1}\le \theta\beta,\quad(1-\theta)\alpha \le (1-\theta)\mathbf{a^\top}\mathbf{x}_{2}\le (1-\theta)\beta\\\Rightarrow \alpha \le \mathbf{a}^\top(\theta \mathbf{x}_{1}+(1-\theta) \mathbf{x}_{2})\le \beta

    2. By constructing the condition of the set to be the form of a convex set.

      Example: {xxa2θxb2}(ab,0θ1)\left\{\mathbf{x} \mid\|\mathbf{x}-\mathbf{a}\|_{2} \leq \theta\|\mathbf{x}-\mathbf{b}\|_{2}\right\}(\mathbf{a} \neq \mathbf{b},0\le\theta\le 1) is convex.

      xa2θxb2(xa)(xa)θ2(xb)(xb)(1θ2)xx2(aθ2b)xθ2bbaaxx2(aθ2b)x1θ2θ2bbaa1θ2xaθ2b1θ222θ2(ab)2(1θ2)2xaθ2b1θ22θab21θ2\begin{aligned}\|\mathbf{x}-\mathbf{a}\|_{2} \leq& \theta\|\mathbf{x}-\mathbf{b}\|_{2}\\(\mathbf{x}-\mathbf{a})^\top (\mathbf{x}-\mathbf{a})\le& \theta^2(\mathbf{x}-\mathbf{b})^\top (\mathbf{x}-\mathbf{b})\\(1-\theta^2)\mathbf{x}^\top \mathbf{x}-2(\mathbf{a}^\top-\theta^2\mathbf{b}^\top)\mathbf{x}\le &\theta^2\mathbf{b}^\top \mathbf{b}-\mathbf{a}^\top \mathbf{a}\\\mathbf{x}^\top \mathbf{x}-\frac{2(\mathbf{a}^\top-\theta^2\mathbf{b}^\top)\mathbf{x}}{1-\theta^2}\le &\frac{\theta^2\mathbf{b}^\top \mathbf{b}-\mathbf{a}^\top \mathbf{a}}{1-\theta^2}\\\left\|\mathbf{x}-\frac{\mathbf{a}-\theta^2\mathbf{b}}{1-\theta^2}\right\|_2^2\le& \frac{\theta^2(\mathbf{a}-\mathbf{b})^2}{(1-\theta^2)^2}\\\left\|\mathbf{x}-\frac{\mathbf{a}-\theta^2\mathbf{b}}{1-\theta^2}\right\|_2\le&\frac{\theta\|\mathbf{a}-\mathbf{b}\|_2}{1-\theta^2}\\\end{aligned}

      The set is a n-dimensional ball, which is convex.

  • Convex hull

    Convex hull of a set CC is the set of all convex combinations of points in CC.


    • conv{eiej}=xij0,ijxij=1\operatorname{conv}\{\mathbf{e}_i\mathbf{e}_j^\top\} = x_{ij}\ge 0,\sum_{ij}x_{ij}=1

    • conv{uuu=1}\operatorname{conv}\{\mathbf{u}\mathbf{u}^\top\mid\|\mathbf{u}\|=1 \}

      By definition of convex hull, S={iλiuiuiλi0,iλi=1}S = \{\sum_{i}\lambda_i\mathbf{u}_i\mathbf{u}_i^\top\mid \lambda_i\ge0,\sum_i\lambda_i=1\}. If XS\mathbf{X}\in S, then X0,tr(X)=1\mathbf{X}\succeq 0, \operatorname{tr}(\mathbf{X})=1.

      1. Sum of semidefinite matrices is still semidefinite.
      2. tr(iλiuiui)=iλitr(uiui)=iλi=1\operatorname{tr}\left(\sum_{i}\lambda_i\mathbf{u}_i\mathbf{u}_i^\top\right) = \sum_i\lambda_i\operatorname{tr}\left(\mathbf{u}_i\mathbf{u}_i^\top\right)=\sum_{i}\lambda_i=1.

      Now we have another set S~={XX0,tr(X)=1}\tilde{S}=\{\mathbf{X}\mid\mathbf{X}\succeq 0, \operatorname{tr}(\mathbf{X})=1 \}. We have already proved that SS~S\subset\tilde{S}.

      Suppose that XS~\mathbf{X}\in\tilde{S}. By eigenvalue decomposition, X=iλiuiui\mathbf{X} = \sum_i{\lambda_i}\mathbf{u}_i\mathbf{u}_i^\top. iλi=tr(X)=1\sum_i\lambda_i = \operatorname{tr}(\mathbf{X}) = 1. Thus, S~S\tilde{S}\subset S, S~=S\tilde{S}= S.

    • conv{uvu=v=1}\operatorname{conv}\{\mathbf{u}\mathbf{v}^\top\mid\|\mathbf{u}\|=\|\mathbf{v}\|=1 \}

      S={iσuiviσ0,iσi=1}S = \{\sum_{i}\sigma\mathbf{u}_i\mathbf{v}_i^\top\mid \sigma\ge0,\sum_i\sigma_i=1\}. S~=S~={XX1}\tilde{S} = \tilde{S}=\{\mathbf{X}\mid\|\mathbf{X}\|_*\le 1\}.

      1. SS~S\subset \tilde{S}

        X=iσuiviby triangle inequality of norm,iσiuivithe rank is 1, so its SVD=itself, eigenvalue is (1,0,)=iσi=1\begin{aligned} \|\mathbf{X}\|_* =&\|\sum_i\sigma\mathbf{u}_i\mathbf{v}_i^\top\|_*\quad\text{by triangle inequality of norm,}\\ \le& \sum_i\sigma_i \|\mathbf{u}_i\mathbf{v}_i^\top\|_*\quad \text{the rank is 1, so its SVD=itself, eigenvalue is }(1,0,\cdots)\\ =&\sum_i\sigma_i = 1 \end{aligned}

      2. S~S\tilde{S}\subset S

        X=UΣV=ipσiuivi,p=min(m,n)\|\mathbf{X}\|=\mathbf{U\Sigma V}^\top = \sum_i^p\sigma_i\mathbf{u}_i\mathbf{v}_i^\top, \quad p=\min(m,n)

        Since σi\sigma_i is singular value, it satisfies σi0\sigma_i\ge 0. Let δ=1i=1pσi\delta = 1-\sum_{i=1}^p\sigma_i. Take σp+1=σp+2=δ/2\sigma_{p+1}=\sigma_{p+2} = \delta/2, take up+2=up+1,vp+1=vp+1\mathbf{u}_{p+2}=-\mathbf{u}_{p+1}, \mathbf{v}_{p+1}=\mathbf{v}_{p+1}. Now we have:



A set CC is a cone if for every xC,θ>0\mathbf{x}\in C,\theta>0, we have θxC\theta\mathbf{x}\in C.

A set CC is a convex cone if for any x1,x2C,θ1,θ2>0\mathbf{x}_1,\mathbf{x}_2\in C, \theta_1,\theta_2>0, we have θ1x1+θ2x2C\theta_1\mathbf{x}_1+\theta_2\mathbf{x}_2\in C.

The conic hull of a set CC is the set of all conic combinations of points in CC.

{θ1x1++θkxkxiC,θi0,i=1,,k}\left\{\theta_{1} \mathbf{x}_{1}+\ldots+\theta_{k} \mathbf{x}_{k} \mid \mathbf{x}_{i} \in C, \theta_{i} \geq 0, i=1, \ldots, k\right\}

  • Dual cone

    Let KK be a cone, its dual cone KK^* satisfies:

    K={yxy0,xK}K^* = \{\mathbf{y\mid \mathbf{x}^\top \mathbf{y}\ge 0, \forall\mathbf{x}\in K}\}

    KK^* is always closed convex. K1K2K_1\subseteq K_2 implies K2K1K_2^*\subseteq K_1^*. KK^{**} is the closure of the convex hull of KK.


    • Subspace. K={xAx=0}K=\{\mathbf{x}\mid \mathbf{Ax}=\mathbf{0}\}. K={y(A)y=0}K^*=\{\mathbf{y}\mid \mathbf{(A^\perp )^\top y}=\mathbf{0}\}. Because x=Az\mathbf{x}=\mathbf{A^\perp z}.

    • Positive semidefinite cone. Dual cone is itself. tr(XY)0 for all X0Y0\operatorname{tr}(\mathbf{X Y}) \geq 0 \text { for all } \mathbf{X} \succeq \mathbf{0} \Longleftrightarrow \mathbf{Y} \succeq \mathbf{0}

      1. \Rightarrow.

        If YS+n\mathbf{Y\notin}S_+^n, then there exists q\mathbf{q} that qYq=tr(qqY)<0\mathbf{q}^\top \mathbf{Y}\mathbf{q}=\operatorname{tr}(\mathbf{q}\mathbf{q}^\top\mathbf{Y} )<0. Let X=qq0\mathbf{X}=\mathbf{q}\mathbf{q}^\top\succeq0, we have tr(XY)<0\operatorname{tr}(\mathbf{X Y})<0. Thus, tr(XY)0 for all X0Y0\operatorname{tr}(\mathbf{X Y}) \geq 0 \text { for all } \mathbf{X} \succeq \mathbf{0} \Longrightarrow \mathbf{Y} \succeq \mathbf{0}

      2. \Leftarrow.

        tr(YX)=tr(Yi=1nλiqiqiT)=i=1nλiqiTYqi0\operatorname{tr}(\mathbf{Y X})=\operatorname{tr}\left(\mathbf{Y} \sum_{i=1}^{n} \lambda_{i} \mathbf{q}_{i} \mathbf{q}_{i}{ }^{T}\right)=\sum_{i=1}^{n} \lambda_{i} \mathbf{q}_{i}{ }^{T} \mathbf{Y} \mathbf{q}_{i} \geq 0

    • Norm cone. K={(x,t)Rn+1xt}K=\left\{(\mathbf{x}, t) \in \mathbb{R}^{n+1} \mid\|\mathbf{x}\| \leq t\right\}. Dual cone: K={(u,v)Rn+1uv}K^*=\left\{(\mathbf{u}, v) \in \mathbb{R}^{n+1} \mid\|\mathbf{u}\|^* \leq v\right\}

      We need to prove that xu+tv0\mathbf{x}^\top \mathbf{u}+tv\ge 0 for all xtuv\|\mathbf{x}\|\le t\Longleftrightarrow \|\mathbf{u}\|^*\le v.

      1. \Leftarrow.

        For some t>0,t>0, xt\|\mathbf{x}\|\le t. By definition of dual norm, u(x/t)uv\mathbf{u}^\top (-\mathbf{x}/t)\le \|\mathbf{u}\|^* \le v, and thus ux+tv0\mathbf{u}^\top\mathbf{x} +tv\ge 0.

      2. \Rightarrow.

        If u>v\|\mathbf{u}\|^*>v, then by definition of dual norm, there exists an x\mathbf{x} that x1\|\mathbf{x}\|\le 1 and xu>v\mathbf{x^\top u}>v.

        Then we have x=x1\|-\mathbf{x}\| = \|\mathbf{x}\|\le 1 and take t=1t=1: u(x)+v<0\mathbf{u}^\top(-\mathbf{x}) +v< 0, which contradicts with the lefthand side(assumption). Thus, uv\|\mathbf{u}\|^*\le v.

    Given KK, we usually guess a dual cone KK^*. If it is hard to prove that xy0,xKyK\mathbf{x^\top y}\ge 0,\forall \mathbf{x}\in K\Leftrightarrow \mathbf{y}\in K^*, we can prove xy0,yKxK\mathbf{x^\top y}\ge 0,\forall \mathbf{y}\in K^*\Leftrightarrow \mathbf{x}\in K instead.

Operators that preserve convexity#


SαS_\alpha is convex αAαASα\forall \alpha\in\mathcal{A}\Rightarrow\bigcap_{\alpha\in\mathcal{A}}S_\alpha is convex (can be intersection of an infinite number of sets)

Affine function#

SRnS\subseteq \R^n is convex, f(x)=Ax+b:RnRmf(S)={f(x)xS}f(\mathbf{x})= \mathbf{Ax}+\mathbf{b}:\R^n\to \R^m\Rightarrow f(S) =\{f(\mathbf{x})\mid \mathbf{x}\in S\} is convex

Similarly, the inverse image of SS under ff: f1(S)={xf(x)S}f^{-1}(S)=\{\mathbf{x}\mid f(\mathbf{x})\in S\} is also convex.

Sum and Cartesian product#

S1,S2S_1,S_2 are convex, then S1+S2={x+yxS1,yS2}S_1+S_2=\{\mathbf{x}+\mathbf{y}\mid \mathbf{x}\in S_1,\mathbf{y}\in S_2 \} and S1×S2={(x1,x2)x1S1,x2S2}S_1\times S_2=\{(\mathbf{x}_1,\mathbf{x}_2)\mid \mathbf{x}_1\in S_1,\mathbf{x}_2\in S_2 \} are convex.


  • Polyhedron

    {xAxb,Cx=d}={xf(x)R+m×{0}},f(x)=(bAx,dCx)\{\mathbf{x}\mid\mathbf{Ax}\preceq\mathbf{b},\mathbf{Cx}=\mathbf{d} \}=\{\mathbf{x}\mid f(\mathbf{x})\in\R_+^m\times\{0\} \}, f(\mathbf{x})=(\mathbf{b}-\mathbf{Ax},\mathbf{d}-\mathbf{Cx})

  • Solution set of A(x)=i=1nxiAiBA(\mathbf{x})=\sum_{i=1}^n\mathbf{x}_i\mathbf{A}_i\preceq\mathbf{B}

    the inverse image of positive semidefinite cone under f(x)=BA(x)f(\mathbf{x})=\mathbf{B}-A(\mathbf{x})

  • Hyperbolic cone {xxPx(cx)2,cx0}\{\mathbf{x}\mid\mathbf{x}^\top \mathbf{Px}\le (\mathbf{c}^\top\mathbf{x})^2,\mathbf{c}^\top\mathbf{x}\ge 0 \}, PS+n\mathbf{P}\in\mathbb{S}^n_+

    the inverse image of the second order cone {(z,t)zzt2.t0}\{(\mathbf{z},t)\mid \mathbf{z}^\top \mathbf{z}\le t^2.t\ge 0 \} under f(x)=(P1/2x,cx)f(\mathbf{x})=(\mathbf{P}^{1/2}\mathbf{x}, \mathbf{c}^\top\mathbf{x})

  • Ellipsoid {x(xxc)P1(xxc)1}\{\mathbf{x}\mid(\mathbf{x}-\mathbf{x}_c)^\top \mathbf{P}^{-1}(\mathbf{x}-\mathbf{x}_c)\le 1\}

    The image of Euclidean ball {uu21}\{\mathbf{u}\mid \|\mathbf{u}\|_2\le 1\} under x=f(u)=P1/2u+xc\mathbf{x}=f(\mathbf{u}) = \mathbf{P}^{1/2}\mathbf{u}+\mathbf{x}_c

    The inverse image of the unit ball under u=g(x)=P1/2(xxc)\mathbf{u}=g(\mathbf{x} )=\mathbf{P}^{-1/2}(\mathbf{x}-\mathbf{x}_c)

Perspective function#

P:Rn+1Rn,P(z,t)=z/t,zRn,t>0P:\R^{n+1}\to\R^n, P(\mathbf{z},t)=\mathbf{z}/t,\mathbf{z}\in\R^n,t>0. The perspective function actually scales the vector so that the last component becomes 1, and can then be dropped.

If CC Is convex, then P(C)={P(x)xC}P(C)=\{P(\mathbf{x})\mid \mathbf{x}\in C\} and P1(C)={(x,t)Rn+1x/tC,t>0}P^{-1}(C)=\{(\mathbf{x},t)\in\R^{n+1}\mid \mathbf{x}/t\in C, t>0\} are convex.

Linear-fractional functions#

Applying perspective function to affine functions. If g(x)=[AcT]x+[bd]g(\mathbf{x})=\left[\begin{array}{l} \mathbf{A} \\ \mathbf{c}^{T} \end{array}\right] \mathbf{x}+\left[\begin{array}{l} \mathbf{b} \\ d \end{array}\right], then f(x)=(Ax+b)/(cx+d),domf={xcx+d>0}f(\mathbf{x}) = (\mathbf{Ax}+\mathbf{b})/ (\mathbf{c^\top x}+d), \textbf{dom} f=\{\mathbf{x}\mid \mathbf{c^\top x}+d>0\}.

Separating and supporting hyperplanes#

Separating hyperplane theorem#

Two convex sets CD=a0,bC\cap D=\empty \Leftrightarrow \exist \mathbf{a\ne0}, b that axb,xC,axb,xD\mathbf{a^\top x}\le b,\forall \mathbf{x}\in C,\mathbf{a^\top x}\ge b,\forall \mathbf{x}\in D.

Example: Separation of an affine and a convex set

CC Is convex and D={Fu+guRm}D=\{\mathbf{Fu+g}\mid \mathbf{u}\in\R^m\} is affine. Suppose that they are disjoint, then there exist a0\mathbf{a\ne 0} and bb such that axb,xD\mathbf{a^\top x}\ge b,\forall \mathbf{x}\in D. Thus, aFubag\mathbf{a^\top Fu}\ge b-\mathbf{a^\top g}. Since the righthand side is a number, the linear function aFu\mathbf{a^\top Fu} is bounded below iff aF=0\mathbf{a^\top F=0}.

Thus, there exist a0\mathbf{a\ne 0} such that Fa=0,axag,xC\mathbf{F^\top a=0}, \mathbf{a^\top x}\le \mathbf{a^\top g}, \forall \mathbf{x}\in C.


Strict separation#

Two convex sets CD=a0,bC\cap D=\empty \Leftrightarrow \exist \mathbf{a\ne0}, b that ax<b,xC,ax>b,xD\mathbf{a^\top x}< b,\forall \mathbf{x}\in C,\mathbf{a^\top x}> b,\forall \mathbf{x}\in D.

Example: Separation of a point and a closed convex set

That is to say, the two sets C,B(x0,ϵ)C, B(\mathbf{x}_0,\epsilon) do not intersect for some ϵ>0\epsilon > 0. Since B(x0,ϵ)={x0+uu2ϵ}B(\mathbf{x}_0,\epsilon)=\{\mathbf{x}_0+\mathbf{u}\mid \|\mathbf{u}\mid_2\le \epsilon \}, we have

axb,xCa(x0+u)b,u2ϵ\mathbf{a^\top}\mathbf{x}\le b,\forall \mathbf{x}\in C\\ \mathbf{a^\top}(\mathbf{x}_0+\mathbf{u})\ge b, \forall \|\mathbf{u}\|_2\le \epsilon

The u\mathbf{u} minimizes the lefthand side is u=ϵa/a2\mathbf{u}=\epsilon \mathbf{a}/\|\mathbf{a}\|_2, so ax0ϵa2b\mathbf{a}^\top \mathbf{x}_0-\epsilon\|\mathbf{a}\|_2\ge b. Therefore, f(x)=axϵa2/2bf(\mathbf{x}) = \mathbf{a}^\top \mathbf{x}-\epsilon\|\mathbf{a}\|_2/2- b is negative on CC and positive at x0\mathbf{x}_0.

Corollary: A closed convex set is the intersection of all half spaces that contain it.

Obviously if a point is in the closed convex, it is in all the half spaces that contain it.

In reverse, if there exists a point x\mathbf{x} that is of the intersection SS but not in the convex set CC, then by strict separation, there exists a hyperplane that separates x\mathbf{x} and the CC. Thus, this half space contains CC but not x\mathbf{x}, so xS\mathbf{x}\notin S.

Converse separating hyperplane theorems#

Any two convex sets C,DC, D, at least one of which is open, are disjoint iff there exists a separating plane.

Farkas Lemma

For ARm×n,bRm\mathbf{A}\in\R^{m\times n}, \mathbf{b}\in\R^m, the following are strong alternatives:

  1. xR+n,Ax=b\exist \mathbf{x}\in \R_+^n, \mathbf{Ax=b}
  2. yRm,Ay0,by<0\exist\mathbf{y}\in\R^m, \mathbf{A^\top y}\ge \mathbf{0}, \mathbf{b^\top y}<0


1¬21\Rightarrow\neg 2: by=(xA)y0\mathbf{b^\top y}=(\mathbf{x^\top A^\top})\mathbf{y} \ge 0

¬12\neg1 \Rightarrow 2: C=cone(A)C=cone(\mathbf{A}) is a closed convex cone that does not contain b\mathbf{b}. Hence by separating hyperplane theorem, there exists a yRm\mathbf{y}\in\R^m that y,x0>y,b,xC\langle \mathbf{y}, \mathbf{x}\rangle \ge 0 > \langle\mathbf{y},\mathbf{b}\rangle, \forall \mathbf{x}\in C, i.e. Ay0,by<0\mathbf{A^\top y}\ge \mathbf{0}, \mathbf{b^\top y}<0.

Supporting hyperplanes#

If a0\mathbf{a\ne 0} satisfies axax0,xC\mathbf{a^\top x}\le \mathbf{a^\top x}_0, \forall \mathbf{x}\in C, then the hyperplane {xax=ax0}\{\mathbf{x}\mid \mathbf{a^\top x} = \mathbf{a^\top x}_0\} is the supporting hyperplane to CC at point x0\mathbf{x}_0. Geometrically, the hyperplane is tangent to CC at point x0\mathbf{x}_0.

Supporting hyperplane theorem

For any nonempty convex set CC and any x0C\mathbf{x}_0\in\partial C, there exists a supporting hyperplane to CC at point x0\mathbf{x}_0.