算是讀書筆記，記錄一下。沒有證明，隻有定理。
一、最優化數學基礎
1正定矩陣
1 正定矩陣定義
對應着半正定矩陣，負定矩陣，半負定矩陣和不定矩陣，這裡隻以正定矩陣為例。
則A為正定矩陣。
定義是一種常用的，用來判定某個對稱矩陣是否是正定矩陣的方法。
2 正定矩陣的判定方法
（1）根據定義判斷
（2）根據矩陣的順序主子式判斷
（3）根據矩陣的特征值判斷
3 擴充知識點
（1）判定正定矩陣的第一種方法，定義。需要計算行向量乘矩陣乘列向量，了解矩陣的乘法，理清次元和最終傳回的結果的次元。
（2）計算順序主子式，就是計算不同階數的行列式值。了解行列式的有關概念和性質；高階行列式展開計算的方法，某一行或者某一列的元素乘以對應的代數餘子式之和。
（3）矩陣的特征值。特征值的計算，根據定義，求解特征多項式的解。一個解就是一個特征值。根據特征值計算對應的特征向量，每個特征值都擁有基礎解系，一重特征值在求解特征多項式過程中對應的維數為一，基礎解系次元為一，三者一一對應。
（4）實對稱矩陣。常用的，特殊的，很重要的一個矩陣。擁有很多優良性質。不同的特征值對應的特征向量互相正交，同一個特征值對應的解系裡的特征向量不一定正交，可以通過施密特正交化轉換成正交的。實對稱矩陣A，存在正交矩陣Q，使得Q-1AQ=QTAQ為對角型矩陣，對角線上的元素即為特征值。Q特征值對應的特征向量正交化，歸一化後，合并在一起的矩陣。
2 函數的凹凸性
1 區分凹函數和凸函數。求最小值是凸，最大值是凹。以凸函數為例。
2 凸函數的判定
（1）性質來判定
自變量線性組合對應的函數值小于等于自變量函數值對應的線性組合。
（2）一階充要條件
（3）二階充要條件
需要判定海瑟矩陣是否為半正定，用到第一部分的判定方法。
3 極值的性質
極值有極大值和極小值，此處以極小值為例
1 極值點的一階必要條件
極值點處的梯度為0，必要條件，反過來不成立。
2 極值點的二階必要條件
極值點處的梯度（各向偏導）為0，海瑟矩陣半正定。
是必要條件，反過來不成立。
反過來不成立的例子：
3 極值點的二階充分條件
用來判定是否為極值點
先求出駐點，然後判斷駐點處的海瑟矩陣是否為正定。
當駐點出的海瑟矩陣半正定時，通過放松後的條件判斷。
放松後的二階充分條件：局部區域内半正定（局部凸函數）
舉例：
4 極值的二階充要條件
凸函數的駐點為全局極值點
總結：
二、無限制優化
此處以求極小值為例，極大值情況相同。某些情況（現實中大多數情況）
1 一階導數（梯度下降法）
如果梯度存在，梯度方向是函數值上升最快的方向，反方向是下降最快的方向，使用梯度反方向作疊代的方向，并使用一維搜尋求解步長，進行疊代。
2 二階導數（牛頓法）
1 牛頓法
最簡單的牛頓法，利用極值的一階必要條件（駐點，梯度，各向導數為0），将函數表達式在Xn出泰勒展開到二階，求出Xn+1的疊代公式。
如果原函數為正定二次函數，則通過牛頓法，在牛頓方向，以步長為一，疊代一次便可到達極小值點。
缺點一：牛頓方向可能不是下降的方向，步長選的不好，可能不會收斂。
缺點二：牛頓方向需要求海瑟矩陣的逆，占用記憶體，對于不可逆的情況，算法不能進行。
牛頓法缺點的例子：
第一個點，函數值慢慢減小；第二個點，函數值不變，展現缺點一；第三個點，海瑟矩陣奇異，不可求逆，展現缺點二。
2 阻尼牛頓法
針對缺點一，阻尼牛頓法在牛頓方向上，使用一維搜尋，尋找一個使函數值下降最快的步長。
3 拟牛頓法
針對缺點二，構造一個正定矩陣（正定矩陣可以求逆，并保持較快的下降速度），代替海瑟矩陣，再求出拟牛頓方向，進行疊代。每次疊代中，使用目前點的資訊，疊代正定矩陣，計算拟牛頓方向，一維搜尋确定步長。
DFP拟牛頓算法，每次更新的是海瑟矩陣的逆，BFGS更新的是海瑟矩陣。
三、有限制優化
1 隻有等式限制
1 一階必要條件，拉格朗日定理
最優解處的函數的梯度可以由每個限制的梯度線性表示。拉格朗日函數對各個方向的偏導為0，加上原來的等式限制，可以寫出所有的等式，求解出X和λ。
2 二階充分條件，用來判斷是否為極值點
通過限制駐點的海瑟矩陣來判斷。
二階充分條件的放松條件：
在限制的梯度垂直面上正定即可。
例子：
2 隻有不等式限制
1 KKT必要條件
最優解在不等式表面時，最優解處的梯度可以由不等式的梯度線性表示，且在不等梯度的正方向上。
相對于等式，多了個系數u大于等于0和乘積等于0的式子，再加上越來不等式的限制，由以上所有的式子解出可能的限制駐點。
2 KKT充分條件，判斷是否為極值點
目标和限制都為凸函數，滿足KKT條件，則為全局最優解。
3 混合限制
1 KKT必要條件
局部最優解處的梯度可以由等式和不等式限制的梯度線性表示，且不等式為梯度的正方向，不等式和系數乘積為0。
2 KKT充要條件
3 拉格朗日對偶
如果滿足KKT充要條件（兩凸加上仿射函數，就是線性函數），則最優解處滿足KKT條件，且原問題和對偶問題符合強對偶性。