NO IMAGE

//2014年4月20日

//2014年6月20日入“未完成”

//2014年6月21日

參考資料:

http://blog.csdn.net/luoleicn/article/details/6527049

http://blog.csdn.net/dgglx/article/details/6522042

http://www.codelast.com/?p=2780

http://blog.sciencenet.cn/blog-588243-573819.html

http://blog.csdn.net/itplus/article/details/21897443

一.最優化方法的分類(剛開始往往搞不清)

數值非線性全域性最優化引言
約束非線性最優化的數值演算法大致可以分為 基於梯度的方法 和 直接搜尋方法. 基於梯度的方法使用一階導數 (梯度) 或二階導數(黑塞(Hessians)矩陣). 例如,序列二次規劃方法(SQP)、增廣拉格朗日方法和(非線性)內點法. 直接搜尋方法不使用導數資訊. 例如,Nelder-Mead、遺傳演算法和差分進化,以及模擬退火. 直接搜尋方法往往收斂速度較慢,但可以對函式和約束條件中噪聲存在的限制更為寬鬆.
通常情況下,演算法只建立問題的區域性模型. 此外,許多這種演算法總是尋求目標函式,或者由目標函式和約束條件合成的一個優值函式的某種減小,來確保迭代過程的收斂. 如果收斂的話,這種演算法只找到區域性最優解,因此被稱為 區域性最優化演算法. 在 Mathematica 裡,區域性最優化問題可以用FindMinimum 求解.
然而,全域性優化演算法 通常通過既允許減小也允許增大目標函式/優值函式來試圖求全域性最優解. 通常這種演算法的計算代價更高. 全域性最優化問題可以用 Minimize 精確求解或者用 NMinimize 數值化地求解.

凸目標函式是全域性最優的。不然:

牛頓法及其衍生都是區域性最優。

神經網路也是區域性最優。

內點法,外點法也是區域性最優。

模擬退火等是用在無約束規劃上的

2.matlab的fmincon函式

有四種方法:內點法,SQP,積極集,可信域。

3.收斂性及收斂速度

最速下降法的收斂性:對一般的目標函式是整體收斂的(所謂整體收斂,是指不會非要在某些點附近的範圍內,才會有好的收斂性)。

最速下降法的收斂速度:至少是線性收斂的。上面的最速下降法只用到了梯度資訊,即目標函式的一階導數資訊,而牛頓法則用到了二階導數資訊。

牛頓法的收斂性:對一般問題都不是整體收斂的(只有當初始點充分接近極小點時,才有很好的收斂性)。

牛頓法的收斂速度:二階收斂。因此,它比最速下降法要快。

4.最優化歷史(年代越晚越先進)

非線性規劃的一個重要理論是1951年Kuhn-Tucker最優條件(簡稱KT條件)的建立.此後的50年代主要是對梯度法和牛頓法的研究.以Davidon(1959), Fletcher和Powell(1963)提出的DFP方法為起點,
60年代是研究擬牛頓方法活躍時期, 同時對共軛梯度法也有較好的研究. 在1970年由Broyden,Fletcher,Goldfarb 和Shanno從不同的角度共同提出的BFGS方法是目前為止最有效的擬牛頓方法. 由於Broyden, Dennis 和More的工作使得擬牛頓方法的理論變得很完善. 70年代是非線性規劃飛速發展時期, 約束變尺度(SQP)方法(Han和Powell為代表)和Lagrange乘子法(代表人物是Powell 和Hestenes)是這一時期主要研究成果.計算機的飛速發展使非線性規劃的研究如虎添翼.80年代開始研究信賴域法、稀疏擬牛頓法、大規模問題的方法和平行計算,
90年代研究解非線性規劃問題的內點法和有限儲存法. 可以毫不誇張的說, 這半個世紀是最優化發展的黃金時期