單純形加速

單純形加速(simplex acceleration)是單純形法的推廣，指單純形法中的擴展、壓縮、縮邊。是由Spendley等三人於1962年提出，並在1964年經Nelder等兩人加以改進的，為了避免與求解線性規劃問題套用較成熟的單純形法區別，有人建議稱之為可變多面體法。

基本介紹

• 中文名：單純形加速
• 外文名：simplex acceleration
• 所屬學科：數學
• 簡介：單純形法中的擴展、壓縮、縮邊
• 別稱：可變多面體法

基本介紹

二維時，一個三角形有三個頂點，n維時，凸多面體有n+1個頂點，幾何上這種凸多面體被稱為單純形。因構成圖形時，它所需的點數最少，故而得名，如圖1所示。

圖1（a）

圖2

*圖1（a）二維；

（b）三維，四個頂點（個）。

線上性規劃中，滿足約束的一切可行解構成凸多邊形，n個變數，可行解域就是凸多面體。可以證明，線性規劃的最優解一定可在凸集頂點上找到，尋優過程只是從一個頂點出發，進行疊代尋優，找到另一個頂點。因此疊代過程是有限的，這就是線性規劃中單純形算法的根據。最適於等式約束。

非線性規劃中的單純形法借用其“頂點尋優”的想法。但與線性規劃有很大不同。基本思路是：往最壞點的相反方向走，有可能找到較優點”。其基本步驟是對n個變數，在n維空間先構成一個有n+1個頂點的單純形，比較頂點上的函式值，去掉壞點，代以新點，構成新的單純形，以此逐步逼近最優點。它是由Spendley等三人於1962年提出，並在1964年經Nelder等兩人加以改進的，稱為單純形加速法。為了避免與求解線性規劃問題套用較成熟的單純形法區別，有人建議稱之為可變多面體法。

舉例說明

例如，設為二維無約束極小化問題的目標函式，在平面上取不在同一直線上的三個點，並以它們為頂點，構成一單純形(即三角形)，算出各頂點的函式值f(x)，f(x)和f(x)，如果，則x¹點最差，x³點最好，為了尋找極小點，應向最差點的反對稱方向進行搜尋，設線段的中點為，在的延長線上取點，使，稱為關於的反射點，算出的函式值。

1.擴展。若，說明搜尋方向有效，繼續沿向前擴展，取，其中α為擴展因子。

2.壓縮。若，說明x⁵點走得太遠，應壓縮，取，其中β為壓縮因子。

3.縮邊。若方向上所有點的函式值都大於，則不能沿此方向搜尋。這時，以為中心進行縮邊，例如，使頂點x¹和x²向x³移近一半距離，得新單純形，以此為基礎再進行尋優。