Approximation in p-Norm of Univariate Concave Functions |
| |
| Authors: | J. Guérin P. Marcotte G. Savard |
| |
| Affiliation: | 1. Département de mathématiques et génie industriel, école Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, H3C 3A7, Canada
2. Département d’informatique et de recherche opérationnelle, Université de Montréal, C.P. 6128, succursale Centre-ville, Montréal, H3C 3J7, Canada
|
| |
| Abstract: | We derive worst-case bounds, with respect to the L p norm, on the error achieved by algorithms aimed at approximating a concave function of a single variable, through the evaluation of the function and its subgradient at a fixed number of points to be determined. We prove that, for p larger than 1, adaptive algorithms outperform passive ones. Next, for the uniform norm, we propose an improvement of the Sandwich algorithm, based on a dynamic programming formulation of the problem. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
