3
$\begingroup$

Hello, I suspect this reduces to a homework problem, but I've been a bit hung up on it for the last few hours. I'm trying to minimize the (convex) function $f(x) = 1/x + ax + bx^2$ , where $x,a,b>0$. Specifically, I'm interested in the minimal objective function value as a function of $a$ and $b$. Since finding the minimizer $x^*$ is tricky (requires solving a cubic), I figured I'd try and find a lower bound using the following argument: if $b=0$, the minimizer is $x=1/\sqrt{a}$ and the minimal value is $2\sqrt{a}$. If $a=0$, the minimizer is $x=(2b)^{-1/3}$ and the minimal value is $\frac{3\cdot2^{1/3}}{2}b^{1/3}$. Therefore, one possible approximate solution is the convex combination

$(\frac{a}{a+b})\cdot2\sqrt{a} + (\frac{b}{a+b})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3}$.

Numerical simulations suggest that the above expression is a lower bound for the minimal value. Does this follow from some nice result about parameterized convex functions? It seems like it shouldn't be hard to prove. I guess in a nutshell I just want to prove that for all $x,a,b>0$ we have

$(\frac{a}{a+b})\cdot2\sqrt{a} + (\frac{b}{a+b})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3} \leq 1/x + ax + bx^2$. Thanks!

EDIT: It also appears that if I take the convex combination

$(\frac{a^{3/5}}{a^{3/5}+b^{2/5}})\cdot2\sqrt{a} + (\frac{b^{2/5}}{a^{3/5}+b^{2/5}})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3}$

then I get a tighter lower bound, and in fact the lower bound is within a factor of something like $3/2$ of the true minimal solution.

$\endgroup$
4
  • $\begingroup$ can't you just split 1/x into the linear combination and use that. $\endgroup$ Apr 16, 2011 at 19:24
  • $\begingroup$ Sorry, I don't understand -- how does the "splitting" work? $\endgroup$ Apr 17, 2011 at 8:29
  • 2
    $\begingroup$ but computing the roots of your cubic don't seem to be too much more complicated than computing the lower bounds? en.wikipedia.org/wiki/Cubic_function $\endgroup$
    – Suvrit
    Apr 17, 2011 at 8:50
  • $\begingroup$ @Suvrit: is it? The expression for the roots of a cubic looks pretty complicated to me, and the lower bound is just a pair of terms. $\endgroup$ Apr 17, 2011 at 20:40

2 Answers 2

1
$\begingroup$

The first inequality is true. Write $$f=\frac{a}{a+b}f_0+\frac{b}{a+b}f_1,$$ where $f_0$ and $f_1$ correspond to the case $b=0$ and $a=0$, respectively. You know that $f_0\ge2\sqrt a$ and $f_1\ge\frac{3\cdot2^{1/3}}{2}b^{1/3}$. This implies $$f\ge\frac{a}{a+b}2\sqrt a+\frac{b}{a+b}\frac{3\cdot2^{1/3}}{2}b^{1/3}.$$

$\endgroup$
1
  • $\begingroup$ Is it true? We have $\frac{a}{a+b}f_0 + \frac{b}{a+b}f_1 = \frac{1}{x}+\frac{a^2}{a+b}x + \frac{b^2}{a+b}x^2$ $\endgroup$ May 8, 2011 at 9:10
1
$\begingroup$

As Nishant Chandgotia sugessted: simply write $f(x) = \left(p\cdot \frac{1}{x} + ax\right) + \left((1-p)\frac{1}{x}+bx^2 \right)$ for some parametr $p\in[0,1]$.

For the first term, minimizer is equal to $ p^{\frac{1}{2}}a^{-\frac{1}{2}}$ and the minimal value is $p^{\frac{1}{2}} 2a^{\frac{1}{2}}$. For the second therm, minimizer is equal to $(1-p)^{\frac{1}{3}}(2b)^{-\frac{1}{3}} $ and the minimal value is $(1-p)^{\frac{2}{3}} \cdot\frac{3\cdot 2^{\frac{1}{3}} }{2} b^{\frac{1}{3}}$

The best estimate is achieved when both minimizers are equal, which means, in therms of $p$, that

\begin{equation} \left(\frac{p}{a}\right)^{3} = \left( \frac{1-p}{2b}\right)^{2} \end{equation}

Note, that this equation has a solution in interval $0 < p < 1$ by Mean-value theorem, unfortunately not expressible in nice way.

Any way, we get for any $p\in[0,1]$ the following estimate:

\begin{equation} f(x) \geqslant p^{\frac{1}{2}} \cdot 2a^{\frac{1}{2}} + (1-p)^{\frac{2}{3}} \cdot\frac{3\cdot 2^{\frac{1}{3}} }{2} b^{\frac{1}{3}} \end{equation}

Finally, we check that $p^{\frac{1}{2}} + (1-p)^{\frac{2}{3}} \geqslant 1$. This inequality implies, that estimate reamins valid after using any convex combination instead of weights $p^{\frac{1}{2}}, (1-p)^{\frac{2}{3}}$, i.e.

\begin{equation} f(x) \geqslant \alpha \cdot 2a^{\frac{1}{2}} + (1-\alpha) \cdot\frac{3\cdot 2^{\frac{1}{3}} }{2} b^{\frac{1}{3}} \end{equation}

This can be seen immediately, however, by the inequality $f \geqslant \alpha f_0 + (1-\alpha) f_1$. My goal was to complete presented ideas and to show when exact optimum is attained.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.