How does one go about finding convex hulls of functions.
For example the equation $x_{1}^{2} + x_{2}^{2} = 1$.
How I attempted to solve this problem was I selected the extreme points $(1,0)$; $(0,1)$; $(-1,0)$; $(0,-1)$ and I applied the divide and conquer algorithm. I added number of points but I figured it won’t be a convex hull.
Could one help me on formulating convex hulls because I search and all I find is algorithms which make use of a finite amount of points.
Best Answer
What you're looking for is the biconjugate of a function, which forms the convex envelope (hull) of a function. The conjugate of a function $f: \mathbb{E}\to [-\infty,\infty]$ is defines as $$f^*(\mathbf{y}) = \max_{\mathbf{x}\in\mathbb{E}} \mathbf{y}^T\mathbf{x} - f(\mathbf{x}),$$ therefore the biconjugate is $$f^{**}(\mathbf{x}) = \max_{\mathbf{y}\in\mathbb{E}^*} \mathbf{x}^T\mathbf{y} - f^*(\mathbf{y}).$$ It can be shown, for example, that the $l_1$ norm is the convex envelope of the $l_0$ "norm".
For your function we can say that it's an indicator on the set $S=\{\mathbf{x}\in\mathbb{R}^n | \|\mathbf{x}\|_2^2=1 \}$. Therefore $f(\mathbf{x})=0$ if $\mathbf{x}\in S$ and $f(\mathbf{x})=\infty$ otherwise. So we have $$f^*(\mathbf{y}) = \max_{\mathbf{x}} \mathbf{y}^T\mathbf{x} - \delta_S(\mathbf{x})\overset{\mathbf{x}=\frac{\mathbf{y}}{\|\mathbf{y}\|}}{=}\|\mathbf{y}\|_2,$$ as the maximum is attained when $\mathbf{x}, \mathbf{y}$ are colinear and we must have $\mathbf{x}$ as a unit vector. The biconjugate is $$f^{**}(\mathbf{x}) = \max_{\mathbf{y}} \mathbf{x}^T\mathbf{y} - \|\mathbf{y}\| \overset{\text{Cauchy Schwarz}}{\leq} \max_{\mathbf{y}} \|\mathbf{y}\|(\|\mathbf{x}\|-1).$$ We notice that if $\|\mathbf{x}\|\leq 1$ then any positive value of $\|\mathbf{y}\|$ will give the function a value lower than 0. Therefore we will set $\mathbf{y}=0$. If $\|\mathbf{x}\|>1$ the problem is unbounded. Therefore the final result is $f^{**}(\mathbf{x})=0$ if $\mathbf{x}\in C$, for the set $C=\{\mathbf{x}\in\mathbb{R}^n | \|\mathbf{x}\|_2^2\leq 1 \}$.