An optimal adaptive algorithm for the approximation of concave functions |
| |
| Authors: | J. Guérin P. Marcotte G. Savard |
| |
| Affiliation: | (1) Département de mathématiques et génie industriel, école Polytechnique Montréal, C.P. 6079, succursale Centre-ville Montréal (Québec), H3C 3A7, Canada;(2) CRT and DIRO, Université de Montréal, CP 6128, succursale Centre-Ville, Montréal, Canada, H3C 3J7;(3) GERAD and Département de mathématiques et génie industriel, école Polytechnique Montréal, C.P. 6079, succursale Centre-ville, Montréal (Québec), H3C 3A7, Canada |
| |
| Abstract: | ![]()
Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case. This work was partially supported by NSERC (Canada) and FCAR (Québec). |
| |
| Keywords: | Dynamic programming Approximation Adaptive algorithm |
| 本文献已被 SpringerLink 等数据库收录！ |
|
