In the context of my research, I've encountered the problem described below. I wonder if this is a standard problem in convex optimization or linear programming and would appreciate any comments. I was searching for a solution online (for example here) but could not find where a similar problem is considered.
Let a function $F(x):\mathbb{R}^n \to \mathbb{R}$ given by $$F(x): = \max_{i=1,\ldots, N} \{ v_i \cdot x +b_i\} \tag{*}, $$ where for each $i$, $ v_i \in \mathbb{R}^n, b_i \in \mathbb{R}$ and '$\cdot$' is dot product.
$F$ is a continuous convex piecewise linear function, each linear region of $F$ is a convex polyhedron (a linear region is a connected component over which $F$ is differentiable.)
The representation of $F(x)$ as in (*) is known. Given a point $x_0 \in \mathbb{R}^n$, I want to find a description of the linear region (polyhedron) that $x_0$ is lying within (assuming $x_0$ is not on the boundary of two linear regions).
I'm looking for algorithm and trying to see what the complexity of this algorithm is (in terms of the number of hyperplanes $N$ that define $F$)