本筆記不關(guān)注證明過程

P2 無約束優(yōu)化的基礎(chǔ)

從初始點一步一步到最優(yōu)點：

終止條件：

全局收斂：起始點x0任意，收斂到x*

局部收斂：x0∈N(x*) ，收斂到x*。（x0在解的附近）

線搜索方法：x0=xk，方向pk，步長αk，xk+1=xk+αkpk

選方向：

• 最速下降法：pk=-▽f(xk)
• 牛頓方向：pk=-▽^2 f(xk)^(-1)▽f(xk)

• 擬牛頓方向：pk=-Bk·▽f(xk)
• 共軛梯度法：

信賴域方法

在xk附近構(gòu)造二次函數(shù)

P3 線搜索方法

φ(α) :=f(xk+αkpk)

方法：xk+1=xk+αkpk

最速下降：pk=-▽f(xk)

步長：αk=argmin φ(α) = argmin f(xk+αkpk)

wolfe條件是一種選取合適步長α的準(zhǔn)則

保證下降得比較快

下圖第二個不等式：忽略分母||pk||，左側(cè)為曲線上任意一點與最左側(cè)點連線的斜率，右側(cè)為選定斜率，兩斜率要滿足不等式關(guān)系。

第一個不等式由第二個推導(dǎo)而來（個人猜測）。

下面右圖中加粗的段就是滿足wolfe條件的區(qū)域，

保證步長α不會太小，取值在藍(lán)色區(qū)域

下圖第一個式子表明曲線上任意點的斜率應(yīng)大于某值，這就讓α的取值在平移后的藍(lán)色直線的右側(cè)，保證了α不會太小。

第二個式子左側(cè)應(yīng)右乘pk（應(yīng)該是筆誤了）

滿足wolfe條件的α是存在的

此函數(shù)為關(guān)于α的函數(shù)φ。

P4 線搜索方法的收斂性和收斂速度

紫色區(qū)域比初始值小，其值f(x)稱為下水平集

定理中的Σ<∞，也就是其中的每一項趨向于0

(L>0)

下圖中λ為特征值，Κ為條件數(shù)

P5 算法收斂性

Zoutendijk定理加上以下條件，則擬牛頓法收斂。

下圖第一行等式右側(cè)第一項右上角缺-1

因為當(dāng)xk離x*比較遠(yuǎn)時：

1. 二階梯度有可能不正定，方向也就不一定是下降方向
2. αk不一定能滿足wolfe條件

所以要對牛頓法進行修正

當(dāng)上圖中λi全為正，二階梯度正定。

一般情況下不全為正，所以需要用其他矩陣來將λi變?yōu)檎蛘?

方法1，正數(shù)對應(yīng)的位置為0，其他位置按λi'=ε-λi得出，但其中的矩陣不是對角陣。

方法2，把所有位置加上同一個λ，需要試探。

P6 正定矩陣的cholesky因子分解

信賴域方法在當(dāng)前的迭代定義一個區(qū)域，在此區(qū)域內(nèi)能夠相信(trust)模型可以充分代表目標(biāo)函數(shù)。然后選擇步(step)作為當(dāng)前區(qū)域的近似極小值點。

如下圖所示，盡管用到了最優(yōu)步長，（基于模型）由線搜索方法找到的極小值點只會使f減小很小的一部分；而由信賴域方法找到的步則可以造成f的大大減少。（越靠近中心越小）

算法4.1

下圖中的mk是f在xk的二階泰勒展開，通過最小化mk求得p，用相應(yīng)的p作為步迭代f。

ρ的分母一定是非負(fù)的。

根據(jù)ρ來選擇信賴域范圍Δk和xk

P7 基于Cauchy點的方法

1. ||p(τ)||是τ的上升函數(shù)
2. m(p(τ))是τ的下降函數(shù)

引理4.3

P8 定理4.5

P9 定理4.6

定理4.6

去優(yōu)酷學(xué)習(xí)本講。

P10 非線性共軛梯度法1

共軛梯度法最早是用于解由正定矩陣作為系數(shù)的線性方程組。

可作為高斯消除法的替代，而且能解大型（線性、非線性）方程組問題。

1、問題

問題①：解一個線性方程組問題。

問題②：二次規(guī)劃問題

在求解問題②時，我們要找到x*，求f(x)的梯度可以得到問題①中的線性方程組，（不那么嚴(yán)謹(jǐn)?shù)闹v），零梯度為0可得x*。

上面的兩個問題是等價的，這種等價可以讓我們把共軛梯度法解釋為：解線性系統(tǒng)的算法，或最小化凸二次方程的技巧。

2、共軛方向

（一對正交向量是關(guān)于單位向量的共軛向量）

{pk}是共軛方向組，其中的元素兩兩共軛。

下圖中倒數(shù)第二行，因為正定矩陣的轉(zhuǎn)置是其本身，所以等式成立。

性質(zhì)

αk=argmin f(xk+αkpk)

xk=x0+α0p0+......+αk-1pk-1

xk=argmin f(x0+u)

算法

xk、pk =>αk=argmin f(xk+αkpk) =>xk+1=xk+αkpk

