第 五 章 无约束最优化方法.

Presentation on theme: "第 五 章 无约束最优化方法."— Presentation transcript:

1 第 五 章 无约束最优化方法

2 5.2 最速下降法 第五章 无约束最优化 在迭代点 x(k) 取方向 d(k)= －▽f(x(k) ) 精确一维搜索
（f） min f(x) f : Rn→R 5.1 最优性条件 设 f 连续可微 必要条件：若x*－l.opt. 则▽f(x*)=0 (驻点)。 当 f 凸时， x*－l.opt. ←→ ▽f(x*)=0 注意： f(x) ≥f(x*)+ ▽Tf(x*)(x-x*),  x. 故 f(x*) ≤f(x)，  x. （ 由于▽Tf(x*) =0） 5.2 最速下降法 在迭代点 x(k) 取方向 d(k)= －▽f(x(k) ) 精确一维搜索 最 速 下降法：梯度方向函数值变化最快的方向

3 第五章 无约束最优化 5.2 最速下降法（续） Yes d(k)= －▽f(x(k) ) x(1), ε >0, k=1 k=k+1
5.2 最速下降法（续） x(1), ε >0, k=1 || ▽f(x(k) ) ||< ε? Yes stop. x(k) –解 No d(k)= －▽f(x(k) ) 解 min f(x(k)+λ d(k)) s.t. λ >0 得 x(k+1)=x(k)+λkd(k) k=k+1

4 5.3 Newton法及其修正 第五章 无约束最优化 特点：全局收敛，线性收敛，易产生扭摆现象而造成早停。
5.2 最速下降法（续） 特点：全局收敛，线性收敛，易产生扭摆现象而造成早停。 （当x(k)距最优点较远时，速度快，而接近最优点时，速度下降） 原因：f(x)=f(x(k))+▽Tf(x(k))(x-x(k)) + o||x-x(k)|| 当 x(k)接近 l.opt.时 ▽f(x(k) ) →0，于是高阶项 o||x-x(k)||的影响可能超过▽Tf(x(k))(x-x(k)) 。 5.3 Newton法及其修正 一、 Newton法： 设f(x)二阶可微，取f(x)在x(k)点附近的二阶Taylor近似函数： qk(x)=f(x(k))+ ▽Tf(x(k))(x-x(k)) +1／2 (x-x(k))T▽2f(x(k)) (x-x(k)) 求驻点： ▽ qk(x)= ▽f(x(k))+ ▽2f(x(k)) (x-x(k))=0

5 得s(k) , x(k+1)=x(k)+s(k)
第五章 无约束最优化 Newton法： （续） 当▽2f(x(k)) 正定时，有极小点： x(k+1)=x(k)-[▽2f(x(k)) ]-1 ▽f(x(k)) ——Newton迭代公式 实用中常用 ▽2f(x(k)) S= -▽f(x(k)) 解得s(k) x(k+1)=x(k)+s(k) x(1), ε >0, k=1 ▽2f(x(k)) S= -▽f(x(k)) 得s(k) , x(k+1)=x(k)+s(k) || s(k) ||< ε? STOP.x(k+1)—l.opt Yes No k=k+1 实用中，判断 若▽2f(x(k)) 非正定时 进行相应处理

6 第五章 无约束最优化 Newton法： （续） 特点：二阶收敛，局部收敛。
（当x(k)充分接近x*时,局部函数可用正定二次函数很好地近似，故收敛很快） 二次终结性：当f(x)为正定二次函数时，从任意初始点可一步迭代达到最优解。 设f(x)=1／2xTQx+PTx+r , Qn×n对称正定，P∈ Rn, r∈ R.  x(1), ▽f(x(1))=Q x(1) +P ▽2f(x(1))=Q 迭代： x(2) = x(1) - Q –1(Qx(1) +P) = - Q –1 P (驻点即opt.) 主要缺点： (1)局部收敛 (2)用到二阶Hesse阵，且要求正定 (3)需计算Hesse阵逆或解n阶线性方程组，计算量大

