使用導(dǎo)數(shù)的最優(yōu)化方法課件

第十章使用導(dǎo)數(shù)的最優(yōu)化方法----研究無約束問題最優(yōu)化方法精確一維搜索的一個重要性質(zhì)：定理：最速下降法最速下降方向取搜索方向:步驟:例:第一次迭代解:第二次迭代例:最速下降法的收斂性定理：二次函數(shù)情形最速下降法表示為Kantorovich不等式定理（最速下降法—二次情形）定理：條件數(shù)非二次情形結(jié)論：在相繼兩次迭代中,梯度方向互相正交.牛頓法基本思想:用一個二次函數(shù)去近似目標(biāo)函數(shù)f(x),然后精確地求出這個二次函數(shù)的極小點.----一維搜索函數(shù)逼近法中的牛頓法的推廣.牛頓方向定理：步驟:用Newton法求解無約束問題會出現(xiàn)以下情形：（1）收斂到極小點。（2）收斂到鞍點。（3）Hesse矩陣不可逆，無法迭代下去。優(yōu)點:（1）Newton法產(chǎn)生的點列{x(k)}若收斂，則收斂速度快---具有至少二階收斂速率。(2)Newton法具有二次終止性。缺點:（1）可能會出現(xiàn)在某步迭代時，目標(biāo)函數(shù)值上升.（2）當(dāng)初始點遠(yuǎn)離極小點時，牛頓法產(chǎn)生的點列可能不收斂，或者收斂到鞍點，或者Hesse矩陣不可逆，無法計算.（3）需要計算Hesse矩陣的逆矩陣，計算量大.步驟:阻尼牛頓法用阻尼牛頓法求解下列問題:步驟:修正牛頓法共軛方向法共軛方向定義：例：定理1證明：定理2：證明：定理3：定理（擴(kuò)張子空間定理,expandingsubspacetheorem）共軛方向法步驟（適用于正定二次函數(shù)）從任意點出發(fā)，依次沿某組共軛方向進(jìn)行一維搜索求解非線性規(guī)劃問題的方法。結(jié)論：證明：共軛方向法步驟（適用于正定二次函數(shù)）共軛方向法步驟（適用于正定二次函數(shù)）例：共軛梯度法(ConjugateGradientMethod)(FR法)記號：在共軛梯度法中，初始點處的搜索方向取為該點的負(fù)梯度方向，即取而以下各共軛方向d(k)由第k次迭代點x(k)處的負(fù)梯度-gk與已經(jīng)得到的共軛向量d(k-1)的線性組合來確定。以此類推，得定理:步驟(FR共軛梯度法）例:例:用于一般函數(shù)的共軛梯度法與原方法的主要區(qū)別：迭代的延續(xù)方法：步驟(FR共軛梯度法）變尺度法(VariableMetricMethod)

擬牛頓法(Quasi-NewtonMethod)這是一種求解無約束極值問題的有效算法，由于它既避免了計算二階導(dǎo)數(shù)、矩陣及其求逆過程，又比最速下降法的收斂速度快，特別是對高維問題具有顯著的優(yōu)越性，所以，它被公認(rèn)為求解無約束極值問題最有效的算法之一。牛頓法的缺點:（1）可能會出現(xiàn)在某步迭代時，目標(biāo)函數(shù)值上升.（2）當(dāng)初始點遠(yuǎn)離極小點時，牛頓法產(chǎn)生的點列可能不收斂，或者收斂到鞍點，或者Hesse矩陣不可逆，無法計算.（3）需要計算Hesse矩陣，計算量大.基本原理：阻尼牛頓法:擬牛頓條件擬牛頓法步驟秩1校正一般策略：校正矩陣擬牛頓法步驟DFP算法(變尺度法)定義：DFP公式DFP法計算步驟:例:用DFP方法求解下列問題：第一次迭代第二次迭代例:用共軛梯度法求解下列問題：第一次迭代第二次迭代DFP算法(變尺度法)定理：推論：定理：信賴域方法基本思想：在當(dāng)前迭代點的某個鄰域內(nèi)（通稱取為以當(dāng)前迭代點為中心的球域，稱為信賴域），根據(jù)已知的有關(guān)優(yōu)化問題的信息，確定一個模型函數(shù)來近似原來的目標(biāo)函數(shù)；然后，在該領(lǐng)域內(nèi)極小化模型函數(shù)確定可能的改進(jìn)點；最后，根據(jù)一定標(biāo)準(zhǔn)決定是否接受這個可能的改進(jìn)點。基本原理子問題信賴域半徑的確定通過比較迭代過程中模型函數(shù)和目標(biāo)函