幾何解釋

在X空間中沿著pi變化，在Y空間中沿著某一軸變化

對于Φ(x)=Ax-b，當(dāng)A是對角陣時，Φ的contour是一個長短軸與坐標(biāo)系平行的橢圓，這樣就可以沿著坐標(biāo)軸方向?qū)ふ襪inimizer

3、共軛梯度法

性質(zhì)ii說明構(gòu)造的向量是共軛向量

以上方法可以用來①得到大型線性方程組的近似解②二次函數(shù)優(yōu)化問題的漸進解

P11 非線性共軛梯度法2

引理5.6保證pk+1是下降方向

強wolfe條件的個人理解：k+1的斜率要更大

P12 擬牛頓法

下面兩種方法分別推導(dǎo)出通過梯度的差，x的差算Hk+1、Bk+1，用H、B算pk+1

①DFP方法

SR1:Symmetric Rank 1

①矩陣的跡

trace(A)△=Σaii，定義為主對角線元素之和

性質(zhì)：trace(A+B)=trace(A)+trace(B)

trace(uuT)=trace(uTu)=||u||^2

trace(AB)=trace(BA)

trace(aA)=atrace(A)

trace(A)=Σλi(A) 矩陣特征根之和等于跡

②方陣的行列式

定義 det(A)=Σa1i1·a2i2·......·anin

性質(zhì) det(aA)=a^n det(A)

det(AB)=det(A)·det(B)

det(A)=Πλi(A) 特征根之跡等于行列式

det(I+xyT)=1+yTx

(A+B)^(-1) = B-1(A-1 + B-1)A-1

定義 A^(-1) 《==》det(A) /= 0

det(A-1)=1/det(A)

矩陣逆引理

④Ψ(A)=trace(A)-ln det(A)

P13 BFGS方法

①曲率條件：

引理：如果pk是下降方向，且αk滿足wolfe條件，則曲率條件成立。

引理（BFGS方法）：如Bk正定，則Bk+1正定。

定理：

條件：nabla f(x)滿足lipschitz連續(xù)，且

則：lim inf||fk|| = 0

P15 計算導(dǎo)數(shù)

P16 無需導(dǎo)數(shù)的優(yōu)化方法（DFO）

坐標(biāo)下降法：遍歷n個坐標(biāo)方向e1,e2,......en，輪流在每個方向進行線搜索以獲得新迭代。

在第一次迭代中，固定除x1以外的其他x，找到能使目標(biāo)函數(shù)最小（至少減少）的點；下一次迭代，固定除x2以外的其他x，進行搜索。

上圖為包含兩個變量的二次函數(shù)利用坐標(biāo)搜索方法進行優(yōu)化。

在傳統(tǒng)的共軛梯度法中要通過導(dǎo)數(shù)來獲得共軛向量。

為了不用導(dǎo)數(shù)，用{e1,e2,...en}構(gòu)造一個線性子空間，f在S1，S2中的最優(yōu)解x1*,x2*組成的向量x1*-x2*與{e1,e2,...,en}共軛（線性子空間性質(zhì)）。f在S1中求最優(yōu)解x1的問題可以變?yōu)樵赟中求最優(yōu)解{c1,c2,...,cn}的問題，而此問題可化為對單個c求解的問題（上圖最后一行）。

又稱單純形法。

n維空間中的n+1個點可以構(gòu)成一個單純形，如下圖右側(cè)所示。

P17 最小二乘方問題

用下圖第一行的式子來衡量模型和系統(tǒng)的觀測之間的差異。

下圖中的rj(x)是一個對從x1到xn的偏導(dǎo)組成的向量。

P18 非線性方程組

H(x(s)),λ(s))=0

求H全微分：

P19 約束優(yōu)化理論

積極約束集：在不等式約束中，當(dāng)x給定后，ci(x)可以分為兩種，其中ci(x)=0的部分包含于積極約束集。

約束問題的lagrange函數(shù)

用拉格朗日乘數(shù)法解決只有等式約束的問題。分別對每個x求偏導(dǎo)。

用KKT條件求包含等式和不等式約束的問題。

對偶理論表明我們可以從原有的優(yōu)化問題中，利用其函數(shù)與數(shù)據(jù)，構(gòu)造一個alternative問題。

本小結(jié)的結(jié)論都是在下面的情況下得出的：

即無等式約束，目標(biāo)函數(shù)和-ci(x)都是凸函數(shù)。

下圖中不等式約束前的λ>0。

對偶函數(shù)：max θD(λ)

s.t. λi大于等于0,i∈I

P20 基本的必要條件

x是解的必要條件

如果積極約束都是線性函數(shù)的話，也就是A(x)內(nèi)都是線性函數(shù)

P21 點與凸集的分割定理

λ∈R^p

K是閉凸集

定理（強對偶成立條件）

min f(x)

s.t. ci(x)≥0, i∈I

且f(x), -ci(x)都是凸函數(shù)，kkt條件成立

則強對偶性成立

P22 SQP方法和內(nèi)點方法

序列二次規(guī)劃sequence quadratic programming