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.

Not the answer you're looking for? Browse other questions tagged .