# Local convexity of a function containing norms

Given the function: $$f(\mathbf{x}, \mathbf{C}) = \prod_{i=1}^N\left(1+\frac{1}{2}\left|x_{i}-0.5\right| + \frac{1}{2}\left|C_{i}-0.5\right|-\frac{1}{2}\left|x_{i}-C_{i}\right|\right)$$ for $$\mathbf{x} \in [0,1]^N$$ and $$\mathbf{C} \in [0,1]^N$$.

I want to prove $$f(\mathbf{x}, \mathbf{C})$$ is locally convex across intervals defined by the constant (fixed) $$\mathbf{C}$$ and domain breaks at $$\{0, 1/2, 1\}^N$$. ie: convex in $$x_1,x_2 \in [0,0.5]$$ then separately convex in $$x_1 \in [0.5,0.7]$$, $$x_2 \in [0,0.5]$$, etc. for the example shown below

Relevant Information:

A function $$f: \mathbb{R}^N \rightarrow \mathbb{R}$$ is convex is $$\mathbf{dom} f$$ is a convex set and if for all $$x,y \in \mathbf{dom} f,$$ and $$\theta$$ with $$0 \leq \theta \leq 1,$$ we have: $$f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta)f(y)$$

If we assume that $$f$$ is twice differentiable, then $$f$$ is convex if and only if $$\mathbf{dom} f$$ is convex and its Hessian is positive semidefinite: for all $$x \in \mathbf{dom}f,$$ $$\nabla^2 f(x) \succeq 0$$

Now since $$\frac{d}{dx_i}\left(\left|x_i - \frac{1}{2}\right|\right) = \frac{x_i - \frac{1}{2}}{\left|x_i - \frac{1}{2}\right|}$$ and $$\frac{d}{dx_i}\left(\left|x_i - C_{i}\right|\right) = \frac{x_i - C_{i}}{\left|x_i - C_{i}\right|}$$ which are undefined at $$\frac{1}{2}$$ and $$C_i$$, I can only apply the second order condition (Hessian) on intervals where the minimum does not occur at an end point.

A 2D example with $$C_i = [0.7; 0.7]$$ is shown below:

Because of this, I would like to apply the definition of convexity $$f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta)f(y)$$ as well as leveraging the triangle inequality $$|a + b| \leq |a| + |b|$$. However, the term $$-\frac{1}{2}\left|x_{i}-C_{i}\right|$$ seems to throw a monkey wrench in this approach as well because of the $$-\frac{1}{2}$$ term out front after applying the triangle inequality to both absolute values (ie: the inequality would switch)

Question:

Is there a simple way to choose $$a$$ and $$b$$ in the triangle inequality such that $$f(\theta x + (1 - \theta)y) \leq \theta f(x) + (1 - \theta)f(y)$$ is easily shown? Or a slightly different approach for functions that are not continuously differentiable? thanks!

• Do you want $f$ to be convex with respect to $x$ for fixed $C$? Or convex with respect to both $x$ and $C$ considering $f : \mathbb{R}^{2N} \mapsto \mathbb{R}$?
– cs89
Commented Apr 30, 2023 at 17:29
• @cs89b I want $f$ to be convex with respect to $x$ for a fixed $C$ as in the example $C$ is fixed to $[0.7; 0.7]$ However, $C \in [0,1]^N$ can take any value in that domain and is generally not known a-priori Commented Apr 30, 2023 at 17:46
• Thanks for the precision. Once $C$ is fixed, do you want $f$ to be convex for the whole domain $[0,1]^N$? Or by "locally", you mean that for each $\bar{x} \in [0,1]^N$ (except at the singular points), you want $f$ to be convex in a neighborhood of $\bar{x}$?
– cs89
Commented Apr 30, 2023 at 17:53
• @cs89 once $C$ is fixed the domain $[0,1]^N$ is split into $N\text{-}d$ hyper-rectangles. By locally convex, I mean for a given interval (ie: say $x_1 \in [0.5, 0.7]$ and $x_2 \in [0.5, 0.7]$) I would like to prove $f$ is convex. Ideally, I would do this for all intervals including the break pts giving $f$ is convex for $[0,1]^N$ Commented Apr 30, 2023 at 18:14
• Are you really defining $f$ by a product? Your graph show a slanted plane, but I would expect something more curvy in the region $[0.5,0.7]^2$. Can you double check that there is no mistake?
– cs89
Commented May 1, 2023 at 17:14

We first define $$f_i(x_i,C_i)=1+0.5|x_i-0.5|+0.5|C_i-0.5|-0.5|x_i-C_i|,$$ so that we can write $$f(\mathbf{x},\mathbf{C})=\prod_{i=1}^n f_i(x_i,C_i)$$. Also, we consider the following intervals: $${ I_{i,0}=\{x_i\le 0.5,C_i\le 0.5,x_i\le C_i\}, \\ I_{i,1}=\{x_i\le 0.5,C_i\le 0.5,x_i\ge C_i\}, \\ I_{i,2}=\{x_i\le 0.5,C_i\ge 0.5,x_i\le C_i\}, \\ I_{i,3}=\{x_i\le 0.5,C_i\ge 0.5,x_i\ge C_i\}, \\ I_{i,4}=\{x_i\ge 0.5,C_i\le 0.5,x_i\le C_i\}, \\ I_{i,5}=\{x_i\ge 0.5,C_i\le 0.5,x_i\ge C_i\}, \\ I_{i,6}=\{x_i\ge 0.5,C_i\ge 0.5,x_i\le C_i\}, \\ I_{i,7}=\{x_i\ge 0.5,C_i\ge 0.5,x_i\ge C_i\} .}$$ Soon enough, the reason behind these definitions will be justified.

