优化设计-2

函数左端输出变量 [x]=linprog()

[x,fval]= linprog()

[x,fval,exitflag]= linprog()

[x,fval,exitflag,output]= linprog()

[x,fval,exitflag,output,lambda]= linprog()

X返回目标函数最优解,fval返回目标函数最优值,exitflag终止迭代的标志（整数值）,output输出迭代次数,lambda解x的拉格朗日乘子 exitflag=1 exitflag=0 exitflag=-2 exitflag=-3

output, algorithm output, funcCount output,iterations output,message

第4章 一维搜索方法

是指求解一维目标函数f(x)的极小点和极小值的数值迭代方法，可归纳为单变量函数的极小化问题。虽然优化设计中大部分问题是多维问题，一维问题的情况较少，但是一维优化方法是优化方法中最基本的方法，在数值迭代过程中都要进行一维搜索。另外，很多多维优化问题最终归结为一维优化问题来处理。

如果确定了迭代点x(k)及其搜索方向d(k)，那么迭代所得的新点x(k+1)将取决于步长a(k)，即

x(k+1)= x(k)+ a(k) d(k)，k=0，1，2，… (4.1)

由式4.1可知，不同的步长a(k)会得到不同的迭代点和不同的目标函数值f(x(k+1))。一维优化问题的目的是在既定的迭代点x(k)和搜索方向d(k)下寻求最优步长a(k)，使迭代产生的新点x(k+1)的函数值最小，即

min f[x(k)+ a(k) d(k)]

在初始迭代点x(k)和搜索方向d(k)确定后，就把求解多维优化问题的极小值变成求解一个自变量即最优步长a的最优值的一维问题了。即求一元函数 f(x(k+1))=f(x(k)+ a d(k))=φ( a) (4.2) 的极值问题。

一维搜索的优化方法很多，常用进退法、黄金分割法和二次插值法。 一维搜索方法的步骤：

(1) 确定初始搜索区间[a,b]，即最优步长a所在的区间[a,b]。搜索区间应为单峰区间，并且在区间内目标函数应只有一个极小值。

(2) 在搜索区间[a,b]内寻找最优步长a，使目标函数式4.2达到极小值。

4.1 确定初始单峰区间的方法—进退法

原理

进退法也称为外推法，是一种通过比较函数值大小来确定单峰区间的方法。由单峰函数的性质可知，在极小点左边函数值应严格下降，而在极小点右边函数值应严格上升。因此，从某一种给定的初始点x0出发，以初始步长a沿着目标函数值的下降方向，逐步前进（或后退），直至找到相继的3个计算点的函数值出现“大-小-大”的趋势为止。 利用进退法确定搜索区间[a,b]的步骤如下： (1) 任取x0，步长a>0，取x1=x0+a。 (2) 后退运算。φ(x1)>φ(x0)，则令a=2a（步长加倍），x2=x0-a。分以下两种情况：若φ(x2)<φ(x0)，则令x1=x0，x0=x2。重复(2)；若φ(x2)>φ(x0)，则停止a=x2，b=x1。 (3) 前进运算，若φ(x1)<φ(x0)，则令a=2a（步长加倍），x2=x1+a。若φ(x2)<φ(x1)，则令x0=x1，x1=x2，重复(3)；若φ(x2)>φ(x1)，则停止，a=x0，b=x2。 程序框图

4.2 黄金分割法

1 基本原理

又称为0.618法，它通过不断缩短搜索区间的长度来寻求一维函数f(x)的极小点。对于单峰函数f(x)，在其极值存在的某个区间[a,b]内取若干点，计算这些点的函数值并进行比较，总可以找到极值存在的更小区间。在这更小区间内增加计算点，又可以讲区间进一步缩小。当

区间足够小，即满足精度要求时，就可以用该区间内任意一点的函数值来近似表达函数的极值。

设单变量函数f(x)在区间[a,b]上有定义，若存在一点x*(a b)，使得f(x)在区间[a,x*]上严格单调减，f(x)在区间[x*,b]上严格单调增，则称f(x)是区间[a,b]上的（下）单峰函数。显然x*是f(x)在区间[a,b]上的唯一的极小值点。

根据（下）单峰函数所具有的性质，对在某区间[a,b]上的（下）单峰函数f(x)可采用黄金分割法搜索其在区间[a,b]内得极小值点。 2 计算方法

