最优化方法复习

1、第1章最优化问题的基本概念1.1最优化的概念最优化就是依据最优化原理和方法，在满足相关要求的前提下，以尽可能高的效率 求得工程问题最优解决方案的过程。1.2最优化问题的数学模型最优化问题的一般形式find x , x , A , xmin f (x , x , A , x ) TOC o 1-5 h z 12ns.t. g (x , x , A , x ) 0 u = 1,2, A , pu12nh (x , x ,A , x ) = 0 v = 1,2,A , qv12n最优化问题的向量表达式find Xmin f (X)一 一s.t. G(X) 0，使得 VX e N(X*,5 ) c D

2、(X。X*)都有 f (X*) f (X)，则称 X* 为 f (X)的局部 极小点；若f (X*) f (X)，则称X*为f (X)的严格局部极小点。若VX e D，都有f (X*) f (X)，则称X*为f (X)的全局极小点，若f (X*) f (X)，则称X*为f (X)的全局严格极小点。find X对最优化问题min f (X) s.t. G(X) 0而言满足所有约束条件的向量X = xi,x2,A ,xt称为上述最优化问题的一个可行解，全 体可行解组成的集合称为可行解集。在可行解集中，满足：f (X*) = min f (X)的解称为优化问题的最优解。凸集和凸函数凸集：设D u R

3、n，若对所有的X1、X2 e D，及以e 0,1，都有aX 1 + (1 a)X2 g D， 则称D为凸集。凸函数：设f : D u Rn r R1，D是凸集，如果对于所有的X1、X2 e D，及a e 0,1，都有 f aX 1 + (1 a) X 2 af (X1) + (1 a) f (X 2)，则称 f (X)为 D 上的凸函数。二、局部极小点的判别条件驻点：设f (X)是定义在n维空间Rn的子集D上的n元实值函数，X*是D的点，若 Nf (X*) = 0，则称X*为f (X)的驻点。局部极小点的判别：设f (X)是定义在n维空间Rn的子集D上的n元实值函数，具 有连续的二阶偏导数。若

4、X*是f (X)的驻点，且V2f (X*)是正定矩阵，则X*是f (X)的 严格局部极小点。第3章无约束优化方法3.1下降迭代算法及终止准则一、数值优化方法的基本思想基本思想就是在设计空间选定一个初始点Xk，从该点出发，按照某一方向Sk (该 方向的确定原则是使函数值下降)前进一定的步长ak，得到一个使目标函数值有所下 降的新设计点Xk+1，然后以该点为新的初始点，重复上面过程，直至得到满足精度要求 的最优点X*。该思想可用下式表示：Xk+1 = Xk +a kSk二、迭代计算的终止准则工程中常用的迭代终止准则有3种：点距准则相邻两次迭代点之间的距离充分小时，迭代终止。数学表达为：|Xk+1

5、X8函数下降量准则(值差准则)相邻两次迭代点的函数值之差充分小，迭代终止。数学表达为：|f(Xk+1) f(Xk)|8梯度准则目标函数在迭代点处的梯度模充分小时，迭代终止。数学表达为：|W(Xz)| 0及L、k0，使当k k0时下式：忡+1 - X*| k 0时下式：|Xk+1 - X 0都存在k0 0，使当k k0时下式：Xk+1 - x f (x2)，说明极小点在x2右侧，应加大步长向前搜索。转；若f (x ) f (x )，说明极小点在x左侧，应以x点为基准反向小步搜索。转； 1211大步向前搜索：令h u 2h，取x3 = x2 + h，计算f (x3)； TOC o 1-5 h z

6、若 f (x ) f (x3)，说明极小点在x3右侧，应加大步长向前搜索。此时要注意做变换：舍弃原x点，以原x点为新的x点，原x点为新的x点。转，直至出现“高一 12132一低一一高”排列，则单峰区间可得；反向小步搜索(要注意做变换)：为了保证x3点计算公式的一致性，做变换：将原x点记为新x点，原x点记为新x点，令h u - h，取x = x + h，转2112432例：用进退法确定函数f (x) = x2 -6x + 9的单峰区间a，b，设初始点x0 = 0 ，h = 1。解：。x0 = 0 h = 1. x = x = 0 x = x + h = 1 f (x ) = 9 f (x ) =