7 第五章 无约束最优化 5.3 Newton法及其修正 二、 Newton法的改进：
(1)为减小工作量，取m（正整数），使每m次迭代使用同一个Hesse阵，迭代公式变为： x(km+j+1)=x(km+j)-[▽2f(x(km))]-1 ▽f(x(km+j)) j=0,1,2, …,m-1 , k=0,1,2, … 特点：收敛速度随m的增大而下降 m=1时即Newton法， m→∞ 即线性收敛。 (2)带线性搜索的Newton法： 在Newton迭代中，取d(k)= -[▽2f(x(k)) ]-1 ▽f(x(k)) , 加入线性搜索：min f(x(k)+λk d(k)) 求得λk , x(k+1)=x(k)+λkd(k) 特点：可改善局部收敛性，当d(k)为函数上升方向时，可向负方向搜索，但可能出现± d(k)均非下降方向的情况。

8 第五章 无约束最优化 (3)Goldstein-Price方法(G-P法)：
5.3 Newton法及其修正 二、 Newton法的改进： （续） (3)Goldstein-Price方法(G-P法)： 取 d(k)= -[▽2f(x(k)) ]-1 ▽f(x(k)) ， ▽2f(x(k)) 正定 - ▽f(x(k)) ，否则 采用下列精确一维搜索： 求λk，使其中δ ∈(0,1／2) 1° f(x(k)+λk d(k)) ≤ f(x(k))+ δ ▽f(x(k)) Td(k) λk 2° f(x(k)+λk d(k)) ≥f(x(k))+ (1-δ) ▽f(x(k)) Td(k) λk 特点：在一定条件下， G-P法全局收敛。 但当▽2f(x(k)) 非正定情况较多时，收敛速度降为接近线性。

9 (4)Levenberg-Marguardt法（L-M法）： 主要思想：
第五章 无约束最优化 5.3 Newton法及其修正 二、 Newton法的改进： （续） (4)Levenberg-Marguardt法（L-M法）： 主要思想： 用[▽2f(x(k)) +μ I ] 取代▽2f(x(k)) 进行迭代，其中I 为单位矩阵。 μ>0 使 [▽2f(x(k)) +μ I] 正定， μ尽量小。 特点：全局二阶收敛。

10 第五章 无约束最优化 5.4 共轭梯度法 一、共轭梯度法的方向：
设f(x)=(1/2)xTGx+bTx+c Gn×n对称正定，b∈ Rn,从最速下降方向开始，构造一组共轭方向： 设初始点x(1),取d(1)= -▽f(x(1)) ……① (最速下降方向) 设k≥1,已得到k个相互共轭的方向d(1),d(2), …,d(k),以及，由x(1)开始依次沿上述方向精确一维搜索得到点x(2), …，x(k),x(k+1).即有下式： x(i+1)=x(i)+αid(i) , i=1,2, …,k ……② 精确一维搜索保证方向导数为0： ▽fT(x(i+1))d(i)=0, i=1,2, …,k ……③ 在x(i+1)点构造新方向d(k+1)为-▽f(x(k+1)) 与d(1),d(2), …,d(k)的组合： ④

11 第五章 无约束最优化 5.4 共轭梯度法 一、共轭梯度法的方向： （续） 使d(k+1)与d(1),d(2), …,d(k)都共轭：
d(k+1) TG d(j) =0 , j= 1,2, …,k ……⑤ Gram-Schmidt过程： i, j= 1,2, …,k 记 y(j)= ▽f(x(j+1)) -▽f(x(j)) =G(x(j+1)-x(j))=αjGd(j) …….⑥ 根据⑥式，有 d(i)T y(j) = αj d(i)T G d(j)=0 , i≠j ……⑦ 根据④，⑤，⑥有 d(k+1) T y(j) = αj d(k+1)T G d(j)=0 , j= 1,2, …,k ……⑧ ⑧′ 这里的j应为i

12 第五章 无约束最优化 5.4 共轭梯度法 一、共轭梯度法的方向： （续）
 j≤k, i<j 有 ▽f(x(j+1))T d(i)= ……⑨ 由⑥式 由⑨式 ▽f(x(j+1))T ▽f(x(i))=  i<j≤k …… ⑩ (由④式 ) 根据⑧及⑥得： j=1,2, …,k-1 - ▽f(x(k+1))T [▽f(x(j+1)) - ▽ f(x(j))]+βj(k) d(j)T y(j)=0

