3
$\begingroup$

Let

$$f(x) := \frac{2x+1}{x^2+3}$$

I would like to solve the following optimization problem

$$ \begin{array}{ll} \underset {x_1, x_2, x_3} {\text{minimize}} & f(x_1) + f(x_2) + f(x_3) \\ \text{subject to} & x_1 + x_2 + x_3 = 3 \\ & x_1, x_2, x_3 \in [0,3] \end{array} $$

I am not sure how to find that since $f(x)$ is concave and convex over the given interval. Any help will be greatly appreciated.

$\endgroup$
6
  • $\begingroup$ Lagrange multipliers? $\endgroup$
    – eyeballfrog
    Mar 28 at 14:41
  • $\begingroup$ @eyeballfrog I dont know them $\endgroup$
    – Helixglich
    Mar 28 at 14:56
  • $\begingroup$ Are you sure you want to mimize? I ask since in the given interval, there is a unique maximum, whereas minima are obtained at the boundary. $\endgroup$
    – Andreas
    Mar 28 at 15:19
  • $\begingroup$ @Andreas. Indeed I was. Otherwise I would have used Jensen $\endgroup$
    – Helixglich
    Mar 28 at 16:14
  • $\begingroup$ Given how nice the objective function is, I wonder if its niceness can be exploited $\endgroup$
    – Rodrigo de Azevedo
    Mar 29 at 8:35

2 Answers 2

Reset to default
4
$\begingroup$

We have, for all $x \in [0, 3]$, $$\frac{2x + 1}{x^2 + 3} - \frac{x + 4}{12} = \frac{x(x + 7)(3 - x)}{12(x^2 + 3)} \ge 0.$$

Thus, we have, for all $x_1, x_2, x_3 \in [0, 3]$ with $x_1 + x_2 + x_3 = 3$, $$f(x_1) + f(x_2) + f(x_3) \ge \frac{x_1 + 4}{12} + \frac{x_2 + 4}{12} + \frac{x_3 + 4}{12} = \frac54$$ with equality if $x_1 = 0, x_2 = 0, x_3 = 3$ and permutations.

Thus, the minimum if $\frac54$.

$\endgroup$
11
  • 2
    $\begingroup$ Nice! errata: the minimum is $\frac54$; $x_1 = 0, x_2 = 0, x_3 = 3$ and permutations. $\endgroup$
    – Andreas
    Mar 28 at 16:07
  • 1
    $\begingroup$ Hmmm. That is smart. Can you explain your motivation for the first line? $\endgroup$
    – Helixglich
    Mar 28 at 16:11
  • $\begingroup$ @River Li could you please explain to me how one should come up with $\frac{2x+1}{x^{2}+3}-\frac{x+4}{12}\ge0$.....It kinda looks like tangent line trick but It isn't $\endgroup$
    – Helixglich
    Mar 28 at 18:55
  • 3
    $\begingroup$ @Helixglich there is no general, "magic intuition" that help solve all problems. Most of the times, it's experience of solving similar problems in the past. As for the guess, since you have a liner sum constraint, it would be a reasonable first attempt to look for: $$\dfrac{2x+1}{x^2+3}\geq ax + b$$ to hold for $x\in[0,3].$ This means that the cubic after expanding should have factors $x(x-3)$ and another linear factor and in that case it turns out to be useful. This is not guaranteed in general and if the problem was harder/tighter, then it would naturally require more advanced stuff. $\endgroup$
    – dezdichado
    Mar 28 at 19:20
  • 2
    $\begingroup$ @Helixglich As explained by dezdichado, here we used linear function lower bound for the objective. $\endgroup$
    – River Li
    Mar 28 at 23:15
1
$\begingroup$

Uhhh. I didn't realize that River Li was just using tangent line trick...I had nothing to do so I present a proof that if probably wrong but I can't find why....
Let $f(x) = \frac{2x+1}{x^2+3}$. Therefore, $f'(x) = \frac{-2x^2-2x+6}{(x^2+3)^2}$. Therefore $f''(x) = \frac{4x^3+6x^2-36x-6}{(x^2+3)^3}$
We are now ready to locate the inflection points of $f(x)$ $$f''(x) = 0 \leftrightarrow 4x^3+6x^2-36x-6 = 0$$ Since \begin{array}{|c|c|} \hline x& f''(x)\\ \hline -4&-22 \\ \hline -3&48 \\ \hline 0&-6 \\ \hline 3&48 \\ \hline \end{array} And clearly $-4,-3,0,3$ are not zeros. From intermediate value theorem follows that there is only one root of the cubic in the interval $[0,3]$ and thus one inflection point ot $f(x)$.

We will now use something known as n - 1 EV (Theorem 2.8) $\leftarrow$ Please someone check if I am using this correctly

We now just need to optimise: $F(a) =f(a) + f(a) + f(3-2a)$ subject to $a\in[0,1.5]$

$$F(a) = 2*\frac{2a+1}{a^2+3}+\frac{2(3-2a)+1}{(3-2a)^2+3}\Longrightarrow F'(a) = \frac{4a^2-14a+9}{4(a^2-3a+3)^2}-4*\frac{a^2+a-3}{(a^2+3)^2}$$ We will now find the critical points in $F'(a)$ subject to $a\in[0,1.5]$

Since $a\in \mathbb{R}$ the function is always defined and we will only need to check $F'(a) = 0$ $$F'(a) = 0 \leftrightarrow \frac{4a^2-14a+9}{4(a^2-3a+3)^2}=4\frac{a^2+a-3}{(a^2+3)^2}$$ $$12a^6-66a^5+63a^4+324a^3-954a^2+1134a-513=0$$ From some testing we get the only real root in the interval is $a = 1$ (I did Sturm's method with wolfram if anyone knows a method to do this by hand please please reply ;D )

Now onto our last step:

\begin{array}{|c|c|} \hline a& F'(a)\\ \hline 0&\frac{5}{4} \\ \hline 1&\frac{9}{4} \\ \hline 1.5&1.85714 \\ \hline \end{array}

And finally we conclude that the minimum is $\frac{5}{4}$ with the equality cases being permutations of (0,0,3)

And also the maximum reached at (1,1,1) (Can also be found using concave Jensen)

$\endgroup$
4
  • $\begingroup$ EV is powerful. $\endgroup$
    – River Li
    Mar 30 at 23:34
  • $\begingroup$ @RiverLi can you please explain two things about my solution that I just claimed are true.1) how do I know that n-1Ev doesn't push numbers off the interval. 2) how could I have done what I did with sturms by hand? $\endgroup$
    – Helixglich
    Mar 31 at 4:03
  • $\begingroup$ Actually, since $f(x)$ is concave on $[0, c]$ and convex on $[c, 3]$ for some $c$. You can assume that $x_1 \le x_2\le x_3$. There are two cases: $x_1, x_2 \in [0, c]$ or $x_2, x_3 \in [c, 3]$. $\endgroup$
    – River Li
    Mar 31 at 5:43
  • $\begingroup$ for question 2), I have no idea. $\endgroup$
    – River Li
    Mar 31 at 5:44

You must log in to answer this question.

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