An optimal adaptive algorithm for the approximation of concave functions
Consider a proper concave function \(f:[ 0,1] \to\mathbb R\), normalized so that \(f( 0) =0\) and \(f( 1) =1.\) \ Denote by \(f^{\prime }( \overline{x}) \) an arbitrary supergradient \(\xi \) of \(f\) at \(\overline{x},\) i.e., a supergradient \(\xi \) satisfying: \[ f( x) \leq f( \overline{x}) +\xi ( x-\overline{x} ) \text{ for all }x\in [ 0,1] \] Let \(x_{1},\dots .,x_{n}\) denote a finite sequence of \(n\) distinct points of evaluation, called knots, in \(( 0,1) \) and \(\sigma \) a permutation that reorders the knots and the two endpoints from left to right, i.e., \[ 0=x_{\sigma ( 0) }<x_{\sigma ( 1) }<\dots <x_{\sigma ( n) }<x_{\sigma ( n+1) }=1 \] Denote the under and over approximations of \(f\) over the interval \(( 0,1) ,\) respectively, by \[ \begin{aligned} L( t) &=\min_{i=1,\dots, n+1}\left\{ f( x_{\sigma ( i-1) }) \frac{( t-x_{\sigma ( i) }) }{ x_{\sigma ( i-1) }-x_{\sigma ( i) }}+f( x_{\sigma ( i) }) \frac{( t-x_{\sigma ( i-1) }) }{x_{\sigma ( i) }-x_{\sigma ( i-1) }}\right\}, \\ U( t) &=\min_{i=0,\dots, n+1}\{ f( x_{i}) +f^{\prime }( x_{i}) ( t-x_{i}) \}. \end{aligned} \] This yields the approximation error term \(\int_{0}^{1}( U( t) -L( t) ) \,dt.\) Using dynamic programming, the paper derives a procedure for minimizing the error term through a sequential procedure of knot selection which is proved to be optimal in the sense that it minimizes the error term in the worst case. The procedure is a deterministic adaptive algorithm in the sense that the selection of the current knot is dependent on the locations of the previous knots, i.e., the choice of \(x_{i}\) may depend upon the previous information \(x_{1},f( x_{1}) ,f^{\prime }( x_{1}) ,\dots ,x_{i-1},f( x_{i-1}) ,f^{\prime }( x_{i-1}) .\) The analysis seeks to improve upon previous works by \(( 1) \) obtaining both the optimal convergence rate and optimal selection rules for each \(n\) and \(( 2) \) getting parameter free results, i.e., no a priori information about the function to be approximated is required.
- Approximation in p-norm of univariate concave functions
- An algorithm for approximating piecewise linear concave functions from sample gradients
- scientific article; zbMATH DE number 3879983
- Sandwich approximation of univariate convex functions with an application to separable convex programming
- scientific article; zbMATH DE number 4130198
- A method for convex curve approximation
- Approximation of convex curves with application to the bicriterial minimum cost flow problem
- scientific article; zbMATH DE number 3174053 (Why is no real title available?)
- scientific article; zbMATH DE number 3879983 (Why is no real title available?)
- scientific article; zbMATH DE number 524184 (Why is no real title available?)
- scientific article; zbMATH DE number 1059230 (Why is no real title available?)
- Minimax models in the theory of numerical methods. Transl. from the 1989 Russian orig. by Olga Chuyan
- Sandwich approximation of univariate convex functions with an application to separable convex programming
- The convergence rate of the sandwich algorithm for approximating convex functions
- The adaptive algorithm for minimizing the sum of absolute values of linear functions
- An algorithm for approximating piecewise linear concave functions from sample gradients
- Approximation in p-norm of univariate concave functions
- A new algorithm for approximating the least concave majorant.
- Robust density estimation with the \(\mathbb{L}_1\)-loss. Applications to the estimation of a density on the line satisfying a shape constraint
- Nonlinear function approximation: computing smooth solutions with an adaptive greedy algorithm
This page was built for publication: An optimal adaptive algorithm for the approximation of concave functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2492698)
