Local convexity of a function containing norms

Question

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!

Answer 1

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.

Answer 2

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.