《最優化方法》複習提要
第一章最優化問題與數學預備知識
§1. 1 模型
無約束最優化問題 ．
約束最優化問題（）
即其中稱為目標函式，稱為決策變數，稱為可行域，
稱為約束條件．
§1. 2 多元函式的梯度、hesse矩陣及taylor公式
定義設．如果維向量，，有
．則稱在點處可微，並稱為在點處的微分．
如果在點處對於的各分量的偏導數
都存在，則稱在點處一階可導，並稱向量
為在點處一階導數或梯度．
定理1 設．如果在點處可微，則在點處梯度
存在，並且有．
定義設．是給定的維非零向量，．如果
存在，則稱此極限為在點沿方向的方向導數，記作．
定理2 設．如果在點處可微，則在點處沿任何非零方向的方向導數存在，且，其中．
定義設是上的連續函式，．是維非零向量．如果，使得，有（>）．則稱為在點處的下降（上公升）方向．
定理3 設，且在點處可微，如果非零向量，使得（>）0，則是在點處的下降（上公升）方向．
定義設．如果在點處對於自變數的各分量的二階偏導數都存在，則稱函式在點處二階可導，並稱矩陣
為在點處的二階導數矩陣或hesse矩陣．
定義設，記，如果
在點處對於自變數的各分量的偏導數
都存在，則稱向量函式在點處是一階可導的，並且稱矩陣
為在點處的一階導數矩陣或jacobi矩陣，簡記為．
例2 設，求在任意點處的梯度和hesse矩陣．
解設，則，
因，故得．
又因，則．
例3 設是對稱矩陣，，稱為二次函式，求在任意點處的梯度和hesse矩陣．
解設，則
，從而．
再對求偏導得到，於是
．例4 設，其中二階可導，，試求．
解由多元復合函式微分法知．
定理4 設，且在點的某鄰域內具有二階連續偏導數，則在點處有taylor展式
．證明設，則．按一元函式taylor公式在處展開，有
．從例4得知．
令，有．
根據定理1和定理4，我們有如下兩個公式，．
§1. 3 最優化的基本術語
定義設為目標函式，為可行域，．
（1） 若，都有，則稱為在上的全域性（或整體）極小點，或者說，是約束最優化問題的全域性（或整體）最優解，並稱為其最優值．
（2） 若，都有，則稱為在上的嚴格全域性（或整體）極小點．
（3） 若的鄰域使得，都有，則稱為在上的區域性極小點，或者說，是約束最優化問題的區域性最優解．
（4） 若的鄰域使得，都有，則稱為在上的嚴格區域性極小點．
第二章最優性條件
§2.1 無約束最優化問題的最優性條件
定理1 設在點處可微，若是問題的區域性極小點，則．
定義設在處可微，若，則稱為的平穩點．
定理2 設在點處具有二階連續偏導數，若是問題的區域性極小點，則，且半正定．
定理3 設在點處具有二階連續偏導數，若，且正定，則是問題的嚴格區域性極小點．
注：定理2不是充分條件，定理3不是必要條件．
例1 對於無約束最優化問題，其中，顯然
，令，得的平穩點，而且
．易見為半正定矩陣．
但是，在的任意鄰域，總可以取到，使，即不是區域性極小點．
例2 對於無約束最優化問題，其中，
易知，從而得平穩點，並且
．顯然不是正定矩陣．但是，在處取最小值，即為嚴格區域性極小點．
例3 求解下面無約束最優化問題，
其中，解因為
，所以令，有
解此方程組得到的平穩點．從而，
．由於和是不定的，因此和不是極值點．是負定的，故不是極值點，實際上它是極大點．是正定的，從而是嚴格區域性極小點．
定理4 設是凸函式，且在點處可微，若，則為的全域性極小點．
推論5 設是凸函式，且在點處可微．則為的全域性極小點的充分必要條件是．
例4 試證正定二次函式有唯一的嚴格全域性極小點，其中為階正定矩陣．
證明因為為正定矩陣，且，所以得的唯一平穩點．又由於是嚴格凸函式，因此由定理4知，是的嚴格全域性極小點．
§2.2 等式約束最優化問題的最優性條件
定理1 設在點處可微，在點處具有一階連續偏導數，向量組線性無關．若是問題
的區域性極小點，則，使得
．稱為lagrange函式，其中．
稱為lagrange乘子向量．
易見，這裡．
定理2 設和在點處具有二階連續偏導數，若，使得，並且，，只要，便有，則是問題
的嚴格區域性極小點．
例1 試用最優性條件求解
解 lagrange函式為，則，
從而得的平穩點和，對應有
和．由於．因此．
並且，有．
利用定理2，所得的兩個可行點和都是問題的嚴格區域性極小點．
§2.3 不等式約束最優化問題的最優性條件
定義設，若，使得，，
則稱為集合在點處的可行方向．
這裡．令 ，
．定理1 設是非空集合，在點處可微．若是問題的區域性極小點，則．
對於1）
其中．令，其中是上述問題（1）的可行點．
定理2 設是問題（1）的可行點，和在點處可微，在點處連續，如果是問題（1）的區域性極小點，則，
其中．定理3 設是問題（1）的可行點，和在點處可微，在點處連續，若是問題（1）的區域性極小點，則存在不全為0的非負數，使
． （稱為fritz john點）
如果在點處也可微，則存在不全為0的非負數，使
（稱為fritz john點）
例1 設試判斷是否為fritz john點．
解因為，且，
所以為使fritz john條件成立，只有才行．取即可，因此是fritz john點．
定理4 設是問題（1）的可行點，和在點處可微，在點處連續，並且線性無關．若是問題（1）的區域性極小點，則存在，使得
． （稱為k-t點）
如果在點處也可微，則存在，使得
（稱為k-t點）
例2 求最優化問題的k-t點．
解因為，所以k-t條件為
若，則，這與矛盾．故，從而；
若，則，這與矛盾．故，從而；
由於，且為問題的可行點，因此是k-t點．
定理5 設在問題（1）中，和是凸函式，是可行點，並且和在點處可微．若是問題（1）的k-t點，則是問題（1）的全域性極小點．
§2.4 一般約束最優化問題的最優性條件
考慮等式和不等式約束最優化問題
1）其中．
並把問題（1）的可行域記為．．
定理1 設為問題（1）的可行點，和在點處可微，在點處具有一階連續偏導數，在點處連續，並且向量組線性無關．若是問題（1）的區域性極小點，則，
這裡，，
．定理2 設為問題（1）的可行點，和在點處可微，在點處具有一階連續偏導數，在點處連續．若為問題（1）的區域性極小點，則存在不全為0的數和，且，使
． （稱為fritz john點）
若在點處也可微，則存在不全為0的數和，且，使
（稱為fritz john點）
例1 設試判斷是否為fritz john點．
解 ，且，且，
因此為使fritz john條件成立，只有才行．所以取，即知是fritz john點．
定理3 設為問題（1）的可行點，和在點處可微，在點處具有一階連續偏導數，在點處連續，且向量組線性無關．若是問題（1）的區域性極小點，則存在數和，使
． （稱為k-t點）
如果在點處也可微，則存在數和，使
（稱為k-t點）令，，
稱與為廣義lagrange乘子向量或k-t乘子向量．
令為廣義lagrange函式．稱為廣義lagrange函式．則k-t條件為
定理4 設在問題（1）中，和是凸函式，是線性函式，是可行點，並且和在點處可微．若是問題（1）的k-t點，則是問題（1）的全域性極小點．
例2 求解最優化問題
解廣義lagrange函式為
．因為，．
所以k-t條件及約束條件為
下面分兩種情況討論．
（1） 設，則有
由此可解得，但不是可行點，因而不是k-t點．
（2） 設，則有
由此可得，解得或。從而或．於是或（這與矛盾）．或．由此可知是問題的k-t點，但不是問題的k-t點．
易見，是上的凸函式，是上的凹函式，是線性函式，因此由定理4知，是問題的全域性最優解．
定理5 設為問題（1）的可行點，和在點處具有二階連續偏導數，並且存在乘子向量和使k-t條件成立，即
若對於任何滿足
的向量，都有，則是問題（1）的嚴格區域性極小點．
例3 求解最優化問題
其中常數．
解該問題的廣義lagrange函式為．因為
所以問題的k-t條件及約束條件為
由第1式、第3式知，從而由第二式解得．於是再由第1式知，且，
即得，從而，解得，
於是．所以是問題的k-t點．
又由於在點處關於的hesse矩陣是乙個階對角矩陣，其對角線上第個元素為
，因此是正定矩陣．根據定理5，為問題的嚴格區域性極小點．
第三章常用優化演算法介紹
§3.1 一維搜尋
給定，令．
定義如果求得步長，使得
3.1.1）
則稱這樣的一維搜尋為最優一維搜尋或精確一維搜尋．叫做最優步長．
定理1 對於問題，設是可微函式，是從出發沿方向作最優一維搜尋得到的，則有．
定義如果選取，使目標函式沿方向取得適當的可接受的下降量，即使得下降量是我們可接受的，則稱這樣的一維搜尋為可接受一維搜尋或非精確一維搜尋．
定義設，並且．如果對於有，那麼稱是問題的搜尋區間．
定義設，若存在，使得在上嚴格單調減少，在上嚴格單調增加，則稱是的單谷區間，是上的單谷函式或單峰函式．
定理2 設為的單谷區間，，且，那麼
（1）若，則是的單谷區間；
（2）若，則是的單谷區間．
演算法3-1（進退法）
step1 選取初始資料。給定初始點，初始步長，加倍係數（一般取），計算，置．
step2 試探．令，計算．
step3 比較目標函式值．若，轉step4，否則，轉step5．
step4 加步探索．令，轉step2．
step5 反向搜尋．若，轉換搜尋方向，，轉step2；否則，停止迭代．令．輸出搜尋區間．
§3.2 0.618法與fibonacci法
考慮．假定的乙個搜尋區間已確定，並設在上為單谷函式．
演算法3-2（0.618法）
step1 選取初始資料．確定初始搜尋區間和允許誤差．
step2 計算最初兩個試探點：，求出，並置．
step3 檢查？是，停止計算，輸出；否則，轉step4．
step4 比較函式值．若，轉step5；若，轉step6．
step5 向左搜尋．令．
並計算，轉step7．
step6 向右搜尋．令．
並計算，轉step7．
34 最優化方法課程大綱
一 課程概述 課程名稱 最優化方法 methods of optimization 課程編號 17371309 課程學分 2學分 課程總學時 32學時 課程性質 專業基礎課 專業課 二 課程內容簡介 最優化是從所有可能方案中選擇最合理的方案以達到最優目標的學科，是隨著計算機的普遍應用而發展起來的，它...
最優化方法複習題
第一章概述 包括凸規劃 一 判斷與填空題 1 23 設若，對於一切恒有，則稱為最優化問題的全域性最優解.4 設若，存在的某鄰域，使得對一切恒有，則稱為最優化問題的嚴格區域性最優解.5 給定乙個最優化問題，那麼它的最優值是乙個定值.6 非空集合為凸集當且僅當中任意兩點連線段上任一點屬於.7 非空集合為...
最優化方法複習題
第一章概述 包括凸規劃 一 判斷與填空題 1 23 設若，對於一切恒有，則稱為最優化問題的全域性最優解.4 設若，存在的某鄰域，使得對一切恒有，則稱為最優化問題的嚴格區域性最優解.5 給定乙個最優化問題，那麼它的最優值是乙個定值.6 非空集合為凸集當且僅當中任意兩點連線段上任一點屬於.7 非空集合為...