An optimal adaptive algorithm for the approximation of concave functions

• 成果类型: Article
• 署名作者: Guérin, J; Marcotte, P; Savard, G
• 署名单位: Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0502-7
• 发表日期: 2006
• 页码: 357-366
• 关键词: convex-functions

摘要

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.