1、第三章 無約束最優化的梯度方法1.最速下降法假定我們已經迭代了次，獲得了第個迭代點。從出發，顯然應沿下降方向進行，由于負梯度方向是最速下降方向，因此沿負梯度方向應該是有利的。因此，取搜索方向。此時有：如將該方法應用于二次函數，則可求出的顯式表達式。 2.Newton法適用條件：如果目標函數在上具有連續的二階偏導數，其Hesse矩陣正定。基本想法：考慮從到的迭代過程。在點處用二次函數來逼近，即：3.共軛方向法與共軛梯度法 1) 共軛方向法定義1:設是對稱正定矩陣。若維空間中非零向量系滿足， ,則稱是共軛的，或稱的方向是共軛方向。定理1:若非零向量系是共軛的，則這個向量線性無關。推論：在維空間中，

2、互相共軛的非零向量的向量個數不超過。定義2:設是線性無關的向量系，是任意實數。對于任意指定的，稱形式為的向量集合稱為由點和向量系所生成的線性流形，記為。定理2:假設：為對稱正定矩陣非零向量是共軛向量系；對二次目標函數順次進行如下次直線搜索：，其中是任意選定的初始點。則,是二次函數在線性流形上的極小點。證明：前面已經證明由條件可知上式左乘后再在兩邊加上，得：即：由上式有 ，將所得等式兩邊左乘，有證明:按條件，則存在一組數使得同樣，對于任意上面兩式相減得由結論可知由于是正定的，因此是在線性流行上的極小點。當時，線性流行就是整個維空間了，因此此時就是中的極小點。共軛方向法：已知：具有正定矩陣的二次目

3、標函數和終止限。選定初始點和具有下降方向的向量；置。作直線搜索。判別是否滿足：若滿足，停機。提供共軛方向，使得，k=k+1二次函數的直線搜索：共軛向量系的構造方法：先選定個線性無關的向量系，令設已求得共軛向量，現在來求令為使與共軛，應有：，由此解得：于是共軛方向法的適用范圍：可用于非二次函數，首先通過Taylor公式用二次函數來逼近非二次函數。其次，可用來構造共軛向量系，這要求充分地靠近。2) 共軛梯度法初始共軛向量恰好取為初始點處的負梯度，以下各共軛方向由第迭代點處的負梯度與已得到的共軛向量的線性組合來確定。因為該方法每一個共軛向量都是依賴于迭代點處的負梯度構造出來的，所以稱為共軛梯度法。設

4、已求得共軛向量，現在來求由，知和是線性無關的，取考慮與共軛，需滿足：于是有：現在證明除與共軛外，還與共軛。對依次計算 由于是共軛向量，因此，因為又因為,從共軛向量系構建方法可以看出，迭代點處的梯度是共軛向量系的線性組合。， 因此有：，,從而證明了與共軛。共軛梯度法在非二次函數中的應用：為了把共軛梯度法應用在非二次函數中，有必要消去表達式中的。由于因為，根據表達式的不同，可得到四種共軛梯度算法。最常采用的是第二種表達方式。4.變尺度法1)基本想法考慮Newton迭代公式，變尺度法就是要消除這個迭代公式中的Hesse逆矩陣，為此擬采用某種近似矩陣來替換它，即構造一個矩陣序列去逼近。因此，迭代公式為

5、其中可通過從出發沿作直線搜索來確定。為使確實與近似并具有容易計算的特點，對附加下列條件。要求對稱正定，保證迭代公式具有下降性質。如對稱正定，則，保證迭代公式具有下降性質。要求之間的迭代具有簡單的形式。，其中稱為校正矩陣，上式稱為校正公式。必須滿足擬Newton條件對于二次函數而言,有:上面兩式相減有: 如的逆存在,則有成立,表明能很好近似。如記，于是擬Newton條件可寫為：擬牛頓法算法：已知：目標函數及其梯度，終止準則。選定初始點；計算，選定初始矩陣。計算搜索方向。作直線搜索。如滿足終止準則，停機。計算。，轉。2)校正公式(1)對稱秩1算法(SR1法)校正公式取為其中是維待定非零向量，是待定常數，由于校正公式必須滿足擬牛頓條件，于是有：。取，于是校正公式為：對稱秩1算法的性質：性質1:設將SR1法施用于具有對稱正定矩陣的二次函數，如果初始矩陣是對稱的。迭代點是互異的。當時，那么有：()此算法所生成的搜索方向是互相共軛的。()對，性質2:若性質1的條件都滿足，并且經過次迭代才求到極小點，則。(2)DFP算法考慮如下形式的校正公式由于校正公式必須滿足擬牛頓條件，于是有：取，再令，于是有：，校正公式為：DFP算法性質：性質1:設將DFP法施用于具有對稱正定矩陣的二次函數，如果初始矩陣是對稱的。迭代點是互異的。那么