Question:
Any valid norm is convex. Given $A \in \mathbb{R}^{n \times n}$, $y \in \mathbb{R}^n$, I am wondering under what conditions on $y$ and $A$ (if any) the functions $$ \|y- Ax\|_1 $$ and $$ \| y- A x \|_\infty, $$ are affine over $x \geq 0$.
I am only interested in the non-trivial case, i.e., where $A$ is not a non-negative/non-positive matrix.
Assumptions (optional, if helpful) :
- You can assume that $\mathsf{sign}(y) \in \{\pm 1\}^n$ is known.
- You can assume that $A \succeq 0$.
What I have tried:
For the $\ell_1$ norm, from the dual norm characization: $$ \| y - Ax \|_1 = \sup_{u : \|u\|_\infty \leq 1 } u^\top(y - Ax), $$ I think that the norm is affine over $x \geq 0$ if $$ A^\top \textsf{sign}(y) \leq 0, $$ but I'm uncertain if this is correct. I also don't know if similar conditions hold for $\| y- A x\|_\infty$.