運籌學與最優(yōu)化第二章-下降算法與線搜索法

1、最優(yōu)化方法,第2講無約束優(yōu)化問題的下降算法與線性搜索,先欣賞幾個函數的圖形,先欣賞幾個函數的圖形,最優(yōu)化問題數學模型,凸規(guī)劃—求凸函數在凸集上的最小值問題,第二講無約束優(yōu)化問題的下降算法與線性搜索,最優(yōu)性條件下降算法的一般步驟線性搜索,無約束問題解的最優(yōu)性條件,無約束最優(yōu)化問題,嚴格局部最優(yōu)解,局部最優(yōu)解,嚴格全局最優(yōu)解,局部最優(yōu)解的必要性條件,一階必要性條件二階必要性條件存在一些點，滿足一階和二階必要性條件，

2、但不是局部最優(yōu)解,必要性證明,一階必要性條件 ：利用一階Taylor展式對固定的將d用-d替換，得到由d的任意性，得到,注意這個條件不是充分的。,二階必要性條件,利用二階Taylor展式,由于x*是局部最小解，故 且存在充分小的正數 ，對于所有的,令 ，得到,必要性證

3、明,局部最優(yōu)解的充分性條件,證明：令 為 的最小特征值，則對所有的 d,當 足夠小時， 與 相比， 可以忽略不計,無約束凸優(yōu)化問題的最優(yōu)性條件,證明,（1）,證明,（2）,復習：關于多元函數的梯度和Hessian矩陣,梯度的意義,,,,,●,,,上升方向,下降方向,,變化率為零的方向,等值線(

4、面),下降方向,下降方向 d,觀察一階Taylor展式,下降算法的一般步驟,最速下降法：Newton法：,最速下降法具有慢的收斂速度,Newton法具有很快的收斂速度（二階）,步長 的選?。壕€性搜索,步長 的選取,非精確線性搜索,步長 的選取,Armijo型線性搜索,思想：逐漸減少步長，直到是目標更優(yōu),用進退法實現Armijo搜索：逐漸變小以滿足Armijo搜索條件,缺點：步長可能過小,非精確線性搜索