Problem
This question is motivated by this answer, which represents $k$-th largest element of a set $\{a_1,a_2,\cdots,a_n\}$ (elegantly) as $$ \min _ { I \subseteq [ n ] \atop \vert I\vert = n - k + 1 } \max _ { i \in I } a _ { i } $$ Reflecting that one condition (see page3 of slide) for convex piecewise linear function is that it could be represented as $$ f ( x ) = \max _ { i = 1 , \ldots , m } \left( a _ { i } ^ { T } x + b _ { i } \right) $$ I am now wondering if the function of finding $k$-th largest element of set $\{\mathbf{w}_1^T\mathbf{x}.\mathbf{w}_2^T\mathbf{x}.\cdots,\mathbf{w}_n^T\mathbf{x}\}$ is still piecewise linear. For example, median function $f(\mathbf{x})=\text{median}(\mathbf{w}_1^T\mathbf{x}.\mathbf{w}_2^T\mathbf{x},\mathbf{w}_3^T\mathbf{x})$.
It is piecewise linear, but not convex, assuming that $n$ is finite. You can prove this by induction on $k$. Let us define a few sets to show the first induction steps: $$S =\{a_i \}$$ $$T =\{a_i + a_j : i < j \}$$ $$U =\{a_i + a_j + a_k : i < j < k \}$$ Let $a^{(1)} = \max S$ denote the largest element in the set, which is piecewise linear. The second largest element is $a^{(2)} = \max T - a^{(1)}$, which is the difference of two convex piecewise functions, which is piecewise linear. The third largest element is $a^{(3)} = \max U - a^{(2)}$, etc.