# Is the minimum of a constraint optimization problem differentiable in the constraint parameter?

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.

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:

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

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. 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. All these pairs are as follows: \begin{aligned} (u_1(t),t/2)&\quad\text{if}\quad -4 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_{**})$$.

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

• 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... Commented Apr 26, 2020 at 8:24
• 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... Commented Apr 26, 2020 at 8:25
• 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. Commented Apr 26, 2020 at 8:25
• @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)$. Commented Apr 26, 2020 at 14:31
• 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. Commented Apr 26, 2020 at 14:32