设区间[a,b]的长度为L，在区间内取点λ1，将区间分割为两部分，线段aλ1的长度记作λ，并满足

?L?L????q2且2??L??

?1?5，取正根2由上式有??L??L?0，两边同除L2，得q2+q-1=0，则有q?q?5?1?0.6180339887。q称为区间收缩率，它表示每次缩小所得的新区间长度与缩2小前区间长度之比。

在一维搜索时，在区间内取两对称点λ1和λ2，并满足

q??2L??1L??2??0.618 ?2?2显然，经一次分割后，所保留的极值存在的区间要么是[a, λ2]，要么是[λ1，b]。而经k次分割后，所保留的区间的长度为??qL?(0.618)L。

由于区间收缩率q是一个近似值，每次分割必定带来一定的舍入误差，因此，分割次数太多

时计算会失真。经验表明，黄金分割的次数k应限制在11以内。

kkk4.3 拉格朗日插值多项式

是一种显式公式,它将pn(x)表示为一组插值基函数的线性组合。 1 线性插值

设函数y=f(x)在给定的互异节点x0，x1上的函数值分别为y0=f(x0)，y1=f(x1)，若能构造一个函数

p1(x)=a+bx (4.3)

使它满足p1(x0)=y0，p1(x1)=y1，则式4.3所示的插值问题称为线性插值。

线性插值的几何意义是过曲线y=f(x)上的两点(x0,y0)和(x1,y1)作一直线，用p1(x)近似值代f(x)。

对于给定的两点(x0,y0)和(x1,y1)，某一点x(x0

p1(x)?y0?记

y1?y0x?x1x?x0(x?x0)?y0?y1

x1?x0x0?x1x1?x0l0(x)?x?x1x?x0 ,l1(x)?x0?x1x1?x0l0 (x)和 l1 (x)称为线性插值基函数。

l0 (x)和 l1 (x)实质上是满足条件

l0 (x0)=1, l0 (x1)=0; l1 (x0)=0, l1 (x1)=1的一次插值多项式。

线性插值的解可以表示为插值基函数l0 (x)和 l1 (x)的线性组合，其组合系数为y0和y1,即 p1(x)= y0 l0 (x)+ y1 l1 (x) 2 二次函数插值

又称为抛物线法，基本思路为：利用目标函数在若干点的信息和函数值，构造一个与目标函数相接近的低次插值多项式，然后求该多项式的最优解作为原函数的近似最优解。随着区间的逐次缩小，多项式最优点与原函数最优点之间的距离逐渐缩小，直到满足一定精度要求时终止迭代。 基本原理

设目标函数f(x)在点x1,x2,x3(x1< x2< x3)上的函数值分别为f1=f(x1),f2=(x2),f3=(x3),且满足f1> f2和f2< f3即满足函数值呈“大-小-大”的趋势。于是可通过原函数曲线上的3个点p1(x1,f1), p2(x2,f2), p3(x3,f3)做一条二次曲线，此二次插值多项式为p(x)=a+bx+cx2。 为了求解p(x)的极小值，对p(x)求导数，并令其为0，即

p?(x)?b?2cx?0

解得二次函数极小点

xp??b (4.5) 2c为求得，应求出式4.5中的待定参数b和c。

根据插值条件，插值函数p(x)与原函数f(x)在插值点p1, p2, p3处函数值相等，得 p(x1)=a+bx1+cx12=f1 p(x2)=a+bx2+cx22=f2 p(x3)=a+bx3+cx32=f3 求得

a?(x3?x2)x2x3f1?(x1?x3)x1x3f2?(x2?x1)x1x2f3(x1?x2)(x2?x3)(x3?x1) (4.6)

2222(x2?x3)f1?(x3?x12)f2?(x12?x2)f3b?(x1?x2)(x2?x3)(x3?x1)c?(x2?x3)f1?(x3?x1)f2?(x1?x2)f3(x1?x2)(x2?x3)(x3?x1)把式4.6代入式4.5，既得二次插值函数极小点的计算公式：

22221?(x2?x3)f1?(x3?x12)f2?(x12?x2)f3?xp??? (4.7)

2?(x2?x3)f1?(x3?x1)f2?(x1?x2)f3?为便于计算，将式4.7改写为

xp?0.5(x1?x3?C1) (4.8) C2