介绍

• 一维搜索方法
  • 区间收缩
    • 黄金分割法
  • 函数逼近
    • 三点二插法
    • 牛顿法
  • 初始搜索区间
    • 外推内插法

在此只是记录我的笔记，方便日后重温。

正文

设有一个单谷函数，某个区间[a,b]存在极小值点，用黄金分割法怎么找到它呢？

实现思想关键：

• x1,x2∈[a,b], x1<x2
• x1 - a = b - x2
• 保持缩减比不变：lamba=（保留的区间长度/原区间长度) 不变

为啥是这个比例，课本也没说，可能经验值得出比较迅速有效缩减区间吧，具体还得查阅相关文献。

matlab实现源码

% init

x = -1:0.01:1; % range of x values
f = @(x)2*x.^2-x-1; % f(x) = 2*x^2-x-1 , anonymous piecewise matlab function form 
a = -1; % start of interval
b = 1; % end of interval
len = b - a; % length of interval  
lambda = double((sqrt(5)-1)/2); %golden proportion coefficient, around 0.618
epsilon = 0.06; % accuracy value
iter = 50; % maximum number of iterations
k = 0; %number of iterations

figure; hold on;
plot(x, f(x)); 


% computing x values
x1 = a + (1-lambda)*len;
x2 = a + lambda*len;

% computing values in x points
f_x1 = f(x1);
f_x2 = f(x2);

while((abs(b - a) > epsilon) && (k < iter))
  k = k + 1
  if(f_x1 < f_x2)
    b = x2;
    x2 = x1;
    len = b - a;
    x1 = a + (1 - lambda)*len;

    f_x1 = f(x1);
    f_x2 = f(x2);

    sprintf('     x_min = %f', x1)
    sprintf('     f(x_min) = %f', f_x1)

     plot(x1, f_x1, 'rx');
  else
    a = x1;
    x1 = x2;
    len = b - a;
    x2 = a + lambda*len;

    f_x1 = f(x1);
    f_x2 = f(x2);

    sprintf('    x_min = %f', x2)
    sprintf('    f(x_min) = %f', f_x2)

     plot(x2, f_x2, 'rx');
  end

end

% chooese minimum point 
if(f_x1 < f_x2)
  sprintf('x_min = %f', x1)
  sprintf('f(x_min) = %f', f_x1)
  plot(x1, f_x1, 'bo')
else 
  sprintf('x_min = %f', x2)
  sprintf('f(x_min) = %f', f_x2)
  plot(x2, f_x2, 'bo')
end

奉上 linprog 使用小例子
(其实只用在matlab里输入 linprog help 就可以找到该函数的使用方法啦)

% coefficients
f = [-5; -2; 0; 0; 0];
Aeq =  [30 20 1 0 0
      5 1 0 1 0
      1 0 0 0 1];
beq = [160; 15; 4];
lb = zeros(5,1);

% call a linear programming routine
[x, fval, exitflag, output, lambda] = linprog(f, [], [], Aeq, beq, lb);

% Examine the solution and Lagrange multipliers:
x, fval