Over each of the intervals $$I_{i,j}$$ for $$0\le j\le 7$$, the function $$f_i(x_i,C_i)$$ takes a simple bilinear form as follows $$f_i(x_i,C_i)=\begin{cases} 1.5-C_i&,\quad (x_i,C_i)\in I_{i,0}\\ 1.5-x_i&,\quad (x_i,C_i)\in I_{i,1}\\ 1&,\quad (x_i,C_i)\in I_{i,2}\\ 1-x_i+C_i&,\quad (x_i,C_i)\in I_{i,3}\\ 1+x_i-C_i&,\quad (x_i,C_i)\in I_{i,4}\\ 1&,\quad (x_i,C_i)\in I_{i,5}\\ 0.5+x_i&,\quad (x_i,C_i)\in I_{i,6}\\ 0.5+C_i&,\quad (x_i,C_i)\in I_{i,7} \end{cases},$$ which yields that $$\frac{\partial^2 f_i(x_i,C_i)}{\partial x_i^2}=\frac{\partial^2 f_i(x_i,C_i)}{\partial C_i^2}=0$$ for $$(x_i,C_i)\in I_{i,j}$$ for a fixed $$j\in \{0,1,\cdots,7\}$$. Hence, we have proved the following statement:

The function $$f(\mathbf{x},\mathbf{C})$$ is smooth for $$(\mathbf{x},\mathbf{C})\in \bigotimes_{i=1}^n I_{i,j_i}$$ where $$j_i\in \{0,1,\cdots 7\}$$, $$\bigotimes$$ is the cartesian set product and $$\frac{\partial^2 f(\mathbf{x},\mathbf{C})}{\partial x_i^2}=\frac{\partial^2 f(\mathbf{x},\mathbf{C})}{\partial C_i^2}=0\quad,\quad 1\le i\le n.$$

An interesting corollary of the previous statement is that the Hessian matrix of $$f(\mathbf{x},\mathbf{C})$$ is trace-free over each of the cartesian products $$\bigotimes_{i=1}^n I_{i,j_i}$$. Since the trace of a square matrix is the summation of its eigenvalues, we have proved that the summation of the eigenvalues of the Hessian matrix of $$f(\mathbf{x},\mathbf{C})$$ is equal to zero. This means that the Hessian matrix is either a zero matrix or has at least one positive and one negative eigenvalue.

The case where the Hessian matrix is zero is easy to investigate. For this case, the function $$f(\mathbf{x},\mathbf{C})$$ has to be linear. This happens only when all, except at most one of the $$j_i$$ indices are $$\in \{2,5\}$$. Now we conclude our effort:

The function $$f(\mathbf{x},\mathbf{C})$$ is linear for $$(\mathbf{x},\mathbf{C})\in \bigotimes_{i=1}^n I_{i,j_i}$$ when all, except at most one of the $$j_i$$ indices are $$\in \{2,5\}$$, and is strictly non-convex elsewhere $$\blacksquare$$

For example, when $$N=2$$, the function $$f(\mathbf{x},\mathbf{C})$$ is linear over the following intervals $${ I_{1,2}\times I_{2,2}, \\ I_{1,2}\times I_{2,5}, \\ I_{1,5}\times I_{2,2}, \\ I_{1,5}\times I_{2,5}, \\ I_{1,2}\times I_{2,j} \quad,\quad j\in\{0,1,3,4,6,7\}, \\ I_{1,j}\times I_{2,2} \quad,\quad j\in\{0,1,3,4,6,7\}, \\ I_{1,5}\times I_{2,j} \quad,\quad j\in\{0,1,3,4,6,7\}, \\ I_{1,j}\times I_{2,5} \quad,\quad j\in\{0,1,3,4,6,7\}, }$$ and is non-convex elsewhere.

• for the $N=2$ doesn't your statement say $f(\mathbf{x}, \mathbf{C})$ is linear everywhere? your statement $I_{1,2} \times I_{2,j} \quad, j \in \{0,1,3,4,6,7\}$ excludes $\{2,5\}$ but it is included above?? Commented May 3, 2023 at 17:55
• No. This is because the function equation is not necessarily equal over all of the sets $I_{1,2}\times I_{2,j}$. Commented May 3, 2023 at 19:30

Unfortunately, $$f$$ is not convex, even "locally", as soon as $$N \geq 2$$.

Heuristically, this boils down to the fact that $$(x,y) \mapsto xy$$ is not convex on $$\mathbb{R}^2$$ (see this question).

To see how this comes into play, take $$N = 2$$, $$C_1 = C_2 = 0.7$$ as in your example, and consider the region $$(x_1, x_2) \in [0.5, 0.7]^2$$. Simplifying the absolute values in this region, we obtain $$f(x) = (0.5 + x_1) (0.5 + x_2).$$ While each factor is affine (and thus trivially convex), the product looses the convexity. In the interior of the region $$(0.5,0.7)^2$$, $$f$$ is smooth, so you can determine its convexity by looking at its Hessian. You obtain $$D^2 f(x) = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix},$$ which has a negative determinant, so $$f$$ cannot be convex.