The motivation of the question is the following:
Let $P$ be a set of $n$ points in $\mathbb{R}^d$. Consider the following objective(convex and differentiable) function $f:\mathbb{R}^d\rightarrow [0,\infty)$.
$f(c) = \sum_{p\in P}\Vert p-c\Vert^2$.
It is well known that the mean $\mu(P)=\frac{1}{n}\sum_{p\in P}p$ minimizes the function over $\mathbb{R}^d$. More generally, for any $c\in \mathbb{R}^d$ the following is true
$f(c) = f(\mu(P)) + n\Vert c-\mu(P)\Vert^2$.
There are various ways to prove this. For example we can compute the gradient
$\nabla f(c) = \sum_{p\in P}2(c-p)$
Since $f$ is convex, for $c^\star = \mu(P)$, we have $\nabla f(c^\star) = 0$. The Hessian is $\nabla^2 f(c)=2nI$, $I$ being the Identity matrix. Now consider the second order approximation
$f(c) = f(c^\star) + \langle \nabla f(c^\star), c-c^\star\rangle + \frac{1}{2}(c-c^\star)^T\nabla^2f(\theta)(c-c^\star) = f(c^\star) + n\Vert c-c^\star\Vert^2$, for some $\theta\in [c,c^\star]$.
Coming to the main question
Let $\mathcal{P} = \left\{P_1,\cdots,P_n \right\}$ be a family of $n$ finite sets in $\mathbb{R}^d$. Consider the following (convex) function
$F(c) = \sum_{j\in[n]}\max_{p\in P_j}\Vert p-c\Vert^2$
Given $c\in\mathbb{R}^d$, let $p_j\in P_j$ such that $\Vert p_j-c\Vert^2=\max_{p\in P_j}\Vert p-c\Vert^2$. Then one can show that $G(c) = \sum_{j\in[n]}2(c-p_j)$ is a valid "sub gradient" of $F$ at $c$ ($\in \partial F(c)$). It is well known that $c^\star$ minimizes $F$ iff $0\in \partial F(c^\star)$. Therefore, $c^\star = \frac{1}{n} \sum_{j\in[n]} p_j$ is a minimizer of $F$. Now I want find out how changing the point effects the function(similar to the above). For that one needs an analogue of Hessian for non differentiable functions, where the "sub gradient" exists.
So is there a way to compute something similar to the Hessian, when the function is non-differentiable?
PS. After Googling, I found the paper GENERALIZED HESSIAN PROPERTIES OF REGULARIZED NONSMOOTH FUNCTIONS, it may be of importance.
UPDATE: 29/01/2020
It seems to me that $c^\star = \frac{1}{n} \sum_{j\in[n]} p_j$ may not be a minimizer of $F$, because $G(c)$ may not be zero for any $c\in \mathbb{R}^d$ (there may not be any point which is the "mean" of the points farthest in the sets). This is interesting.
