无约束一维极值——进退法

无约束一维极值——进退法

前言

在求解目标函数的极小值的过程中,若对设计变量的取值范围不加限制，称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，但无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。

无约束一维极值问题求解时一般采用一维搜索法,其中方法包括多种。线性搜索包括黄金分割、斐波那契法、牛顿法等,非线性搜索包括抛物线法和三次插值法。

1.无约束算法基础

无约束最优化算法求解无约束最优化问题的方法,有解析法和直接法两类:

1. 解析法就是利用无约束最优化问题中目标函数f(x)的解析表达式和它的解析性质(如函数的一阶导数和二阶导数),给出一种求它的最优解的方法,或一种求近似解的迭代方法。解析法主要有最速 下降法、共轭方向法、共轭梯度法、非二次函数的共轭梯度法、牛顿法、拟牛顿法、变尺度法等。
2. 直接法就是在求最优解的过程中，只用到函数的函数值,而不必利用函数的解析性质。直接法也是一种迭代法,迭代步骤简单。当目标函数的表达式十分复杂,或写不出具体表达式时,它就成为了重要的方法。直接法适应面很广,适用于计算机运算。

2.进退法

进退法是一种缩小极值区间的算法,算出的结果是一个包含极值的区间,适用于未知极值范围的情况下使用。

其理论依据是f(x)为单谷函数(只有一个极值点),且[a,b]为其极小值点的一个搜索区间,对于任意x1,x2∈[a,b],如果f(x1)<f(x2),则[a,x2]为极小值的搜索区间,如果f(x1)> f(x2),则[x1,b]为极小值的搜索区间。

因此,在给定初始点x0及初始搜索步长h的情况下,首先以初始步长向前搜索一
步,计算f(x0+h)。

如果f(x0) > f(x0 +h),则可知搜索区间为[x0,x],其中x待求,为确定x,前进一步计算 f(x0+λh),λ为放大系数,且 λ>1,直到找到合适的λ" ,使得f(x0 +h) < f(x0+λ" h),从而确定搜索区间为[x0，x0+λ"h]。

如果f(x0) < f(x0 +h),则可知搜索区间为[x,x0+h],其中x待求，为确定x,后退一步计算 f(x0-λh),λ为缩小系数，且0<λ<1,直到找到合适的λ”,使得 f(x0-λ" h) > f(x0),从而确定搜索区间为[x0 -λ”h，x0+h]。

进退法的基本算法步骤如下:

1. 给定初始点x⁽⁰⁾ ,初始步长h0,令h=h0,x⁽¹⁾=x⁽¹⁾ ,k=0;
2. 令x⁽⁴⁾=x⁽¹⁾+h,k=k+1;
3. 若f(x⁽⁴⁾) < f(x⁽¹⁾),则转到步骤(4),否则转到步骤(5);
4. 令x⁽²⁾=x⁽¹⁾，x⁽¹⁾ =x⁽⁴⁾ ，f(x⁽²⁾)=f(x⁽¹⁾) , f(x⁽¹⁾)=f(x⁽⁴⁾)，令h = 2h ,转到步骤(2);
5. 若 k=1,则转到步骤(6),否则转到步骤(7);
6. 令h = -h , x⁽²⁾ = x⁽⁴⁾, f(x⁽²⁾)= f(x⁽⁴⁾),转到步骤(2);
7. 令x⁽³⁾ =x⁽²⁾，x⁽²⁾=x⁽¹⁾, x⁽¹⁾ = x⁽⁴⁾停止计算, 极小值点包含于区间[x⁽¹⁾, x⁽³⁾]或[x⁽³⁾ , x⁽¹⁾]。

根据以上分析，编写用进退法求解一维函数的极值区间的MATLAB函数fun_ JT
如下:

function [minx, maxx]= fun_JT(f, x0, h0, eps)
% 目标函数:f
% 初始点:x0
% 初始步长:h0
% 精度:eps
% 目标函数取包含极值的区间左端点:minx
% 目标函数取包含极值的区间又端点:maxxformat long;if nargin == 3;eps = 1.0e-6;endx1 = x0;k=0;h= h0;while 1x4 = x1 + h;k = k+ 1;f4 = subs(f, findsym(f),x4);f1 = subs(f, findsym(f),x1);if f4 < f1x2 = x1;x1 = x4;f2 = f1;f1 = f4;h = 2* h;elseif k == 1h = -h;x2 = x4;f2 = f4;elsex3 = x2;x2 = x1;x1 = x4;break;endendendminx = min (x1,x3);maxx = x1 +x3 -minx;format short;
end

例 取初始点为 0,步长为0.05,用进退法求函数f(t)=t⁴-2t²-t+1的极值区间。

解：

clear all
clc
syms t;
f=t^4-2*t^2-t+ 1;
[x1,x2] = fun_JT(f,0,0.05)

由上面的结果可知f(t)的极值点在区间[0.35,1.55]内。