1
$\begingroup$

Let $h:\mathbb R^{>0}\to \mathbb R^{\ge 0}$ be a smooth function, satisfying $h(1)=0$, and suppose that $h(x)$ is strictly increasing on $[1,\infty)$, and strictly decreasing on $(0,1]$.

Let $s>0$ be a parameter, and define $ F(s)=\min_{xy=s,x,y>0} h(x)+ h(y)$.

If I am not mistaken, the map $s \to F(s)$ is continuous.

Question: Is $F$ differentiable everywhere on $(0,\infty)$? We cannot expect more than $F \in C^1$ for sure, as the example below shows.

There are examples where the minimum points cannot be chosen in a differentiable manner in $s$, yet $F$ is still differentiable:

Take $h(x)=(x-1)^2$. Then

$$ F(s) = \begin{cases} 2(\sqrt{s}-1)^2, & \text{ if }\, s \ge \frac{1}{4} \\ 1-2s, & \text{ if }\, s \le \frac{1}{4} \end{cases} $$ is $C^1$, and in particular, differentiable at $s=\frac{1}{4}$, even though the points of minima $(a(s),b(s))$ are given by $$ \begin{cases} \sqrt{s}, & \text{ if }\, s \ge \frac{1}{4} \\ \frac{1}{2}(1 \pm \sqrt{1-4s}), & \text{ if }\, s \le \frac{1}{4} \end{cases} $$ which is not differentiable at $s=\frac{1}{4}$. These points of minima are unique up two permuting $a$ and $b$.

Note that $F \in C^1$, but is not twice differentiable at $s=\frac{1}{4}$, so we had some loss of regularity, as we started with smooth objective function, and a smooth constraint.

Is there any "standard theory" for when the minimum of a contraint optimization problem differentiable in the parameter? I tried to google in various ways, but couldn't find the relevant material I guess.

$\endgroup$
1

1 Answer 1

2
+50
$\begingroup$

The answer to your question is: No, in general $F$ is not differentiable everywhere on $(0,\infty)$.

First, to simplify the notations a bit, consider the change of variables $x=e^u$, $y=e^v$, $s=e^t$, $g(u)=h(x)=h(e^u)$, and $G(t)=F(s)=F(e^t)$, induced by the smooth increasing correspondence $\ln\colon(0,\infty)\to\mathbb R$.

Then the problem can be rewritten as follows:

Let $g\colon\mathbb R\to\mathbb R$ be a smooth function with $g(0)=0$, and suppose that $g$ is strictly increasing on $[0,\infty)$ and strictly decreasing on $(-\infty,0]$. For each real $t$, let $$G(t):=\min_{u\in\mathbb R}[g(u)+g(t-u)].$$ Is then $G$ differentiable everywhere on $\mathbb R$?

Note that any minimizer $u$ of $g(u)+g(t-u)$ satisfies the equation $g'(u)=g'(t-u)$. Therefore, with the implicit function theorem in mind, the main idea -- in order to produce a promised counter-example -- is to get a function $g$ with the the equation $g'(u)=g'(t-u)$ having, for some real $t$, appropriate multiple roots $u$.

It turns out that $$g(u):=\frac{u^6}{6}+\frac{2 u^5}{5}-\frac{3 u^4}{4}-\frac{4 u^3}{3}+2 u^2,$$ with $g'(u)=u(u-1)^2(u+2)^2$ will do. Indeed, first of all here, clearly this function $g$ satisfies all the conditions: $g$ is smooth, $g(0)=0$, $g$ is strictly increasing on $[0,\infty)$, and strictly decreasing on $(-\infty,0]$. Moreover, for this function $g$ we have $$G(t)=\begin{cases} G_1(t) & \text{ if }t\geq 2\text{ or } t_*\leq t\leq \frac{4}{5}\text{ or }t\leq -4, \\ G_2(t) & \text{otherwise}, \end{cases} $$ where $$G_1(t):=\frac{1}{960} \left(5 t^6+24 t^5-90 t^4-320 t^3+960 t^2\right),$$ $$G_2(t):=\frac{1}{60} \left(55 t^6+264 t^5+390 t^4+60 t^3-345 t^2-5 \sqrt{(t+1)^6 \left(5 t^2+6 t-7\right)^3}-300 t+225\right),$$ and $t_*=-1.958\ldots$ is the only negative root of the polynomial $P(t):=55 t^4+176 t^3+156 t^2-32 t-148$. Finally, $${G^{\,}}'(t_*+)={G^{\,}}'_1(t_*)=-3.995\ldots\ne-0.0492\ldots={G^{\,}}'_2(t_*)={G^{\,}}'(t_*-).$$ So, $G$ is not differentiable at $t_*$, as claimed.