13 第五章 无约束最优化 5.4 共轭梯度法 一、共轭梯度法的方向： （续）
上式中由⑩式有： - ▽f(x(k+1))T ▽f(x(j+1)) =0 由⑥式有： βj(k) d(j)T y(j)= βj(k) αjd (j)T Gd(j) 于是 βj(k) = 故④式中只有 βk(k) ≠0, 记βk = βk(k) 可得到公式： d(k+1)= - ▽f(x(k+1))+ βk d(k) 当 j=k时，由⑧′, ⑥式得： (11) 注意：

14 第五章 无约束最优化

15 第五章 无约束最优化 二、算法流程图 y N k=n? x(1), ε >0 d(1)=-▽ f(x(1)),k=1 k=k+1
Stop.x(k)—解 解 min f(x(k)+λ d(k)) s.t. λ >0 得 λ k x(k+1)=x(k)+λk d(k) k=n? x(1)=x(n+1) 求β k d(k+1)= -▽ f(x(k+1))+β kd(k) y N 重新开始

16 2、每步迭代只需存储若干向量（适用于大规模问题）； 3、有二次终结性（对于正定二次函数，至多n次迭代可达opt.）
第五章 无约束最优化 5.4 共轭梯度法 三、算法特点： 1、全局收敛（下降算法）；线性收敛； 2、每步迭代只需存储若干向量（适用于大规模问题）； 3、有二次终结性（对于正定二次函数，至多n次迭代可达opt.） 注：对不同的β k公式，对于正定二次函数是相等的，对非正定二次函数，有不同的效果，经验上PRP效果较好。

17 第五章 无约束最优化 5.5 变尺度法 一、变尺度法的基本思路： (f)min f(x), f: R n→ R 1、基本思想：
5.5 变尺度法 一、变尺度法的基本思路： (f)min f(x), f: R n→ R 1、基本思想： 用对称正定矩阵H(k)近似▽2f(x(k)), 而H(k)的产生从给定H(1)开始逐步修整得到。 2、算法框图： x(1),H(1)对称 ε>0, k=1 d(k)=-H(k) ▽ f(x(k)) 一维搜索得λk x(k+1)=x(k)+ λk d(k) ||x(k+1)-x(k)||< ε? 修正H(k)产生H(k+1) Stop. x(k+1)----解 k=k+1 y N

18 第五章 无约束最优化 5.5 变尺度法 一、变尺度法的基本思路： （续） 3、拟Newton方程：
5.5 变尺度法 一、变尺度法的基本思路： （续） 3、拟Newton方程： 记：s(k)=x(k+1)-x(k) , y(k)=▽ f(x(k+1))-▽ f(x(k)) 当 f 为二次函数时：f(x)=1∕ 2xTBx+c T x+b ▽ f= B x+c 有 y(k)=Bs(k) 或 s(k)=B-1 y(k) 称 H y=S 或 y=BS 为拟Newton方程。 显然 当H 正定时, B-1=H. 4、”近似”： 对于f(x)的二阶Taylor展式，舍去高阶项， 有 y(k) ≈ ▽ 2f(x(k))s(k) 或 s(k) ≈ (▽ 2f (x(k)))-1 y(k) 用矩阵B(k)或H(K)分别取代▽ 2f(x(k)) 或者 (▽ 2f (x(k)))-1 使拟Newton方程成立，可看作是对▽ 2f(x(k)) 或(▽ 2f (x(k)))-1的一种近似。此种近似H 或 B 不唯一。

19 第五章 无约束最优化 5.5 变尺度法 一、变尺度法的基本思路： （续） 5、变尺度法的主要特点：
5.5 变尺度法 一、变尺度法的基本思路： （续） 5、变尺度法的主要特点： 　⑴只需用到函数的一阶梯度；（Newton法用到二阶Hesse阵） 　⑵下降算法，故全局收敛； ⑶不需求矩阵逆；（计算量小） ⑷一般可达到超线性收敛；（速度快） ⑸有二次终结性。 二、DFP ( Davidon(1959),Fletcher and Powell(1963) ) 法和 BFGS ( Broyden(1970), Fletcher (1970),Goldfarb(1970),Schanno(1970) ) 法: 1、DFP法： 以下省去各量上标，x, s, y, H 表示第k 步的量， 等表示第k+1步的量。

