Does this linear combination of vector norms describe a convex set?

Question

Consider the surface identified by the following implicit equation \begin{equation} |\vec{x}|+|\vec{y}|-|\vec{z}|-|\vec{x}+\vec{y}-\vec{z}|=0, \end{equation} with $(\vec{x},\vec{y},\vec{z})\in\mathbb{R}^{3N}$ and $|\cdot |$ being the Euclidean norm in $\mathbb{R}^N$. Is such a surface convex in $\mathbb{R}^{3N}$? Are there some regions of $\mathbb{R}^{3N}$ in which the restriction of the surface to the region is convex?. Observe that this surface can be obtained by intersecting the following cones: \begin{align} t_x&=|\vec{x}|, \quad t_y=|\vec{y}|, \\ t_z&=|\vec{z}|, \quad t_x+t_y-t_z=|\vec{x}+\vec{y}-\vec{z}|, \end{align} where now $(t_x,\vec{x},t_y,\vec{y}, t_z, \vec{z})\in \mathbb{R}^{3(N+1)}$.

Answer 1

You say that the case $N=1$ is "trivially convex".

I'm sorry but I don't agree at all.

I have been computing by hand at first, working at the elimination of the different absolute values, octant by octant, obtaining, as you say, one linear relationships, but not relationships with inequalities. Therefore the 3D set is a surface (S), not a volume, made of 8 planar sectors (6 with a 90° opening, 2 with a 60° opening) assembled as a double umbrella (symmetrical with respect to the origin).

Therefore (S) is not eligible to be a convex set: the midpoint of 2 points of (S), is - most often - not in (S). If you restrict (S) to one of these 8 planar sectors, you have a convex set...

Then, I have written a Matlab program (see below) that has given this, confirming my computations:

clear all;close all;hold on;axis equal
f= @(x,y,z)(abs(x)+abs(y)-abs(z)-abs(x+y-z));
a=3; N = 100; W=4;L='linewidth';
plot3([-a,a],[0,0],[0,0],L,W); % x axis
plot3([0,0],[-a,a],[0,0],L,W);
plot3([0,0],[0,0],[-a,a],L,W);
plot3([a,-a],[0,0],[a,-a],L,W);
plot3([0,0],[a,-a],[a,-a],L,W);
u = linspace(-a,a, N);
[X, Y, Z] = meshgrid(u, u, u);
D = f(X, Y, Z);
isosurface(X,Y,Z,D,-0.01);% levelset of f for value v=-0.01
view([-126,12])
xlabel('x');
ylabel('y');
zlabel('z');

I f we consider now the region defined by $|x|+|y|-|z|-|x+y-z|<0$ we will get the interior of the umbrellas, with "nice level sets". See for example below the level set

$$|x|+|y|-|z|-|x+y-z|=-0.5$$