A lower bound of a particular convex function - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:50:26Z http://mathoverflow.net/feeds/question/61946 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/61946/a-lower-bound-of-a-particular-convex-function A lower bound of a particular convex function Jennifer Gao 2011-04-16T19:15:18Z 2011-05-08T10:14:55Z <p>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</p> <p>$(\frac{a}{a+b})\cdot2\sqrt{a} + (\frac{b}{a+b})\cdot\frac{3\cdot2^{1/3}}{2}b^{1/3}$.</p> <p>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</p> <p>$(\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!</p> <p>EDIT: It also appears that if I take the convex combination</p> <p>$(\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}$</p> <p>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.</p> http://mathoverflow.net/questions/61946/a-lower-bound-of-a-particular-convex-function/62099#62099 Answer by Denis Serre for A lower bound of a particular convex function Denis Serre 2011-04-18T08:41:55Z 2011-04-18T08:41:55Z <p>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}.$$</p> http://mathoverflow.net/questions/61946/a-lower-bound-of-a-particular-convex-function/64279#64279 Answer by Maciej S. for A lower bound of a particular convex function Maciej S. 2011-05-08T10:14:55Z 2011-05-08T10:14:55Z <p>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]$.</p> <p>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}}$</p> <p>The best estimate is achieved when both minimizers are equal, which means, in therms of $p$, that </p> <p>$$\left(\frac{p}{a}\right)^{3} = \left( \frac{1-p}{2b}\right)^{2}$$</p> <p>Note, that this equation has a solution in interval $0 &lt; p &lt; 1$ by Mean-value theorem, unfortunately not expressible in nice way. </p> <p>Any way, we get for any $p\in[0,1]$ the following estimate:</p> <p>$$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}}$$</p> <p>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.</p> <p>$$f(x) \geqslant \alpha \cdot 2a^{\frac{1}{2}} + (1-\alpha) \cdot\frac{3\cdot 2^{\frac{1}{3}} }{2} b^{\frac{1}{3}}$$</p> <p>This can be seen immediately, however, by the <strong>inequality</strong> $f \geqslant \alpha f_0 + (1-\alpha) f_1$. My goal was to complete presented ideas and to show when exact optimum is attained.</p>