20 第五章 无约束最优化 5.5 变尺度法 二、DFP 法和BFGS 法: 1、DFP法： （续）

21 第五章 5.5 变尺度法 二、1、DFP法： （续） Ex. 用DFP法求解 10x12+x22
第五章 变尺度法 二、1、DFP法： （续） Ex. 用DFP法求解 10x12+x22 解：取初始点x(1)=(1∕10,1)T, H(1)=I (单位矩阵) 得到如下结果： （计算过程见下页）

22 第五章 变尺度法 二、1、DFP法： （续） 计算过程：

23 第五章 变尺度法 二、1、DFP法： （续）

24 第五章 5.5 变尺度法 二、1、DFP法： （续） 定理：设H对称正定，sTy>0那么DFP法产生的 对称正定。
第五章 变尺度法 二、1、DFP法： （续） 定理：设H对称正定，sTy>0那么DFP法产生的 对称正定。 注：下列各情况下有sTy>0： 1º f(x)为正定二次函数； 2º 精确一维搜索时； 3º 前章介绍的不精确一维搜索时。 可以证明： DFP法在精确一维搜索前提下，超线性收敛。 2、BFGS法 若把前面的推导，平行地用在y=Bs公式上，可得到

25 用此公式求方向时，需用到矩阵求逆或解方程： d= -B-1▽ f(x) 或 Bd= -▽ f(x)
第五章 变尺度法 二、2、BFGS法（续） 用此公式求方向时，需用到矩阵求逆或解方程： d= -B-1▽ f(x) 或 Bd= -▽ f(x) 由于每次只有秩2的变换，这里的计算量仍可以降下来。为了得到H-公式，可对上面 求逆（推导得）： BFGS法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用前文中介绍的不精确一维搜索有全局收敛性。

26 第五章 变尺度法 三、Broyden族 当在秩2公式中，α、β 任意选取时可得到不同的公式，经过理论推导，可得到下列结果：

27 第五章 变尺度法 三、Broyden族（续）

28 第五章 无约束最优化 5.6 直接算法 min f(x) 一、单纯形法及可变多面体算法 1、单纯形法基本思路：
设 x(0),x(1),…, x(n)是R n中n+1个点构成的一个当前的单纯形。 比较各点的函数值得到：x max,x min使 f( x max)=max{f(x(0)),f(x(1)), …,f(x(n))} f( x min)=min{f(x(0)),f(x(1)), …,f(x(n))} 取单纯形中除去x max点外，其他各点的形心： 去掉x max，加入x(n+1)得到新的单纯形。 重复上述过程。

29 第五章 5.6 直接算法 一、1、单纯形法基本思路： （续） 几点注意： ⑴当x(n+1)又是新单纯形的最大值点时，取次大值点进行反射；
第五章 5.6 直接算法 一、1、单纯形法基本思路： （续） 几点注意： ⑴当x(n+1)又是新单纯形的最大值点时，取次大值点进行反射； ⑵若某一个点x′出现在连续m个单纯形中的时候，取各点与x′连线的中点（n个）与x′点构成新的单纯形，继续进行。 经验上取 m≥ 1.65n+0.05n2 例如：n=2时，可取m≥ 1.65× × 4 =3.5 可取 m=4. 1 2 3 4 5 7 8 9 10 6 11 12 13

30 第五章 5.6 直接算法 一、1、单纯形法基本思路： （续） 优点：不需求导数，不需要一维搜索。 缺点：无法加速，收敛慢，效果差。
第五章 5.6 直接算法 一、1、单纯形法基本思路： （续） 优点：不需求导数，不需要一维搜索。 缺点：无法加速，收敛慢，效果差。 2、改进单纯形法： （可变多面体算法） 设第k步迭代得到n+1个点： x(0),x(1),…, x(n) ，得到x max,x min及 通过下列4步操作选新迭代点： 1º 反射： 取反射系数α >0,(单纯形法中α =1) 2º 扩展：给定扩展系数γ >1,计算。（加速）

