python - 使用分段线性函数低估 f(x)

Question

我正在尝试使用分段线性函数 g(x) 检查是否有任何 Matlab/Python 程序可以低估 f(x)。即 g(x) 需要小于或等于 f(x)。请参见下面的图片和代码。能否请您帮忙修改一下这段代码，看看如何低估这个函数？

 x = 0.000000001:0.001:1;
 y = abs(f(x));

 %# Find section sizes, by using an inverse of the approximation of the derivative
 numOfSections = 5;
 totalRange = max(x(:))-min(x(:));

 %# The relevant nodes
 xNodes = x(1) + [ 0 cumsum(sectionSize)];
 yNodes = abs(f(xNodes));

 figure;plot(x,y);
 hold on;
 plot (xNodes,yNodes,'r');
 scatter (xNodes,yNodes,'r');
 legend('abs(f(x))','adaptive linear interpolation');

Answer 1

此方法基于 Luis Mendo 的评论。思路如下:

1. 从原始曲线中选择一些点，您最终的分段线性曲线将通过这些点
2. 对于每个点计算原始曲线的切线方程。因为你的图是凸的，你的样本中连续点的切线将在曲线下方相交
3. 为每组连续的切线计算交点的 x 坐标。用切线的方程计算出对应的y坐标

现在，在对点重新排序后，这会为您提供具有所需约束的分段线性近似值。

h = 0.001;
x = 0.000000001:h:1;
y = abs(log2(x));

% Derivative of function on all the points
der = diff(y)/h;

NPts = 10; % Number of sample points

% Draw the index of the points by which the output will pass at random
% Still make sure you got first and last point
idx = randperm(length(x)-3,NPts-2);
idx = [1 idx+1 length(x)-1]; 
idx = sort(idx);
x_pckd = x(idx);
y_pckd = y(idx);
der_pckd = der(idx);

% Use obscure math to calculate the points of intersection
xder = der_pckd.*x_pckd;
x_2add = -(diff(y_pckd)-(diff(xder)))./diff(der_pckd);
y_2add = der_pckd(1:(end-1)).*(x_2add-(x_pckd(1:(end-1))))+y_pckd(1:(end-1));

% Calculate the error as the sum of the errors made at the middle points
Err_add = sum(abs(y_2add-interp1(x,y,x_2add))); 

% Get final x and y coordinates of interpolant
x_final = [reshape([x_pckd(1:end-1);x_2add],1,[]) x_pckd(end)];
y_final = [reshape([y_pckd(1:end-1);y_2add],1,[]) y_pckd(end)];

figure;
plot(x,y,'-k');
hold on
plot(x_final,y_final,'-or')

您可以在我的代码中看到这些点是随机绘制的。如果你想做某种优化(例如，最小化错误的点集是什么)，你可以运行它很长时间并跟踪最佳竞争者。比如10000次随机抽取看到这家伙的崛起: