Is $g(x_1, x_2) = |\alpha - x_1| + |\max \{\alpha, x_1\} + \beta - x_2|$ convex?

Question

Let $\alpha \geq 0$ and $\beta \geq 0$. Can we prove or disprove the following function is convex on $x_2 \geq x_1 \geq 0$? $$ g(x_1, x_2) = |\alpha - x_1| + |\max \{\alpha, x_1\} + \beta - x_2| $$

My Approach: In simulation, it seems that the function is convex but I couldn't rigorously prove it. Any help would be appreciated.

P.S.: A similar question is asked here when $|\cdot|$ is replaced with $(\cdot)^2$ and a counterexample is given to show that it is not convex. But that counterexample does not work for the case of $|\cdot|$.

Answer 1

I deleted my previous solution since it is complicated. I give another solution here.

Proof: We have (cf. @user125932's answer) \begin{align} g(x_1, x_2) = \left\{\begin{array}{ll} -x_1 - x_2 + 2\alpha + \beta & x_1 \le \alpha, x_2 \le \alpha + \beta \\ -x_1 + x_2 - \beta & x_1 \le \alpha, x_2 > \alpha + \beta\\ 2x_1 - x_2 - \alpha + \beta & x_1 > \alpha, x_2 \le x_1 + \beta \\ x_2 - \alpha - \beta & x_1 > \alpha, x_2 > x_1 + \beta. \end{array} \right. \end{align} It is easy to verify that $$g(x_1, x_2) = \max \{-x_1 - x_2 + 2\alpha + \beta, \ -x_1 + x_2 - \beta, \ 2x_1 - x_2 - \alpha + \beta, \ x_2 - \alpha - \beta\}.$$ Thus, $g(x_1, x_2)$ is convex (see Example 3.5, page 80, in [1]).

[1] Boyd and Vandenberghe, "Convex optimization". http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

Answer 2

Here is an idea.

Except for the lines $x_1=\alpha$, $x_2 - x_1 = \beta$ and $x_2 = \alpha + \beta$ the function coincides with appropriate (and apparent) affine functions in the connected regions that remain. Since these regions define an open set whose boundary precisely consists of the lines just identified, the function is convex and differentiable in each region. Moreover, you can adapt this answer to conclude that $f$ satisfies Jensen inequalities in the closure of every region. Then you should check the behavior of $f(x + \theta(y-x))$ when moving from one region to the other, i.e, when $x$ and $y$ are in different regions. Since there are just a few of them, and they are easly identifiable plyhedra, this checking should be feasible and the answer to your question might emerge.

Answer 3

The function is convex. First write the function as $$g(x_1, x_2) = \cases{ -x_1-x_2+2\alpha+\beta & $x_1 \leq \alpha$, $x_2 \leq \alpha+\beta$\\ -x_1+x_2-\beta & $x_1 \leq \alpha$, $x_2 \geq \alpha+\beta$\\ 2x_1-x_2-\alpha+\beta & $x_1 \geq \alpha$, $x_2 \leq x_1+\beta$\\ x_2-\alpha+\beta & $x_1 \geq \alpha$, $x_2 \geq x_1+\beta$}$$

Note that $g$ is continuous (by its original definition) and piecewise linear, in that we can partition its domain into finitely many (closed, convex) regions, such that it is affine on each region.

Let's take a diversion to find a condition we'll use to verify that $g$ is convex. A function $f : D \to \mathbb{R}$ defined on a convex domain $D \subset \mathbb{R}^d$ is convex iff the function $f_{x, y} : [0, 1] \to \mathbb{R}$ given by $f_{x, y}(t) = f((1-t)x + ty)$ is convex for any $x, y \in D$. But when $f$ is piecewise linear, so is any $f_{x, y}$, and in this case it is easy to prove that $f_{x, y}$ is convex iff its sequence of slopes (one for each successive region of its domain) is increasing. Say that $f$ has regions $R_1, \dots, R_n$, where $f(u) = v_i \cdot u + c_i$ on $R_i$. Then if the line $L_{x, y} = \{(1-t)x + ty \mid t \in [0, 1]\}$ intersects the successive regions $R_{i_1}, \dots, R_{i_k}$ (going from $t = 0$ to $t = 1$), then the sequence of slopes is $v_{i_1} \cdot (y-x), \dots, v_{i_k} \cdot (y-x)$, so we must check that this sequence is increasing for any $x, y$.

To check this, we can equivalently check the following simpler condition: that whenever $x' \in R_i$ and $y' \in R_j$, we have $v_i \cdot (y'-x') \leq v_j \cdot (y'-x')$. This condition is clearly necessary, and is sufficient since then for any $1 \leq r < s \leq k$, taking $x' = (1-t_1)x + t_1y \in R_{i_r}$ and $y' = (1-t_2)x + t_2y \in R_{i_s}$ (where $t_1 < t_2$), we have that $v_{i_r} \cdot (y' - x') \leq v_{i_s} \cdot (y'-x')$, i.e. that $(t_2 - t_1)(v_{i_r} \cdot (y-x)) \leq (t_2 - t_1)(v_{i_s} \cdot (y-x))$ hence $v_{i_r} \cdot (y-x) \leq v_{i_s} \cdot (y-x)$, meaning the sequence of slopes for any $L_{x, y}$ is increasing as desired. But $v_i \cdot (y-x) \leq v_j \cdot (y-x)$ iff $(v_j - v_i) \cdot x \leq (v_j - v_i) \cdot y$, so we can restate our simpler condition as the following result:

$f$ is convex if and only if for every $R_i, R_j$, we have $\sup_{x \in R_i} (v_j - v_i) \cdot x \leq \inf_{x \in R_j} (v_j - v_i) \cdot x$.

and in fact this only needs to be checked for neighboring $R_i, R_j$, namely those with $R_i \cap R_j \neq \varnothing$.

We can now use this to check that $g$ is convex. Label the regions $R_1, R_2, R_3, R_4$ in the same order as listed above, so $v_1 = (-1, -1), v_2 = (-1, 1), v_3 = (2, -1), v_4 = (0, 1)$. Checking, we see that \begin{align*} \sup_{x \in R_1} (v_2 - v_1) \cdot x &= 2\alpha+2\beta &= \inf_{x \in R_2} (v_2 - v_1) \cdot x \\ \sup_{x \in R_1} (v_3 - v_1) \cdot x &= 3\alpha &= \inf_{x \in R_3} (v_3 - v_1) \cdot x \\ \sup_{x \in R_1} (v_4 - v_1) \cdot x &= 3\alpha+2\beta &= \inf_{x \in R_4} (v_4 - v_1) \cdot x \\ \sup_{x \in R_2} (v_3 - v_2) \cdot x &= \alpha-2\beta &= \inf_{x \in R_3} (v_3 - v_2) \cdot x \\ \sup_{x \in R_2} (v_4 - v_2) \cdot x &= \alpha &= \inf_{x \in R_4} (v_4 - v_2) \cdot x \\ \sup_{x \in R_3} (v_4 - v_3) \cdot x &= 2\beta &= \inf_{x \in R_4} (v_4 - v_3) \cdot x \end{align*} so $g$ is indeed convex.