4
$\begingroup$

$$ \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$.

$\endgroup$
3
  • $\begingroup$ how is it possible for a non-constant function to be non-decreasing and have identical values at 0 and $n+1$? $\endgroup$ May 18, 2020 at 17:55
  • $\begingroup$ @Carlo Beenakker my bad f is non-decreasing over $\{ 1, \ldots ,n\}$ $\endgroup$
    – user83947
    May 18, 2020 at 17:58
  • $\begingroup$ a linearly increasing $f(i)=ix/n$ would give $(1+1/n)x$ for the sum; can one do better? $\endgroup$ May 18, 2020 at 19:18

1 Answer 1

0
$\begingroup$

$\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$.

$\endgroup$
2
  • 1
    $\begingroup$ Replaced the previous version of the answer by hopefully a cleaner one. $\endgroup$ May 19, 2020 at 4:42
  • 1
    $\begingroup$ Replaced the answer by a simpler version. $\endgroup$ May 19, 2020 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.