Consider a finite set $A \subseteq \mathbb{N} \times \mathbb{N} \times \mathbb{R}$. Minimize $$\sum_n \left( \max_{(n',i,a) \in A, n=n'} (a + x_i) + \max_{(n',i,a) \in A, n=n'} (-a - x_i) \right)$$ over $x \in \mathbb{R}^m$, where $m$ is large enough.
This problem is convex since the formula is sum of maximum of convex (or affine) functions. Thus a local minimum is a global minimum. It seems there might be an iterative greedy algorithm that minimizes the goal little by little and eventually reaches a local minimum in polynomially many steps.
If you are uncomfortable with its formulation with $\mathbb{R}$, just replace $\mathbb{R}$ with $\mathbb{Z}$. Does it change anything? I am not sure, but probably not.
The decision version of this problem would ask "is the minimum less than or equal to a given $k$?". It is NP since $x \in \mathbb{R}^m$ would work as a polynomial length certificate.
My question: Is it NP-complete? Is it a known problem?
Thank you very much in advance. My expectation is that it is a known problem. It looks like a famous problem. I just don't know the name of the problem. It would simply answer my question if you leave me a proper search keyword so that I could search it on the internet.