# When is the optimum of an optimization problem convex in the constraint parameter?

Let $$f:(0,\infty) \to [0,\infty)$$ be a $$C^1$$ function satisfying $$f(1)=0$$. Suppose that $$f(x)$$ is strictly increasing on $$[1,\infty)$$ and strictly decreasing on $$(0,1]$$, and that $$\lim_{x\to 0} f(x)$$ is finite.

Define $$F:(0,1) \to [0,\infty)$$ by $$F(s)=\min_{xy=s,x,y\in(0,\infty)} f(x)+ f(y).$$

The properties of $$f$$ imply that the minimum for $$0 is obtained at a point where $$x,y \le 1$$.

Question: Are there "natural" conditions on $$f$$ which imply that $$F$$ is convex?

The finiteness assumption of $$\lim_{x\to 0} f(x)$$ is mainly here to exclude the possibility that $$(\sqrt s,\sqrt s)$$ is a minimizer for every $$s$$, or $$F(s)=2f(\sqrt s)$$. (In this case $$F$$ is always convex).

Here are some examples and non-examples:

Quadratic penalization: $$f(x)=(x-1)^2$$. $$F(s) = \begin{cases} 1-2s, & \text{ if }\, 0 \le s \le \frac{1}{4} \\ 2(\sqrt{s}-1)^2, & \text{ if }\, s \ge \frac{1}{4}, \end{cases}$$

is convex as its derivative is non-decreasing. In this case, the minimum point $$(x(s),y(s))$$ for $$s \le \frac{1}{4}$$ satisfies $$x(s)+y(s)=1$$.

Qubic penalization: $$f(x)=(1-x)^3$$. $$F(s)=\begin{cases} 1 - 3 s - 2s^{3/2} &\text{ if } 0 is not convex, as $$F''<0$$ on $$(0,1/9)$$.

Similarly, for $$f(x)=(x-1)^4$$, $$F$$ is also non-convex.

So, interestingly, when we change from quadratic to either cubic or quartic the convexity properties of $$F$$ change. Is there any "conceptual" reason for this? Is the convexity of $$F$$ for $$f(x)=(x-1)^2$$ just a "mere miracle", without some hidden cause behind it?

Edit:

Since the question seems hard, I think that it's reasonable to start with an easier problem:

Characterize the situations where $$F(s)$$ has an affine part.

In the example where $$f(x)=(x-1)^2$$, $$F$$ is affine on a subinterval. This seems quite remarkable and unexpected. Can we prove that this only happens when $$f$$ is quadratic?

Here is my attempt, which at the moment I don't know how to finish:

Assume for simplicity that there exist a $$C^1$$ map $$s \to (x(s),y(s))$$ giving a minimizer to the problem, i.e. for any $$s \in (0,1]$$ $$F(s)=f(x(s))+f(y(s)), \, \, \,x(s)y(s)=1. \tag{1}$$ The methods of Lagrange's multipliers gives $$f'(x(s))=\lambda(s) y(s),f'(y(s))=\lambda(s) x(s). \tag{2}$$ We have $$F'(s)=\lambda (s)$$, so $$F''(s)=0$$ if and only if $$\lambda(s) < 0$$ is constant.

I am not sure how to proceed from here.

$$\lambda$$ must non-positive since $$f' \le 0$$ on $$(0,1)$$ by our assumption.

Note that our known solution for $$f(x)=(x-1)^2$$ satisfies equation $$(2)$$ for $$\lambda(s)=-2$$:

Indeed, the minimum is obtained at points where $$x(s)+y(s)=1$$, so $$f'(x(s))=2(x(s)-1)=-2(1-x(s))=-2y(s).$$

Since multiplying $$f$$ by $$\alpha>0$$ results in a multiplication of $$\lambda(s)$$ by $$\alpha$$, it suffices to assume that $$c=-2$$ and prove that $$f(x)=(x-1)^2$$.

• Looks to me like it takes a "perfect storm" to overcome the non-convexity of $xy=s$. – Mark L. Stone Jun 10 at 15:51
• Thanks, I think you might be right. I tried to solve a "easier " question: When is the optimum $F(s)$ affine? This miracle seems even more surprising than convexity. I have edited the question to include an attempted proof for that subproblem. (It reduces to a coupled ODE+a functional equation. which I don't know how to analyze). – Asaf Shachar Jun 29 at 7:38