Approximating a convex function by a piecewise linear function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T05:48:21Z http://mathoverflow.net/feeds/question/108340 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108340/approximating-a-convex-function-by-a-piecewise-linear-function Approximating a convex function by a piecewise linear function Flavio Burton 2012-09-28T13:04:26Z 2012-09-28T18:13:44Z <p>Suppose I have a Lipschitz-continuous convex function $f:\mathbb{R}^n\rightarrow \mathbb{R}$. I wish to approximate it on the unit ball by a piecewise-linear function $g:\mathbb{R}^n\rightarrow \mathbb{R}$ such that pointwise: $$\forall x : ||x||_2 \leq 1, |f(x) - g(x)| \leq \epsilon$$</p> <p>Are there known bounds on the complexity of the piecewise linear function (i.e. the number of linear pieces needed) to achieve such an approximation, in terms of $\epsilon$ and $n$? I'm particularly interested in the dependence on the dimension $n$. Might the dependence be polynomial (or even linear?), or are there Lipschitz convex functions that require exponentially many linear pieces (in $n$) to approximate? </p> http://mathoverflow.net/questions/108340/approximating-a-convex-function-by-a-piecewise-linear-function/108367#108367 Answer by ε-δ for Approximating a convex function by a piecewise linear function ε-δ 2012-09-28T17:50:45Z 2012-09-28T18:13:44Z <p>For $f(x)=|x|^2$, you get $\varepsilon\sim\tfrac C {k^{2/n}}$, where $k$ is the number of pieces for your PL-function. In particular, you will not get linear bound for $n\ge 3$.</p> <p>I think for any convex 1-Lipschitz function you should get $\varepsilon=O(k^{-2/n})$.</p> <p>An easy construction gives $\varepsilon=O(k^{-1/n})$, simply take the maximum of supporting linear functions with gradients $\{v_1,v_2,\dots,v_k\}$ which form a $C k^{-1/n}$ dense set in the unit ball.</p> <p>(Note that the worse case for this approximation is a linear function with gradient sufficiently far from $v_i$.)</p>