31 第五章 5.6 直接算法 一、 2、改进单纯形法： （续） 若f(y(1))<f(x min), 则
第五章 5.6 直接算法 一、 2、改进单纯形法： （续） 若f(y(1))<f(x min), 则 若f(y(1))> f(y(2)), 那么y(2)取代x max; 否则， y(1)取代x max 。若max{f(x(i))| x(i) ≠x max } ≥ f(y(1)) ≥ f(x min), y(1)取代x max 。 3° 收缩：若f(x max )> f(y(1)) > f(x(i)), x(i) ≠x max ,计算 ,以y(3)取代x max 。 4 ° 减半：若f(y(1)) > f(x max ), 重新取各点，使 x(i)= x min +1∕ 2(x(i) - x min ) 得到新单纯形。 经验上：α=1,0.4≤β≤0.6, 2.3≤γ≤3.0 . 有人建议:α=1, β=0.5， γ=2 。 算法停机准则取：

32 第五章 5.6 直接算法 二、模式搜索法： Hooke & Jeeves 1961 1、基本思想与主要过程：
第五章 5.6 直接算法 二、模式搜索法： Hooke & Jeeves 1、基本思想与主要过程： △利用两类移动（探测性移动和模式性移动）进行一步迭代： 探测性移动的目的：探求一个沿各坐标方向的新点并得到 一 个“有前途”的方向； 模式性移动的目的：沿上述“有前途”方向加速移动。 △主要过程：第k步迭代，设已得到x(k) 1°探测性移动： 给定步长αk ，设通过模式性移动得到y(0), 依次沿各坐标方向e(i)=(0, …,1,0, …,0)T i 移动αk步长：i=0,1, …,n-1 , =y(i)+ e(i+1) 若f( )<f(y(i)), 则 y(i+1) =

33 第五章 5.6 直接算法 二、1、基本思想与主要过程： （续） 否则取 =y(i)+ e(i+1)
第五章 5.6 直接算法 二、1、基本思想与主要过程： （续） 否则取 =y(i)+ e(i+1) 若f( )<f(y(i)), 则 y(i+1) = 否则 y(i+1) = y(i) 最后得到y(n) 。 若f(y(n) )<f(x(k)), 令x(k+1)=y(n). 2°模式性移动： x(k+1) - x(k)为一个有前途的方向，取 y(0)= x(k+1) +(x(k+1) - x(k))=2 x(k+1) - x(k) [f(y(0))<f(x(k+1) )?] 3 °几点措施： ①若探测性移动得到y(n)使f(y(n) ) ≥f(x(k)), 则跳过模式性移动而令y(0)=x(k) 重新进行探测性移动，初始y(0)=x(1) ；

34 第五章 5.6 直接算法 二、1、基本思想与主要过程： （续） ②若y(n)= y(0) （即每一个坐标方向的移动都失败），减小
第五章 5.6 直接算法 二、1、基本思想与主要过程： （续） ②若y(n)= y(0) （即每一个坐标方向的移动都失败），减小 αk ，重复上述过程。 ③当进行到αk充分小（ αk <ε ）时，终止计算。最新的 迭代点x(k)为解。 例： y(0)=x(1) y(1) y(2)=x(2) y(0) y(2)=x(3) y(2)=x(4) = y(1) = y(0) y(2) (f(y(2)) ≥f(x(4))) y(2)=x(5) y(1) = y(0)

35 第五章 5.6 直接算法 二、2、算法： i<n? 2 1 初始x, α ,y(0)=x, ε>0 计算f=f(x)
第五章 5.6 直接算法 二、2、算法： 初始x, α ,y(0)=x, ε>0 计算f=f(x) f1=f(y(0)),i=1 y(i)=y(i-1)+ αe(i) 计算f2=f(y(i)) f2<f1? f1=f2 i<n? yes 1 No i=i+1 2 y(i)=y(i-1)+ (-α)e(i) y(i)=y(i-1)

36 第五章 5.6 直接算法 二、2、算法： (续) 1 2 yes ㄡ =y(n), y(0)=2ㄡ -x f1<f ?
第五章 5.6 直接算法 二、2、算法： (续) 1 f1<f ? No yes ㄡ =y(n), y(0)=2ㄡ -x x=ㄡ ,f=f(x) y(n)=x? y(0)=x Yes α<ε ? α=0.1 α 2 停；x为解