Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
can't you just split 1/x into the linear combination and use that. –  Nishant Chandgotia Apr 16 '11 at 19:24
    
Sorry, I don't understand -- how does the "splitting" work? –  Jennifer Gao Apr 17 '11 at 8:29
2  
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 –  Suvrit Apr 17 '11 at 8:50
    
@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. –  Jennifer Gao Apr 17 '11 at 20:40
add comment

2 Answers

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

share|improve this answer
    
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$ –  Maciej S. May 8 '11 at 9:10
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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