無約束優(yōu)化方法11變尺度法

一：尺度矩陣的概念變量的尺度變換是放大或縮小各個坐標(biāo)，通過尺度變換可以把函數(shù)的偏心程度降低到最低限度。尺度變換技巧能顯著地改善幾乎所有極小化方法的收斂性質(zhì)。如：求目標(biāo)函數(shù)的極小點。若將上例的目標(biāo)函數(shù)引入變換23若矩陣G是正定的，則總存在矩陣Q，使得：將函數(shù)的偏心降為0對于一般二次函數(shù)如果進行尺寸變換則在新的坐標(biāo)系中，函數(shù)的二次項變?yōu)椋▎挝痪仃嚕┯糜页说仁絻蛇叄迷儆肣左乘等式兩邊，得所以4

這說明二次函數(shù)矩陣G的逆陣，可以通過尺度變換矩陣Q來求得。牛頓方向便可寫成牛頓迭代公式變?yōu)?例子：變換6則在變換后的坐標(biāo)系中，矩陣G變?yōu)橹恍柰ㄟ^一次迭代即可求得極小點7比較牛頓法迭代公式和梯度法迭代公式可以看出，差別在于牛頓法中多了部分。

實際上是在x空間內(nèi)測量距離大小的一種度量，稱作尺度矩陣H如在未進行尺度變換前，向量x長度的概念是變換后向量x對于H尺度下的長度8

這樣的長度定義，在確定“長度”這個純量大小是，使得某些方向起的作用比較大，另一些方向起的作用比較小。

它和梯度法的公式只差一個H，牛頓法就可以看成是經(jīng)過尺度變換后的剃度法。經(jīng)過尺度變換，使函數(shù)的偏心率減小到0，函數(shù)的等值面變成球面，使設(shè)計空間中任意點處的梯度都通過極小點。（對二次函數(shù)）。

為使這種尺度有用，必須對一切非零向量的x均有，既然牛頓法迭代公式可用尺度變換矩陣表示出來，即9變尺度矩陣的建立

對于一般函數(shù)f(x)，當(dāng)用牛頓法尋求極小點時，其牛頓迭代公式為

為了避免在迭代公式中計算海賽矩陣的逆矩陣，可以用在迭代中逐步建立的變尺度矩陣

來替換，即構(gòu)造一個矩陣序列來逼近海賽逆矩陣序列。10

1）為了保證迭代公式具有下降性質(zhì)，要求Hk中的每個矩陣都是對稱正定的

其中是從出發(fā)，沿方向搜索而得到的最佳步長。

為了使變尺度矩陣確實與近似，并必須附加某些條件：

若要求搜索方向為下降方向，即要求也就是，即，即應(yīng)為對稱正定。2）要求之間的迭代具有簡單的形式。顯然

為最簡單的形式，其中為校正矩陣。上式稱作校正公式。11所謂擬牛頓條件可以推導(dǎo)：3）要求必須滿足擬牛頓條件。設(shè)迭代過程已經(jīng)進行了k+1步，，

均已求出，現(xiàn)在推導(dǎo)

所需要的條件。當(dāng)f(x)為具有正定矩陣G的二次函數(shù)時

因為具有正定海賽矩陣的一般函數(shù)，在極小點附近可用二次函數(shù)很好的近似，所以如果迫使?jié)M足類似于上式的關(guān)系那么就可以很好地近似于。12上述關(guān)系稱擬牛頓條件

根據(jù)上述擬牛頓條件，不通過海賽矩陣求逆就可以構(gòu)造一個矩陣來逼近海賽矩陣的逆陣，這類方法統(tǒng)稱作擬牛頓法。由于變尺度矩陣的建立應(yīng)用了擬牛頓條件，所以變尺度法也是屬于一種擬牛頓法。還可以證明，變尺度法對于具有正定矩陣G的二次函數(shù)，能產(chǎn)生對G共軛的搜索方向，因此變尺度法又可以看成是一種共軛方向法。13三、變尺度法的一般步驟

對一般多元函數(shù)f(x)，用變尺度法求極小點，其一般步驟是：1）選定初始點和收斂精度。2）計算，選取初始對稱正定矩陣（例如），置。3）計算搜索方向。4）沿方向進行一維搜索，計算5）判斷是否滿足迭代終止準(zhǔn)則，若滿足則，停機。6）當(dāng)?shù)鷑次后還沒找到極小點時，重置為單位矩陣I，并以當(dāng)前設(shè)計點為初始點，返回到2進行下一輪迭代，否則轉(zhuǎn)到7。147）計算矩陣，置返回到3。

對于校正矩陣，可由具體的公式來計算，不同的公式對應(yīng)不同的變尺度法，但不論哪種變尺度法，必須滿足擬牛頓條件

滿足上式的有無窮多個，因此上述變尺度法（屬于擬牛頓法）構(gòu)成一族算法。1516DFP算法

在變尺度算法中，校正矩陣采用不同的形式，就形成不同的變尺度算法。DFP算法中的校正矩陣如下：

其中、是n維待定向量，、是待定常數(shù)，、都是對稱秩一的矩陣根據(jù)校正矩陣要滿足擬牛頓條件17滿足上面方程的待定向量和有多種取法，我們?nèi)∽⒁獾胶投际菙?shù)量，不妨設(shè)這樣就可以定出從而可得DFP算法的校正公式18

當(dāng)初始矩陣選為對稱正定矩陣時，DFP算法將保證以后的迭代矩陣都是對稱正定的，即使將DFP算法施用于非二次函數(shù)也是如此，從而保證算法總是下降的。這種算法用于高維問題（如20個變量以上），收斂速度快，效果好。DFP算法是無約束優(yōu)化方法中最有效的方法之一，因為它不單純是利用向量傳遞信息，還采用了矩陣來傳遞信息。DFP算法是戴維登（Davidon）與1959年提出的，后來由弗萊徹（Fletcher）和鮑威爾（Powell）與1963年作了改進，故用三人名字的字頭命名。19坐標(biāo)輪換法

該方法是每次搜索只允許一個變量變化，其余變量保持不變。他把多變量問題轉(zhuǎn)換成單變量的優(yōu)化問題，在搜索過程中可以不需要目標(biāo)函數(shù)的導(dǎo)數(shù)。20

否則，進行下一輪搜索，一直到