7、 4102112。f (气) f (x2)说明极小点在x点右侧，应加大步长向前搜索2则 f (x= 0令 h u 2h = 2 x 1 = 2 ，取 x3 = x2 + h = 1 + 2 = 3。f ( x 2) f ( x3)说明极小点在x点右侧，应加大步长向前搜索3f (x 2)= 0舍弃原x1 = 0的点，令x1 = 1x 2 = 3，则f (x1) = 4令 h u 2h = 2 x 2 = 4 ，取 x3 = x2 + h = 3 + 4 = 7 贝 U f (x3) = 16 f (x2) = 0f (气)、f (x2)、f (x3)呈“高一一低一一高”排列.x1，x3为单峰区间

8、，即区间1，7即为所求二、黄金分割法黄金分割法是基于区间消去思想的一维搜索方法，其搜索过程必须遵循以下的原 则：对称取点的原则：即所插入的两点在区间位置对称；插入点继承的原则：即插入的两点中有一个是上次缩减区间时的插入点；等比收缩的原则：即每一次区间消去后，单峰区间的收缩率人保持不变。设初始区间为a , b，则插入点的计算公式为：x = a + 0.382(b - a)x = a + 0.618(b - a)黄金分割法的计算步骤如下：给定初始区间a，b和收敛精度e ；给出中间插值点并计算其函数值：x = a + 0.382(b - a)f (x )x = a + 0.618(b a)f (x

9、)；比较f(气)、f(x2)，确定保留区间得到新的单峰区间a，b；收敛性判别：计算区间a，b长度并与比较，若b - a ，输出x * = (a + b)2否则转；在保留区间继承一点、插入一点，转。-3 x f (x1).舍弃(1.944，5，保留-3, 1.944 1.944-(-3) 继承原 x1 点，即 x2 = 0.056f (x2) = 0.115插入气=a + 0.382(b - a) =-3 + 0.382 x (1.944 + 3) = -1.111f (气)=-0.987/ f (x 2) f (气).舍弃(0.056，1.944，保留-3,0.0560.056 - (-3)

10、；继承原 x1 点，即x2 =-1.111f (x2) = -0.987插入气=a + 0.382(b - a) =-3 + 0.382 x (0.056 + 3) = -1.832f (气)=-0.306/ f (x2) ；继承原 x 2 点，即气=-1.111f (x1) = -0.987插入 x =-1.832 + 0.618 x (0.056 +1.832) = -0.665f (x ) = -0.88822/ f (X2) f (气).保留-1.832，-0.665如此迭代，到第 8 次，保留区为-1.111,-0.940 -0.940-(-1.111) = 0.171 8x* =

11、1 x (-1.111 + 0.940) = -1.0255f (x*) = -0.99923.3梯度法一、基本思想对于迭代式Xk+1 = Xk +以kSk，当取搜索方向Sk =-Vf (Xk)时构成的寻优算法，称 为求解无约束优化问题的梯度法。二、迭代步骤给定出发点Xk和收敛精度8 ；计算Xk点的梯度NF(Xk)，并构造搜索方向Sk =-VF(Xk)；令Xk+1 = Xk +以kSk，通过一维搜索确定步长a k，即：min F(X k +a kSk)求得新点Xk+1收敛判断：若|VF(Xk+1)| e成立，输出X* = Xk+1、F(X*) = F(Xk+1)，寻优结 束；否则令ku k +

12、1转继续迭代，直到满足收敛精度要求。三、梯度法的特点梯度法寻优效率受目标函数性态影响较大。若目标函数等值线为圆，则一轮搜索就 可找到极致点；若当目标函数等值线为扁椭圆时，收敛速度则显著下降。梯度法中相邻两轮搜索方向相互垂直。3.4牛顿法牛顿法分为基本牛顿法和阻尼牛顿法两种。对于迭代式Xk+1 = Xk +akSk，当取a k三1且搜索方向Sk =-V2f (Xk)-1 Vf (Xk)时 构成的寻优算法，称为求解无约束优化问题的基本牛顿法；对于迭代式 Xk+1 = Xk +a kSk，取搜索方向 Sk =-V 2 f (Xk)-1 Vf (Xk)，a k 为从 Xk 出发、沿牛顿方向做一维搜索获

13、得的最优步长，所构成的寻优算法，称为求解无约束优 化问题的阻尼牛顿法。搜索方向Sk = -V2 f (Xk)-1 Vf (Xk)称为牛顿方向。这里需要注意的是会求海塞阵的逆矩阵。3.5变尺度法我们把具有Xe = Xk a kAk Nf (Xk)迭代模式的寻优算法称为变尺度法。其搜索方向表达式为：Sk = AkNf (Xk)，称为拟牛顿方向，其中Ak称为变尺度矩 阵。在迭代开始的时候，A 0 = I ；随着迭代过程的继续，Ak -N 2 f (Xk)i Nf (Xk)。因此，变尺度法从梯度法出发，随着迭代过程的继续最终趋向于牛顿法。3.6共轭梯度法一、共轭方向的概念设H为对称正定矩阵，若有两个n

14、维向量S1和S 2，满足St H - S2 = 0，则称向量S1 与S2关于矩阵H共轭，共轭向量的方向称为共轭方向。若有一组非零向量S，S ，S满足St H -S = 0(i。j)，则称这组向量关于12nij矩阵H共轭。对于n元正定二次函数，依次沿着一组共轭方向进行一维搜索，最多n次即可得到 极值点。二、共轭方向的形成对于函数 f (X) = f (孔，x2,A ,x ) = 2XtHX + BtX + C沿任意方向S0在设计空间上任意做两条平行线，分别与目标函数等值线切于点Xi、X2，令S1 = X2 X1，则S0、S1关于矩阵H共轭。三、共轭梯度法对于迭代式 X k +1 = X k +a

15、 kS k，取搜索方向 S k+1 = Nf (X k +1) + & S kkNf (Xk+1)|2其中：S0 = Nf(X0)，& = k|W( Xk )|2共轭梯度法相邻两轮搜索方向是一对共轭方向。3.7鲍威尔法基本迭代公式仍旧是：Xk+1 = Xk +a kSk基本鲍威尔法每轮搜索分为两步：一环的搜索+在该环搜索完毕后生成的新方向上 的一维搜索。对于基本鲍威尔法，相邻两轮搜索生成的搜索方向是共轭的。修正鲍威尔法与基本鲍威尔法类似，所不同的是每环搜索后生成的新方向要利用鲍威尔条件判别其可用性。注意掌握鲍威尔条件的表达式和应用！每环搜索方向组的生成：第一环的搜索方向组就是各坐标轴方向2下一

16、环的搜索方向组由本环搜索方向组和本环生成的新方向共同确定，方法是： 若本环的搜索结果满足鲍威尔条件，则将本环搜索方向组中使目标函数下降量最大的方 向去掉，并将本环生成的新方向递补进去，就形成下一环的搜索方向组；若本环的搜索 结果不满足鲍威尔条件，则下一环的搜索方向组仍旧沿用本环搜索方向组不变。下一环搜索起点的确定：下一环搜索起点由本环搜索结果确定，方法是：若本环的搜索结果满足鲍威尔条件， 则以本环搜索终点为起点，沿新生成的方向作一维搜索，得到的新点作为本轮的搜索终 点，也是下一轮的搜索起点；若本环的搜索结果不满足鲍威尔条件，则取本环搜索终点 和反射点中目标函数值小的点作为本轮的搜索终点，也是下

17、一轮的搜索起点。这里需要注意的是反射点的计算：X,= 2 Xk - X k式中：Xk是本环起点Xk相对于本环终点Xk沿新生成方向的反射点。n+20n例：对于无约束目标函数 min f (X) = xi + 2x2 -4气-2x1 x2，利用修正 Powell法从11. 一 一X 0 = 1出发求最优解。1解：令 X 0 = X0 = 1P1 = P 0 =(匕，e)11 + aX1 = X1 +a=1001令 f(X 1) = 0得:a =03 -X1 = X1 +a=2111 + a则：2令 f(X 1) = 0 得：a = 0.5贝J： X1 =221.5该环生成的新搜索方向为：S1 =

18、X123121.5-1=0.5-X10对S1进行有效性判别：/1 = f (X 0) = -3f2=f (X2)= -7.5f3 = f (x 4)= -7A1 = f (X 0) 一 f (X1) = -3 - (-7) = 4=f (X11)一 f (X 2)= -7 -(-7.5) = 0.53151.5一1=20反射点 X1 = 2 X1 - X1 = 242故最大下降量A = A1 = 4故：f f 和(f - 2 f + f )(f - f3112312-)2 2A(f1 - f3)2 均成立方向S1可用以X1为起点，沿S1方向作一维搜索： 232+a=1.50.53 + 2a1.

19、5 + 0.5aX1 = X1 + aS 1 =32由 min f (X1) = f (X2 +aS1)得a = 2/5 = 0.4故,本轮寻优的终点为：X1 = X 3 =3.8一1.7做收敛性判别：X1 -X。| =1：2.82 + 0.72，应继续搜索下一轮寻优过程的起点为：X j =3.8一1.7下一轮寻优过程的搜索方向组为：(。2,S 1)约束优化方法约束优化方法要求大家重点掌握惩罚函数法，包括点法、外点法、混合法。一、外点法构造惩罚函数：min4 (X, rk) = f (X) + rk ma冲 g (X),0)2 + rkh (X)2 uv外点法既可以处理不等式约勺束优化问题，又可以芟理等式约束优化问题。需要注意的是：惩罚因子rk随迭代次数的增加是递增的，当rk 8时得到的解就是原问题的最优解。例：用外点法求解min f (X) = x 2 + x 2 - 2 x +1 s.t. 3 - X 0时 当3-X2 0时人合4令 Q= 2 气-2 = 01例 = 2X2 + 2rk (x2 - 3) = 01得：气=13rkV 1 + rkx * = lim x = 3