Let $f : \Bbb R^n \to R \cup\{+ \infty\}$ be a piece-wise convex function, in the sense that $f$ admits the following representation (for simplicity consider only two pieces)
$$f(x)=\left\{\begin{matrix}
f_1 (x)& x \in P_1\\
f_2 (x)& x \in P_2\\
+ \infty& \rm{otherwise}
\end{matrix}\right.$$
Where $f_i$ are smooth and convex on whole $\Bbb R^n$ , and $P_i$ are convex polyhedrals whose union is convex polyhedral as well.
I'm looking for conditions on $f_1 , f_2 $ which characterize the convexity of $f(x)$.
As an example of piecewise convex function which is not convex ; $f(x) = – |x|.$.In this example the monotonicity of the slopes of pieces fail. So I believe this characterization may pass through the monotonicity of gradients of pieces.
Even In particular cases when $f_i$ are linear or quadratic what can we say?
Best Answer
You basically need that the 'kink' between $f_1$ and $f_2$ has the correct sign.
Let us denote $\Gamma = P_1 \cap P_2$. This should be a $n-1$-dimensional set possessing a normal vector $\nu \in \mathbb R^n$ pointing from $P_1$ to $P_2$. Then, you have to check that $$ \Bigl( \nabla f_2(x) - \nabla f_1(x) \Bigr)^\top \nu \ge 0$$ holds for all $x \in \Gamma$.
To see that this condition is necessary and sufficient, pick $p_1 \in P_1$ and $p_2 \in P_2$. Then, the segment $[p_1, p_2]$ intersects $\Gamma$ in one $x$. The above condition means that the derivative along this segment is increasing and therefore $f$ is convex along this segment. Finally, one can use that convexity is equivalent to convexity along all segments.