Here are the graphs $\{(t,g'(t))\colon-2.5<t<1.5\}$:

enter image description here

and $\{(t,{G^{\,}}'(t))\colon t\in(-3,3)\setminus\{t_*\}\}$:

enter image description here


A few more details: Recall the main idea: that (i) any minimizer $u$ of $$H_t(u):=g(u)+g(t-u)$$ satisfies the equation $g'(u)=g'(t-u)$ and (ii) we want the equation $g'(u)=g'(t-u)$ to have, for some real $t$, appropriate multiple roots $u$. Indeed, then we will have \begin{equation*} G(t)=H_t(u_j(t))\quad\text{for}\quad t\in T_j \end{equation*} for some natural $k$ and all $j=1,\dots,k$, where the $u_j$'s are different branches of the roots $u$ of the equation $g'(u)=g'(t-u)$ and the $T_j$'s form a subdivision of the real line; if $g$ is algebraic, then the $T_j$'s will be intervals, say $[t_{j-1},t_j]$. Then for $t\in(t_{j-1},t_j)$
\begin{equation*} G\,'(t)=g'(u_j(t))u'_j(t)+g'(t-u_j(t))(1-u'_j(t))=g'(t-u_j(t)). \end{equation*} So, there is no reason for $G\,'(t_j-)=G\,'(t_j+)$ if $j<k$. That is, in the presence of multiple roots $u$ of the equation $g'(u)=g'(t-u)$, it should be expected that $G\notin C^1$. What is then a bit surprising to me (and what I cannot explain) is that in most of the simple cases I have considered we have $G\in C^1$.

Note also that $t/2$ is always a ("trivial") root $u$ of the equation $g'(u)=g'(t-u)$. Further, if $u$ is a root of $g'(u)=g'(t-u)$, then $t-u$ is obviously a root, too. So, we should be interested in the pairs $(u,v)$ of roots of $g'(u)=g'(t-u)$ such that $u<v\le t/2$. All these pairs are as follows: \begin{equation} \begin{aligned} (u_1(t),t/2)&\quad\text{if}\quad -4<t\leq -2,\\ (u_1(t),u_2(t))\text{ or }(u_1,t/2)\text{ or }(u_2,t/2)&\quad\text{if}\quad -2<t<-t_{**},\\ (u_1(t),t/2)&\quad\text{if}\quad t=t_{**},\\ (-2,-1/2)&\quad\text{if}\quad t=-1,\\ (u_1(t),t/2)&\quad\text{if}\quad 4/5<t<2, \end{aligned} \tag{1} \end{equation} where $$t_{**}:=-(3+2\sqrt{11})/5=-1.926\ldots,$$ $u_1(t)$ is the smallest real root of the polynomial $$Q_t(u):=u^4-2 t u^3+\left(4 t^2+4 t-3\right) u^2+t \left(-3 t^2-4 t+3\right) u+\left(t^2+t-2\right)^2,$$ and $u_2(t)$ is the second smallest real root of the polynomial $Q_t(u)$ (for $t$ in the corresponding intervals); we see that such pairs $(u,v)$ exist only for $t\in(-4,t_{**}]\cup\{-1\}\cup(4/5,2)$. Below are the graphs (left panel) of the functions $u_1$ (red), $u_2$ (green), and $t\mapsto u_3(t):=t/2$ (blue), with the fragments (right panel) of these graphs over the most interesting interval, $(-2,t_{**})$.

enter image description here

It is plausible that the discontinuity of $G\,'$ occurs at a point $t$ where some of the distinct branches $H_t(u_i(t))$ ($i=1,2,3$) meet, that is, at a point $t$ such that $H_t(u_i(t))=H_t(u_j(t))$ for some distinct $i$ and $j$ in the set $\{1,2,3\}$. In fact, $$\{t\in\mathbb R\colon H_t(u_1(t))=H_t(u_3(t))\}=\{-4,4/5,2,t_*\}$$ (with $t_*=-1.958\ldots$ as before), $$\{t\in\mathbb R\colon H_t(u_2(t))=H_t(u_3(t))\}=\{-4,-2,4/5,2\},$$ $$\{t\in\mathbb R\colon H_t(u_1(t))=H_t(u_2(t))\}=[-4,-2)\cup\{t_{**},-1\}\cup[4/5,2];$$ concerning the latter two results of the three, note that $u_2(t)$ actually appears in the description (1) of the pairs of roots of $g'(u)=g'(t-u)$ of interest only for $t\in(-2,-t_{**})$.

The actual point of discontinuity of $G\,'$ is $t_*$, as was noted before. Here, one may also note that $t_*=-1.958\ldots$ is in the most interesting interval, $(-2,t_{**})=(-2,-1.926\ldots)$.

$\endgroup$
9
  • $\begingroup$ Thank you very much. This is a very interesting solution. If I am not mistaken, I was able to verify that $G$ is differentiable at all the transition points except at $t=t_*$, although twice differentiable at none of them. I wonder whether this can be deduced directly somehow, or is it surprising? In particular, I am trying to understand what property distinguishes the transition point $t=t_*$ from the other transition points. Is it special because only there the equation $g'(u)=g'(t-u)$ has multiple solutions $u$, like you mentioned at the beginning? I guess you tried to find... $\endgroup$ Commented Apr 26, 2020 at 8:24
  • $\begingroup$ a function such that the minimizers will change non-smoothly from different directions of the transition point, but as my example in the question shows, this is certainly not enough. To summarize- I would like to have a better idea about how you came up with this counter-example, since the fact that the minimum points cannot be chosen in a differentiable manner does not in general imply non-differentiability of the minimal value function. Finally, I find it very interesting that there are multiple transition points, as this answers... $\endgroup$ Commented Apr 26, 2020 at 8:25
  • $\begingroup$ this question... as well. I must say the phenomena you discovered is very non-trivial for me. I wasn't expecting such complexity. Thank you again for all your many insights and help. $\endgroup$ Commented Apr 26, 2020 at 8:25
  • 1
    $\begingroup$ @AsafShachar : I am glad you liked this answer. As was mentioned there, the main idea is that the equation $g'(u)=g'(t-u)$ should have multiple roots $u$ for some real $t$. Next, for some reasons that I don't remember now, it occurred to me that for some $t$ the equation $g'(u)=g'(t-u)$ should have a root $u$ such that $u$ and $t-u$ be of the opposite signs. But the monotonicity pattern of $g$ implies that $g'\le0$ on $(-\infty,0]$ and $g'\ge0$ on $[0,\infty)$. $\endgroup$ Commented Apr 26, 2020 at 14:31
  • 1
    $\begingroup$ Previous comment continued: So, I thought, there must be real $u$ and $v$ such that $u<0<v$ and $g'(u)=g'(v)=0$. I then tried $g'(u)=u(u-1)^2(u+1)^2$, but it did not work. After that, I tried $g'(u)=u(u-1)^2(u+2)^2$, and it worked. $\endgroup$ Commented Apr 26, 2020 at 14:32

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.