一維搜尋
一維搜尋：對一維目标函數尋求最優解
确定單峰區間
試探法：斐波那契法、黃金分割法（0.618法）；插值法：牛頓法
試探法：将單峰區間逐漸縮小，确定X*的近似值。
0.618法：
注：0.618是黃金分割數
無限制優化方法
方法分類
共轭方向：圖中S1與S2為共轭方向
注：對于等值線為同心圓或同心橢圓的目标函數，在一點引出一條線必與某個等值線相切
一維正定的二次函數
X0 + α0*S0 = X1 S0是随機給的，總有一條等值線與S0相切，交點為X1
X1 + α1*S1 = X* 如何找到S1，使得X1+S1為X*
注：X與S為矢量，α為标量
将目标函數近似為二次函數，得出S0*A*S1=0，稱S0與S1為關于A的共轭向量
注：A的共轭向量不唯一，即S0*A*S1=0，也可能S0*A*S3=0
共轭的定義
正交是共轭的特例，共轭是正交的推廣
二維正定矩陣A，至多兩次便可收斂到X*
三維正定矩陣A，至多三次便可收斂到X*
二維正定的二次函數，S=X2-X0 為共轭方向
S2*A*S=0
共轭方向法
第一輪
方向：x1、x2、x3軸
初始點X0
X0+α1*S1 = X1 S1方向沿x1軸
X1+α2*S2 = X2 S2方向沿x2軸
X2+α3*S3 = X3 S3方向沿x3軸
連接配接X0與X3即為方向S4，确定合适的步長α4
X0+α4*X3 = X4
第二輪
方向：x2、x3軸、第一輪中的S4
初始點X4，X0=X4
X0+α1*S1 = X1 S1方向沿x2軸
X1+α2*S2 = X2 S2方向沿x3軸
X2+α3*S3 = X3 S3為上一輪中的S4方向
第三輪
....
第一輪方向：x1軸 x2軸 x3軸 S4
第二輪方向： S1 S2 S3 S4
第三輪方向： S1 S2 S3 S4
降維搜尋：
比如第一輪中，由于α1比較小
導緻 S4 與 α2*S2 + α3*S3 同方向，稱之為降維搜尋
Powell法：修正的共轭方向法
在每輪中淘汰哪個方向需要判斷，不一定每次都淘汰第一個方向
是否選用新計算出來的方向需要進行判斷
梯度法
梯度下降法
共轭梯度法
梯度法+共轭方向法
牛頓法
一維
多元
Xk+1 = Xk + αk*Sk，Sk=∇f/H，αk=1
牛頓法在第k此疊代時，在Xk的局部構造一個二次函數等效目标函數，在二次函數中求出Xk+1
不足：
步長為1，效率低，甚至造成函數值不降反升
阻尼牛頓法：
方向：牛頓方向
在牛頓方向進行搜尋，尋找到使目标函數取極小值的Xk+1
變尺度法
DFP法，三個人名的首字母，P：powell
得出Ak應該是一個實對稱正定矩陣
BFGS法
總結 優化設計（二）
限制優化方法
複合形法
無限制優化問題的單純形法的推廣
隻需計算目标函數值
懲罰函數法
内罰函數法/内點法：疊代點在可行域之内
外罰函數法/外點法：疊代點在可行域之外