Minimization of a discrete valued function $$
\min_{f} \sum_{i=1}^n \max \left( 0, 2f(i) - f(i-1) -f(i+1)\right),
$$
where the minimum is taken over all the functions $f$ from  $\{0,1,2,\ldots,n+1\}$ to $[0,x]$, $x <1$, such that $f$ is non-decreasing over $\{1,2,\ldots,n\}$,  $f(0)=f(n+1)=0$, and $f(n)=x$.
 A: $\newcommand{\De}{\Delta}$Letting 
\begin{equation}
 \De^2f_i:=2f(i)-f(i-1)-f(i+1),
\end{equation}
we rewrite the target of the minimization as 
\begin{equation}
s(f):=\sum_{i\in[n]}(\De^2f_i)_+, 
\end{equation}
where 
$[n]:=\{1,\dots,n\}$ and $u_+:=\max(0,u)$ for real $u$. 
Let now $f$ be a minimizer of $s(\cdot)$ and let 
$g$ be the least concave majorant of $f$ on the set $\{0,\dots,n+1\}$. Then $g$ satisfies all the conditions on $f$: $g$ is non-decreasing on the set $[n]$,  $g(0)=g(n+1)=0$, and $g(n)=x$. Let 
\begin{equation}
 J:=\{j\in[n]\colon g(j)=f(j)\}. 
\end{equation}
Then $(\De^2g_i)_+=\De^2g_i=0\le(\De^2f_i)_+$ for $i\in[n]\setminus J$. Also, noting that $g\ge f$, for $i\in J$ we have 
\begin{multline}
 \De^2g_i=2g(i)-g(i-1)-g(i+1) \\ 
 =2f(i)-g(i-1)-g(i+1) \\ 
 \le2f(i)-f(i-1)-f(i+1)=\De^2f_i, 
\end{multline}
whence $(\De^2g_i)_+\le(\De^2f_i)_+$. 
So, $(\De^2g_i)_+\le(\De^2f_i)_+$ for all $i\in[n]$ and hence $s(g)\le s(f)$. So, $g$ is also a minimizer of $s(\cdot)$. Moreover, since $g$ is concave, we have $\De^2g_i\ge0$ for all $i\in[n]$ and therefore 
\begin{multline}
s(g)=\sum_{i\in[n]}\De^2g_i \\ 
=g(1)-g(0)+g(n)-g(n+1) \\ 
=g(1)+g(n)=g(1)+x.   
\end{multline}
Further, the concavity of $g$ and the conditions $g(0)=0$ and $g(n)=x$ imply $g(1)\ge x/n$. It follows that $s(g)\ge x/n+x$. 
On the other hand, the function $h$ given by $h(i):=xi/n$ for $i\in[n]$ with $h(n+1)=0$ satisfies all the conditions on $f$, and $s(h)=x/n+x$. 
We conclude that 

the minimum in question is $x/n+x$. 

