A Method for Approximating Univariate Convex Functions Using Only Function Value Evaluations
提出仅基于函数值信息构造单变量凸函数的分段线性上下界，并设计迭代添加数据点的夹逼算法，在特定条件下达到二次收敛，可用于战略投资模型等场景。
In this paper, piecewise-linear upper and lower bounds for univariate convex functions are derived that are only based on function value information. These upper and lower bounds can be used to approximate univariate convex functions. Furthermore, new sandwich algorithms are proposed that iteratively add new input data points in a systematic way until a desired accuracy of the approximation is obtained. We show that our new algorithms that use only function value evaluations converge quadratically under certain conditions on the derivatives. Under other conditions, linear convergence can be shown. Some numerical examples that illustrate the usefulness of the algorithm, including a strategic investment model, are given.