網(wǎng)站服務(wù)器租用價(jià)格表怎么從網(wǎng)上找國(guó)外客戶
最優(yōu)化：建模、算法與理論
目前在學(xué)習(xí) 最優(yōu)化：建模、算法與理論這本書(shū)，來(lái)此記錄一下，順便做一些筆記，在其中我也會(huì)加一些自己的理解，盡量寫(xiě)的不會(huì)那么的條條框框（當(dāng)然最基礎(chǔ)的還是要有）
第二章 基礎(chǔ)知識(shí)
2.1 范數(shù)
2.1.1 向量范數(shù)
定義2.1（范數(shù)）稱一個(gè)從向量空間Rn到實(shí)數(shù)域R的非負(fù)函數(shù)||·||為范數(shù)，如果他滿足：
（1）正定性：對(duì)于所有的 v ∈ R n v{\in}R^n v∈Rn，有 ∣ ∣ v ∣ ∣ > = 0 ||v|| >= 0 ∣∣v∣∣>=0,且 ∣ ∣ v ∣ ∣ = 0 ||v|| = 0 ∣∣v∣∣=0 當(dāng)且僅當(dāng) v = 0 v=0 v=0
（2）齊次性：對(duì)于所有的 v ∈ R n v{\in}R^n v∈Rn和 α ∈ R {\alpha}{\in}R α∈R，有 ∣ ∣ α v ∣ ∣ ||{\alpha}v|| ∣∣αv∣∣= ∣ α ∣ |{\alpha}| ∣α∣ ∣ ∣ v ∣ ∣ ||v|| ∣∣v∣∣
（3）三角不等式：對(duì)于所有的 v , w ∈ R n v,w{\in}R^n v,w∈Rn,有 ∣ ∣ v + w ∣ ∣ < = ∣ ∣ v ∣ ∣ + ∣ ∣ w ∣ ∣ ||v+w|| <= ||v|| + ||w|| ∣∣v+w∣∣<=∣∣v∣∣+∣∣w∣∣
最常用的向量范數(shù)為lp范數(shù)（p >= 1）
∣ ∣ v ∣ ∣ p = ( ∣ v 1 ∣ p + ∣ v 2 ∣ p + … + ∣ v n ∣ p ) 1 / p ||v||_{p} = (|v_{1}|^p + |v_{2}|^p + \ldots + |v_{n}|^p)^{1/p} ∣∣v∣∣p?=(∣v1?∣p+∣v2?∣p+…+∣vn?∣p)1/p
顯而易見(jiàn)，高數(shù)應(yīng)該都學(xué)過(guò)，如果 p = ∞ p={\infty} p=∞，那么 l ∞ l_\infty l∞?范數(shù)定義為 ∣ ∣ v ∣ ∣ ∞ = m a x ∣ v i ∣ ||v||_\infty = max|v_i| ∣∣v∣∣∞?=max∣vi?∣
記住 p = 1 , 2 , ∞ p = 1,2,{\infty} p=1,2,∞的時(shí)候最重要，有時(shí)候我們會(huì)忽略 l 2 l_2 l2?范數(shù)的角標(biāo)
也會(huì)遇到由正定矩陣 A A A誘導(dǎo)的范數(shù)，即 ∣ ∣ x ∣ ∣ A = x T A x ||x||_A = \sqrt{x^TAx} ∣∣x∣∣A?=xTAx?
對(duì)于 l 2 l_2 l2?范數(shù)，有常用的柯西不等式，設(shè) a , b ∈ R n a,b{\in}R^n a,b∈Rn，則
∣ a T b ∣ < = ∣ ∣ a ∣ ∣ 2 ∣ ∣ b ∣ ∣ 2 |a^Tb|<=||a||_2||b||_2 ∣aTb∣<=∣∣a∣∣2?∣∣b∣∣2?
等號(hào)成立當(dāng)且僅當(dāng)a與b線性相關(guān)
2.1.2 矩陣范數(shù)
矩陣范數(shù)首先也一樣要滿足那三個(gè)特性啦，就是要滿足正定性，齊次性，三角不等式，常用的就是 l 1 , l 2 l_1,l_2 l1?,l2?范數(shù)，當(dāng) p = 1 p = 1 p=1時(shí)，矩陣 A ∈ R m ? n A{\in}R^{m*n} A∈Rm?n的范數(shù)定義
∣ ∣ A ∣ ∣ 1 = ∑ i = 1 m ∑ j = 1 n ∣ a i j ∣ ||A||_1={\sum_{i=1}^m}{\sum_{j=1}^n}|a_{ij}| ∣∣A∣∣1?=i=1∑m?j=1∑n?∣aij?∣
當(dāng) p = 2 p=2 p=2時(shí)，也叫矩陣的Frobenius范數(shù)（F范數(shù)），記為 ∣ ∣ A ∣ ∣ F ||A||_F ∣∣A∣∣F?，其實(shí)就是所有元素的平方和然后開(kāi)根號(hào)，具體定義如下
∣ ∣ A ∣ ∣ F = T r ( A A T ) = ∑ i , j a i j 2 ||A||_F=\sqrt{Tr(AA^T)}=\sqrt{\sum_{i,j}a_{ij}^2} ∣∣A∣∣F?=Tr(AAT)?=i,j∑?aij2??
這里的 T r Tr Tr表示方陣X的跡（這個(gè)大家應(yīng)該都知道吧，我把百度的解釋搬過(guò)來(lái)—在線性代數(shù)中，一個(gè)n×n矩陣A的主對(duì)角線（從左上方至右下方的對(duì)角線）上各個(gè)元素的總和被稱為矩陣A的跡（或跡數(shù)），一般記作tr(A)），矩陣的F范數(shù)具有正交不變性。
正交不變性呢就是說(shuō)對(duì)于正交矩陣 U ∈ R m ? n , V ∈ R m ? n U{\in}R^{m*n},V{\in}R^{m*n} U∈Rm?n,V∈Rm?n，我們有
∣ ∣ U A F ∣ ∣ F 2 = ∣ ∣ A ∣ ∣ F 2 ||UAF||_F^2=||A||_F^2 ∣∣UAF∣∣F2?=∣∣A∣∣F2?
具體的推導(dǎo)我這里就不寫(xiě)了哈，打公式太麻煩了哈哈，感興趣的可以看這本書(shū)的第24頁(yè)或者來(lái)找我^^
矩陣范數(shù)也可以由向量范數(shù)給誘導(dǎo)出來(lái)，一般稱這種算數(shù)為誘導(dǎo)范數(shù)，感覺(jué)用的不是很多，這里先不擴(kuò)展開(kāi)了
除了上訴的1范數(shù)，2范數(shù)，另一個(gè)常用的矩陣范數(shù)是核范數(shù)，給定矩陣 A ∈ R m ? n A{\in}R^{m*n} A∈Rm?n，核范數(shù)定義為
∣ ∣ A ∣ ∣ ? = ∑ i = 1 r σ i ||A||_*=\sum_{i=1}^r{\sigma}_i ∣∣A∣∣??=i=1∑r?σi?
其中 σ i , i = 1 , 2 , . . . , r {\sigma}_i,i=1,2,...,r σi?,i=1,2,...,r為 A A A的所有非0奇異值, r = r a n k ( A ) r=rank(A) r=rank(A)，類似于向量的 l 1 l_1 l1?范數(shù)可以保稀疏性，我們也通常通過(guò)限制矩陣的核范數(shù)來(lái)保證矩陣的低秩性。
2.1.3 矩陣內(nèi)積
內(nèi)積一般用來(lái)表征兩個(gè)矩陣之間的夾角，一個(gè)常用的內(nèi)積—Frobenius內(nèi)積， m ? n m*n m?n的矩陣 A A A和 B B B的Frobenius內(nèi)積定義為
< A , B > = T r ( A B T ) = ∑ i = 1 m ∑ j = 1 n a i j b i j <A,B>=Tr(AB^T)=\sum_{i=1}^m\sum_{j=1}^na_{ij}b_{ij} <A,B>=Tr(ABT)=i=1∑m?j=1∑n?aij?bij?
其實(shí)就是兩個(gè)矩陣一一對(duì)應(yīng)元素相乘
同樣的，我們也有矩陣范數(shù)對(duì)應(yīng)的柯西不等式，設(shè) A , B ∈ R m ? n A,B{\in}R^{m*n} A,B∈Rm?n，則
∣ < A , B > ∣ < = ∣ ∣ A ∣ ∣ F ∣ ∣ B ∣ ∣ F |<A,B>|<=||A||_F||B||_F ∣<A,B>∣<=∣∣A∣∣F?∣∣B∣∣F?
等號(hào)成立當(dāng)且僅當(dāng)A和B線性相關(guān)
2.2 導(dǎo)數(shù)
2.2.1 梯度與海瑟矩陣
梯度的定義（這玩意應(yīng)該是我之前好像都沒(méi)見(jiàn)到過(guò)的）：給定函數(shù) f : R n → R f:R^n{\rightarrow}R f:Rn→R，且 f f f在點(diǎn) x x x的一個(gè)鄰域內(nèi)有意義，若存在向量 g ∈ R n g{\in}R^n g∈Rn滿足
lim ? p → 0 f ( x + p ) ? f ( x ) ? g T p ∣ ∣ p ∣ ∣ = 0 \lim_{p{\rightarrow}0}\frac{f(x+p)-f(x)-g^Tp}{||p||}=0 p→0lim?∣∣p∣∣f(x+p)?f(x)?gTp?=0
就稱 f f f在點(diǎn) x x x處可微，此時(shí) g g g稱為 f f f在點(diǎn) x x x處的梯度，記作 ? f ( x ) {\nabla}f(x) ?f(x)，如果對(duì)區(qū)域D上的每一個(gè)點(diǎn) x x x都有 ? f ( x ) {\nabla}f(x) ?f(x)存在，則稱 f f f在D上可微
然后呢，這其中經(jīng)過(guò)一系列的推導(dǎo)，就可以得到我們耳熟能詳?shù)奶荻裙?br /> ? f ( x ) = [ ? f ( x ) ? x 1 ， ? f ( x ) ? x 2 ， . . . , ? f ( x ) ? x m ] T {\nabla}f(x)=\left[ \begin{matrix} {\frac{{\partial}f(x)}{{\partial}x_1}} ，{\frac{{\partial}f(x)}{{\partial}x_2}} ，...,{\frac{{\partial}f(x)}{{\partial}x_m}} \end{matrix} \right]^T ?f(x)=[?x1??f(x)?，?x2??f(x)?，...,?xm??f(x)??]T
對(duì)于多元函數(shù)，我們可以定義其海瑟矩陣：如果函數(shù) f ( x ) : R n → R f(x):R^n{\rightarrow}R f(x):Rn→R在點(diǎn) x x x處的二階偏導(dǎo)數(shù) ? 2 f ( x ) ? x i ? x j i , j = 1 , 2 , . . . , n \frac{{\partial}^2f(x)}{{\partial}x_i{\partial}x_j}i,j=1,2,...,n ?xi??xj??2f(x)?i,j=1,2,...,n都存在，則
? 2 f ( x ) = [ ? 2 f ( x ) ? x 1 2 ? 2 f ( x ) ? x 1 ? x 2 ? ? 2 f ( x ) ? x 1 ? x n ? 2 f ( x ) ? x 2 ? x 1 ? 2 f ( x ) ? x 2 2 ? ? 2 f ( x ) ? x 2 ? x n ? ? ? ? 2 f ( x ) ? x n ? x 1 ? 2 f ( x ) ? x n ? x 2 ? ? 2 f ( x ) ? x n 2 ] {\nabla}^2f(x)=\left[ \begin{matrix} \frac{{\partial}^2f(x)}{{\partial}x_1^2} & \frac{{\partial}^2f(x)}{{\partial}x_1{\partial}x_2} & \cdots& \frac{{\partial}^2f(x)}{{\partial}x_1{\partial}x_n}\\ \frac{{\partial}^2f(x)}{{\partial}x_2{\partial}x_1} &\frac{{\partial}^2f(x)}{{\partial}x_2^2} & \cdots & \frac{{\partial}^2f(x)}{{\partial}x_2{\partial}x_n} \\ \vdots & \vdots & &\vdots\\ \frac{{\partial}^2f(x)}{{\partial}x_n{\partial}x_1} &\frac{{\partial}^2f(x)}{{\partial}x_n{\partial}x_2} & \cdots &\frac{{\partial}^2f(x)}{{\partial}x_n^2} \end{matrix} \right] ?2f(x)= ??x12??2f(x)??x2??x1??2f(x)???xn??x1??2f(x)???x1??x2??2f(x)??x22??2f(x)???xn??x2??2f(x)???????x1??xn??2f(x)??x2??xn??2f(x)???xn2??2f(x)?? ?
成為 f f f在點(diǎn) x x x處的海瑟矩陣
當(dāng) ? 2 f ( x ) {\nabla}^2f(x) ?2f(x)在區(qū)域D上每個(gè)點(diǎn) x x x都存在，就稱 f f f在D上二階可微，若他在D上還連續(xù)，可以證明此時(shí)的海瑟矩陣是一個(gè)對(duì)稱矩陣
當(dāng) f : R n → R m f:R^n{\rightarrow}R^m f:Rn→Rm是向量值函數(shù)時(shí)，我們可以定義他的雅可比矩陣 J ( x ) ∈ R m ? n J(x){\in}R^{m*n} J(x)∈Rm?n，他的第i行分量 f i ( x ) f_i(x) fi?(x)梯度的轉(zhuǎn)置，即
J ( x ) = [ ? f 1 ( x ) ? x 1 ? f 1 ( x ) ? x 2 ? ? f 1 ( x ) ? x n ? f 2 ( x ) ? x 1 ? f 2 ( x ) ? x 2 ? ? f 2 ( x ) ? x n ? ? ? ? f m ( x ) ? x 1 ? f m ( x ) ? x 2 ? ? f m ( x ) ? x n ] J(x)=\left[ \begin{matrix} \frac{{\partial}f_1(x)}{{\partial}x_1} & \frac{{\partial}f_1(x)}{{\partial}x_2} & \cdots& \frac{{\partial}f_1(x)}{{\partial}x_n}\\ \frac{{\partial}f_2(x)}{{\partial}x_1} & \frac{{\partial}f_2(x)}{{\partial}x_2} & \cdots& \frac{{\partial}f_2(x)}{{\partial}x_n}\\ \vdots & \vdots & &\vdots\\ \frac{{\partial}f_m(x)}{{\partial}x_1} & \frac{{\partial}f_m(x)}{{\partial}x_2} & \cdots& \frac{{\partial}f_m(x)}{{\partial}x_n} \end{matrix} \right] J(x)= ??x1??f1?(x)??x1??f2?(x)???x1??fm?(x)???x2??f1?(x)??x2??f2?(x)???x2??fm?(x)???????xn??f1?(x)??xn??f2?(x)???xn??fm?(x)?? ?
容易看出，梯度 ? f ( x ) {\nabla}f(x) ?f(x)的雅可比矩陣就是f(x)的海瑟矩陣
類似于一元函數(shù)的泰勒展開(kāi)，對(duì)于多元函數(shù)，這里也不加證明的給出泰勒展開(kāi)
設(shè) f : R n → R f:R^n{\rightarrow}R f:Rn→R是連續(xù)可微的， p ∈ R n p{\in}R^n p∈Rn，那么
f ( x + p ) = f ( x ) + ? ( x + t p ) T p f(x+p)=f(x)+{\nabla}(x+tp)^Tp f(x+p)=f(x)+?(x+tp)Tp
其中 0 < t < 1 0<t<1 0<t<1，進(jìn)一步，如果說(shuō) f f f是二階連續(xù)可微的
f ( x + p ) = f ( x ) + ? f ( x ) T p + 1 2 p T ? 2 f ( x + t p ) p f(x+p)=f(x)+{\nabla}f(x)^Tp+\frac{1}{2}p^T{\nabla}^2f(x+tp)p f(x+p)=f(x)+?f(x)Tp+21?pT?2f(x+tp)p
其中 0 < t < 1 0<t<1 0<t<1
最后呢這一章還介紹了一類特殊的可微函數(shù)-----梯度利普希茨連續(xù)的函數(shù)，這類函數(shù)在很多優(yōu)化算法收斂性證明中起著關(guān)鍵作用
梯度利普希茨連續(xù)定義：給定可微函數(shù) f f f，若存在 L > 0 L>0 L>0,對(duì)任意 x , y ∈ d o m f x,y{\in}domf x,y∈domf有（ d o m f domf domf就是 f f f的定義域）
∣ ∣ ? f ( x ) ? ? f ( y ) ∣ ∣ ≤ L ∣ ∣ x ? y ∣ ∣ ||{\nabla}f(x)-{\nabla}f(y)||{\le}L||x-y|| ∣∣?f(x)??f(y)∣∣≤L∣∣x?y∣∣
則稱 f f f是梯度利普希茨連續(xù)的，相應(yīng)利普希茨常數(shù)為 L L L，有時(shí)候也會(huì)稱為 L L L-光滑，或者梯度 L L L-利普希茨連續(xù)
梯度利普希茨連續(xù)表明， ? f ( x ) {\nabla}f(x) ?f(x)的變化可以被自變量 x x x的變化所控制，滿足該性質(zhì)的函數(shù)有很多很好的性質(zhì)， 一個(gè)重要的性質(zhì)就是具有二次上界
具體證明我這里我就不再過(guò)多闡述了，有二次上界就是說(shuō) f ( x ) f(x) f(x)可以被一個(gè)二次函數(shù)上界所控制，即要求說(shuō) f ( x ) f(x) f(x)的增長(zhǎng)速度不超過(guò)二次
還有一個(gè)推論就是說(shuō)，如果 f f f是梯度利普希茨連續(xù)的，且有一個(gè)全局最小點(diǎn) x ? x^* x?，我們可以利用二次上界來(lái)估計(jì) f ( x ) ? f ( x ? ) f(x)-f(x^*) f(x)?f(x?)的大小，其中 x x x可以是定義域中任意一點(diǎn)
1 2 L ∣ ∣ ? f ( x ) ∣ ∣ 2 ≤ f ( x ) ? f ( x ? ) \frac{1}{2L}||{\nabla}f(x)||^2{\le}f(x)-f(x^*) 2L1?∣∣?f(x)∣∣2≤f(x)?f(x?)
具體的證明我這里就不寫(xiě)了哈，想知道的可以百度或者我們討論一下
2.2.2 矩陣變量函數(shù)的導(dǎo)數(shù)
多元函數(shù)梯度的定義也可以推廣到變量是矩陣的情況，以 m ? n m*n m?n矩陣 X X X為自變量的函數(shù) f ( X ) f(X) f(X)，若存在矩陣 G ∈ R m ? n G{\in}R^{m*n} G∈Rm?n滿足
lim ? V → 0 f ( X + V ) ? f ( X ) ? < G , V > ∣ ∣ V ∣ ∣ = 0 \lim_{V{\rightarrow}0}\frac{f(X+V)-f(X)-<G,V>}{||V||}=0 V→0lim?∣∣V∣∣f(X+V)?f(X)?<G,V>?=0
其中 ∣ ∣ ? ∣ ∣ ||·|| ∣∣?∣∣是任意矩陣范數(shù)，就稱矩陣向量函數(shù) f f f在 X X X處 F r a ˊ c h e t Fr\acute{a}chet Fraˊchet可微，就稱G為 f f f在 F r a ˊ c h e t Fr\acute{a}chet Fraˊchet可微意義下的梯度，其實(shí)矩陣變量函數(shù) f ( X ) f(X) f(X)的梯度也可以用其偏導(dǎo)數(shù)表示為
? f ( x ) = [ ? f ? x 11 ? f ? x 12 ? ? f ? x 1 n ? f ? x 21 ? f ? x 22 ? ? f ? x 2 n ? ? ? ? f ? x m 1 ? f ? x m 2 ? ? f ? x m n ] {\nabla}f(x)=\left[ \begin{matrix} \frac{{\partial}f}{{\partial}x_{11}} & \frac{{\partial}f}{{\partial}x_{12}} & \cdots& \frac{{\partial}f}{{\partial}x_{1n}}\\ \frac{{\partial}f}{{\partial}x_{21}} & \frac{{\partial}f}{{\partial}x_{22}} & \cdots& \frac{{\partial}f}{{\partial}x_{2n}}\\ \vdots & \vdots & &\vdots\\ \frac{{\partial}f}{{\partial}x_{m1}} & \frac{{\partial}f}{{\partial}x_{m2}} & \cdots& \frac{{\partial}f}{{\partial}x_{mn}} \end{matrix} \right] ?f(x)= ??x11??f??x21??f???xm1??f???x12??f??x22??f???xm2??f???????x1n??f??x2n??f???xmn??f?? ?
F r a ˊ c h e t Fr\acute{a}chet Fraˊchet可微的定義和使用往往比較繁瑣，為此還有另一種定義----- G a ^ t e a u x G\hat{a}teaux Ga^teaux可微
定義：設(shè) f ( X ) f(X) f(X)為矩陣變量函數(shù)，如果存在矩陣 G ∈ R m ? n G{\in}R^{m*n} G∈Rm?n對(duì)任意方向 V ∈ R m ? n V{\in}R^{m*n} V∈Rm?n滿足
lim ? t → 0 f ( X + t V ) ? f ( X ) ? t < G , V > t = 0 \lim_{t{\rightarrow}0}\frac{f(X+tV)-f(X)-t<G,V>}{t}=0 t→0lim?tf(X+tV)?f(X)?t<G,V>?=0
則稱 f f f關(guān)于 X X X是 G a ^ t e a u x G\hat{a}teaux Ga^teaux的，就稱G為 f f f在 G a ^ t e a u x G\hat{a}teaux Ga^teaux可微意義下的梯度
若 F r a ˊ c h e t Fr\acute{a}chet Fraˊchet可微可以推出 G a ^ t e a u x G\hat{a}teaux Ga^teaux可微，反之則不可以，但這本書(shū)討論的函數(shù)基本都是 F r a ˊ c h e t Fr\acute{a}chet Fraˊchet可微的，所以我們目前無(wú)需討論，大家了解一下就好了~，統(tǒng)一將矩陣變量函數(shù) f ( X ) f(X) f(X)的導(dǎo)數(shù)記為 ? f ? X \frac{{\partial}f}{{\partial}X} ?X?f?或者 ? f ( X ) {\nabla}f(X) ?f(X)
舉個(gè)例子把，免得大家不知道有什么用
考慮線性函數(shù)： f ( X ) = T r ( A X T B ) f(X)=Tr(AX^TB) f(X)=Tr(AXTB)，其中 A ∈ R p ? n , B ∈ R m ? p , X ∈ R m ? n A{\in}R^{p*n},B{\in}R^{m*p},X{\in}R^{m*n} A∈Rp?n,B∈Rm?p,X∈Rm?n對(duì)任意方向 V ∈ R m ? n V{\in}R^{m*n} V∈Rm?n以及 t ∈ R t{\in}R t∈R，有
lim ? t → 0 f ( X + t V ) ? f ( X ) t = lim ? t → 0 T r ( A ( X + t V ) T B ? T r ( A X T B ) ) t \lim_{t{\rightarrow}0}\frac{f(X+tV)-f(X)}{t}=\lim_{t{\rightarrow}0}\frac{Tr(A(X+tV)^TB-Tr(AX^TB))}{t} t→0lim?tf(X+tV)?f(X)?=t→0lim?tTr(A(X+tV)TB?Tr(AXTB))?
= T r ( A V T B ) = < B A , V > =Tr(AV^TB)=<BA,V> =Tr(AVTB)=<BA,V>
所以， ? f ( X ) = B A {\nabla}f(X)=BA ?f(X)=BA
我學(xué)到這里時(shí)候會(huì)有一個(gè)疑問(wèn)，就是 T r ( A V T B ) = < B A , V > Tr(AV^TB)=<BA,V> Tr(AVTB)=<BA,V>是為什么呢？
我們知道， T r ( A V T B ) = T r ( B A V T ) Tr(AV^TB)=Tr(BAV^T) Tr(AVTB)=Tr(BAVT)這個(gè)是跡的基本性質(zhì)， B A BA BA和 V V V都是 m ? n m*n m?n的，那么這時(shí)候又有一個(gè)性質(zhì)，假設(shè)C和D是相同規(guī)模的矩陣，那么 T r ( A T B ) = < A , B > Tr(A^TB)=<A,B> Tr(ATB)=<A,B>
我這里是參考知乎jordi的，這是他的一個(gè)關(guān)于3*3矩陣的推導(dǎo)
鏈接：https://www.zhihu.com/question/274052744/answer/1521521561
那么這樣就可以推出 T r ( A V T B ) = T r ( V T , B A ) = < B A , V > Tr(AV^TB)=Tr(V^T,BA)=<BA,V> Tr(AVTB)=Tr(VT,BA)=<BA,V>啦
2.2.3 自動(dòng)微分
自動(dòng)微分是使用計(jì)算機(jī)導(dǎo)數(shù)的算法，在神經(jīng)網(wǎng)絡(luò)中，我們通過(guò)前向傳播的方式將輸入數(shù)據(jù) a a a轉(zhuǎn)化為 y ^ \hat{y} y^?，也就是將輸入數(shù)據(jù) a a a作為初始信息，將其傳遞到隱藏層的每個(gè)神經(jīng)元，處理后輸出得到 y ^ \hat{y} y^?。
通過(guò)比較輸出得到 y ^ \hat{y} y^?與真實(shí)標(biāo)簽y，可以定義一個(gè)損失函數(shù) f ( x ) f(x) f(x)，其中 x x x表示所有神經(jīng)元對(duì)飲的參數(shù)集合， f ( x ) f(x) f(x)一般是多個(gè)函數(shù)復(fù)合的形式，為了找到最優(yōu)的參數(shù)，我們需要通過(guò)優(yōu)化算法來(lái)調(diào)整 x x x使得 f ( x ) f(x) f(x)達(dá)到最小，因此，對(duì)神經(jīng)元參數(shù) x x x的計(jì)算是不可避免的
這一塊就是講了一個(gè)神經(jīng)網(wǎng)絡(luò)的前向傳播和后向求導(dǎo)，自動(dòng)微分有兩種方式，前向模式和后向模式，前向模式就是變傳播變求導(dǎo)，后向模式就是前傳播再一層層求導(dǎo)，很顯然現(xiàn)在大家學(xué)的都是后向模式這種的吧，因?yàn)樗麖?fù)雜度更低，計(jì)算代價(jià)小
2.3 廣義實(shí)值函數(shù)
數(shù)學(xué)分析的課程中我們學(xué)習(xí)了函數(shù)的基本概念，函數(shù)是從向量空間 R n R^n Rn到數(shù)據(jù)域 R R R的映射，而在最優(yōu)化領(lǐng)域，經(jīng)常涉及到對(duì)某個(gè)函數(shù)的某一個(gè)變量取inf(sup)操作，這導(dǎo)致函數(shù)的取值可能為無(wú)窮，為了能更方便的描述優(yōu)化問(wèn)題，我們需要對(duì)函數(shù)的定義進(jìn)行某種擴(kuò)展。
那么 what is 廣義實(shí)值函數(shù)呢？
令 R ˉ = R ? ∞ \bar{R}=R{\bigcup}{\infty} Rˉ=R?∞為廣義實(shí)數(shù)空間，則映射 f : R n → R ˉ f:R^n{\rightarrow}\bar{R} f:Rn→Rˉ稱為廣義實(shí)值函數(shù)，可以看到，就是值域多了兩個(gè)特殊的值，正負(fù)無(wú)窮
2.3.1 適當(dāng)函數(shù)
適當(dāng)函數(shù)：給定廣義實(shí)值函數(shù) f f f和非空集合 X X X，如果存在 x ∈ X x{\in}X x∈X使得 f ( x ) < + ∞ f(x)<+{\infty} f(x)<+∞，并且對(duì)任意的 x ∈ X x{\in}X x∈X，都有 f ( x ) > ? ∞ f(x)>-{\infty} f(x)>?∞，那么稱函數(shù) f f f關(guān)于集合 X X X是適當(dāng)?shù)?br /> 總結(jié)一下，就是說(shuō)適當(dāng)函數(shù) f f f呢，至少有一處的取值不為正無(wú)窮，以及處處取值不為負(fù)無(wú)窮。對(duì)于最優(yōu)化問(wèn)題，適當(dāng)函數(shù)可以幫助我們?nèi)サ粢恍┎桓信d趣的函數(shù)，從一個(gè)比較合理的函數(shù)類去考慮問(wèn)題。這應(yīng)該很好理解，我們加入討論一個(gè)min問(wèn)題，他至少有個(gè)取值不能為正無(wú)窮吧，要不然怎么取min，然后處處取值不能為負(fù)無(wú)窮，要不討論有啥意義對(duì)吧？
我們約定，若本書(shū)無(wú)特殊說(shuō)明，定理中所討論的函數(shù)均為適當(dāng)函數(shù)
對(duì)于適當(dāng)函數(shù) f f f，規(guī)定其定義域
d o m f = { x ∣ f ( x ) < + ∞ } domf=\{x|f(x)<+{\infty}\} domf={x∣f(x)<+∞}
因?yàn)閷?duì)于適當(dāng)函數(shù)的最小值肯定不可能在正無(wú)窮處取到^^
2.3.2 閉函數(shù)
閉函數(shù)是另一類重要的廣義實(shí)值函數(shù)，閉函數(shù)可以看作是連續(xù)函數(shù)的一種推廣
在說(shuō)閉函數(shù)之前，我們先引入一些基本概念：
1.下水平集
下水平集是描述實(shí)值函數(shù)取值的一個(gè)重要概念：為此有如下定義
（ α \alpha α-下水平集）對(duì)于廣義實(shí)值函數(shù)： f : R n → R ˉ f:R^n{\rightarrow}\bar{R} f:Rn→Rˉ
C α = { x ∣ f ( x ) ≤ α } C_{\alpha}=\{x|f(x)\le{\alpha}\} Cα?={x∣f(x)≤α}
稱為 f f f的 α \alpha α-下水平集
就是取值不能超過(guò) α \alpha α嘛，若 C α C_{\alpha} Cα?非空，我們知道 f ( x ) f(x) f(x)的全局最小點(diǎn)一定落在 C α C_{\alpha} Cα?中，無(wú)需考慮之外的點(diǎn)
2.上方圖
上方圖是從集合的角度來(lái)描述一個(gè)函數(shù)的具體性質(zhì)，有如下定義：
對(duì)于廣義實(shí)值函數(shù) f ： R n → R ˉ f：R^n{\rightarrow}\bar{R} f：Rn→Rˉ
e p i f = { ( x , t ) ∈ R n + 1 ∣ f ( x ) ≤ t } epif=\{(x,t){\in}R^{n+1}|f(x){\le}t\} epif={(x,t)∈Rn+1∣f(x)≤t}
說(shuō)人話就是函數(shù) f f f上方的東西小于等于t（t取任意值）， f f f的很多性質(zhì)都可以通過(guò) e p i f epif epif得到，可以通過(guò) e p i f epif epif的一些性質(zhì) f f f的性質(zhì)
3.閉函數(shù)、下半連續(xù)函數(shù)
閉函數(shù)：設(shè) f : R n → R ˉ f:R^n{\rightarrow}\bar{R} f:Rn→Rˉ為廣義實(shí)值函數(shù)，若 e p i f epif epif為閉集，則稱 f f f為閉函數(shù)
下半連續(xù)函數(shù)：設(shè)廣義實(shí)值函數(shù) f : R n → R ˉ f:R^n{\rightarrow}\bar{R} f:Rn→Rˉ，若對(duì)任意的 x ∈ R n x{\in}R^n x∈Rn，有
lim?inf ? y → x f ( y ) ≥ f ( x ) \liminf_{y{\rightarrow}x} f(y)\ge{f(x)} y→xliminf?f(y)≥f(x)
則 f ( x ) f(x) f(x)為下半連續(xù)函數(shù)
我覺(jué)得如果不懂這個(gè)下極限的話，直接看文字會(huì)好得多
其實(shí)就是在 x 0 x_0 x0?處的鄰域處，如果 f( x 0 x_0 x0?) 減去一個(gè)正的微小值，從而可以恒小于該鄰域的所有 f ( x ) f(x) f(x)，則稱在該間斷點(diǎn)處有下半連續(xù)性。
如果是下圖這樣的
你的 x 0 x_0 x0?再往左邊取哪怕一點(diǎn)點(diǎn)，都會(huì)驟降，就達(dá)不到 x 0 x_0 x0?的鄰域中的 x x x比 f ( x 0 ) ? ε f(x_0)-{\varepsilon} f(x0?)?ε大，而如果是第一張圖，我們可以保證 x 0 x_0 x0?的左邊不會(huì)驟降，差不多就是這個(gè)意思
設(shè)廣義實(shí)值函數(shù) f : R n → R ˉ f:R^n{\rightarrow}\bar{R} f:Rn→Rˉ。則以下命題等價(jià)：
（1） f ( x ) f(x) f(x)的任意 α \alpha α-下水平集都是閉集
（2） f ( x ) f(x) f(x)是下半連續(xù)的
（3） f ( x ) f(x) f(x)是閉函數(shù)
具體證明我就不在這細(xì)細(xì)展開(kāi)了，同理，想知道可以和我探討或者自行谷歌~
閉集：? 如果對(duì)任意收斂序列，最終收斂到的點(diǎn)都在集合內(nèi)，那么集合是閉的
我們可以看到，其實(shí)閉函數(shù)和下半連續(xù)函數(shù)可以等價(jià)，以后往往只會(huì)出現(xiàn)一種定義
閉（下半連續(xù)）函數(shù)間的簡(jiǎn)單運(yùn)算會(huì)保持原有性質(zhì)
（1）加法，若 f f f和 g g g均為適當(dāng)?shù)拈]函數(shù)，并且 d o m f ? d o m g ≠ ? domf {\bigcap}domg{\neq}? domf?domg=?則 f + g f+g f+g也是閉函數(shù)，說(shuō)是適當(dāng)是避免出現(xiàn)未定式的情況，也就是負(fù)無(wú)窮+正無(wú)窮
（2）仿射映射的復(fù)合，若 f f f為閉函數(shù)，則 f ( A x + b ) f(Ax+b) f(Ax+b)也為閉函數(shù)
（3）取上確界，若每一個(gè)函數(shù) f α f_{\alpha} fα?均為閉函數(shù)，則 s u p α f α ( x ) sup_{\alpha}f_{\alpha}(x) supα?fα?(x)也為閉函數(shù)。
2.4 凸集
2.4.1 凸集的相關(guān)定義
說(shuō)實(shí)話凸集這個(gè)之前說(shuō)的一直都有聽(tīng)說(shuō)，但是具體的定義我一直沒(méi)有搞明白，現(xiàn)在學(xué)一下~
對(duì)于 R n R^n Rn中的兩個(gè)點(diǎn) x 1 ≠ x 2 x_1{\neq}x2 x1?=x2，形如
y = θ x 1 + ( 1 ? θ ) x 2 y={\theta}x_1+(1-{\theta})x_2 y=θx1?+(1?θ)x2?
的點(diǎn)形成了過(guò)點(diǎn) x 1 x_1 x1?和 x 2 x_2 x2?的直線，當(dāng) 0 ≤ θ ≤ 1 0{\le}{\theta}{\le}1 0≤θ≤1時(shí)，這樣的點(diǎn)形成了連接點(diǎn) x 1 x_1 x1?與 x 2 x_2 x2?的線段
我們定義：如果過(guò)集合 C C C中任意兩點(diǎn)的直線都在 C C C內(nèi)，則稱 C C C為仿射集，即
x 1 , x 2 ∈ C ? θ x 1 + ( 1 ? θ ) x 2 ∈ C ， ? θ ∈ R x_1,x_2{\in}C{\longrightarrow}{\theta}x_1+(1-{\theta})x_2{\in}C，{\forall}{\theta}{\in}R x1?,x2?∈C?θx1?+(1?θ)x2?∈C，?θ∈R
很明顯可以看出，線性方程組 A x = b Ax=b Ax=b的解集是仿射集，反之，任意仿射集都可以表示成一個(gè)線性方程組的解集
那么，凸集是定義是什么呢？
凸集：如果連接集合 C C C中任意兩點(diǎn)的線段都在 C C C內(nèi)，則稱 C C C為凸集，即
x 1 , x 2 ∈ C ? θ x 1 + ( 1 ? θ ) x 2 ∈ C ， ? 0 ≤ θ ≤ 1 x_1,x_2{\in}C{\longrightarrow}{\theta}x_1+(1-{\theta})x_2{\in}C，{\forall}0{\le}{\theta}{\le}1 x1?,x2?∈C?θx1?+(1?θ)x2?∈C，?0≤θ≤1
可以看到凸集就是仿射集的直線變成線段了而已，仿射集都是凸集
從凸集我們可以引出凸組合和凸包的概念，形如
x = θ 1 x 1 + θ 2 x 2 + ? + θ k x k x={\theta}_1x_1+{\theta}_2x_2+\cdots+{\theta}_kx_k x=θ1?x1?+θ2?x2?+?+θk?xk?
1 = θ 1 + θ 2 + ? + θ k ， θ i ≥ 0 , i = 1 , 2 , ? , k 1={\theta}_1+{\theta}_2+\cdots+{\theta}_k，{\theta}_i{\ge}0,i=1,2,\cdots,k 1=θ1?+θ2?+?+θk?，θi?≥0,i=1,2,?,k
的點(diǎn)稱為 x 1 , x 2 , ? , x k x_1,x_2,\cdots,x_k x1?,x2?,?,xk?的凸組合，集合 S S S中點(diǎn)所有的凸組合構(gòu)成的集合稱為 S S S的凸包，記作 c o n v S conv S convS,簡(jiǎn)而言之， c o n v S convS convS是包含 S S S的最小的凸集
若在凸組合的定義中去掉 θ i ≥ 0 {\theta}_i{\ge}0 θi?≥0的限制，我們可以得到仿射包的概念
仿射包：設(shè) S S S為 R n R^n Rn的子集，稱如下集合為S的仿射包：
{ x ∣ x = x = θ 1 x 1 + θ 2 x 2 + ? + θ k x k , x 1 , x 2 , ? , x k ∈ S , θ 1 + θ 2 + ? + θ k = 1 } \{x|x=x={\theta}_1x_1+{\theta}_2x_2+\cdots+{\theta}_kx_k, x_1,x_2,\cdots,x_k{\in}S,{\theta} _1+{\theta}_2+\cdots+{\theta}_k=1\} {x∣x=x=θ1?x1?+θ2?x2?+?+θk?xk?,x1?,x2?,?,xk?∈S,θ1?+θ2?+?+θk?=1}
記為 a f f i n e S affineS affineS
fangshebao
一般而言，一個(gè)集合的仿射包實(shí)際上是包含該集合的最小的仿射集
形如
x = θ 1 x 1 + θ 2 x 2 , θ 1 > 0 , θ 2 > 0 x={\theta}_1x_1+{\theta}_2x_2,{\theta}_1>0,{\theta}_2>0 x=θ1?x1?+θ2?x2?,θ1?>0,θ2?>0
的點(diǎn)稱為點(diǎn) x 1 , x 2 x_1,x_2 x1?,x2?的錐組合，若集合 S S S的任意點(diǎn)的錐組合都在 S S S中，則稱S為凸錐
2.4.2 重要的凸集
1.超平面和半空間
任取非零向量 a a a，形如 { x ∣ a T x = b } \{x|a^Tx=b\} {x∣aTx=b}的集合稱為超平面，形如 { x ∣ a T x ≤ b } \{x|a^Tx{\le}b\} {x∣aTx≤b}的集合稱為半空間， a a a是對(duì)應(yīng)的超平面和半空間的法向量，一個(gè)超平面將 R n R^n Rn分為兩個(gè)半空間，容易看出，超平面是仿射集和凸集，半空間是凸集但不是仿射集（這個(gè)如果理解了仿射集和凸集的概念應(yīng)該很好理解）
2.球、橢球、錐
球和橢球也是常見(jiàn)的凸集，球我們這里就不多介紹了
形如
{ x ∣ ( x ? x c ) T P ? 1 ( x ? x ) c ) ≤ 1 } \{x|(x-x_c)^TP^{-1}(x-x)_c){\le}1\} {x∣(x?xc?)TP?1(x?x)c?)≤1}
的集合稱為橢球，其中P對(duì)稱正定，橢球的另一種表示為 { x c + A u ∣ ∣ u 2 ∣ ∣ ≤ 1 } \{x_c+Au||u_2||{\le}1\} {xc?+Au∣∣u2?∣∣≤1}，A為非奇異的方陣
另外，我們稱集合
{ ( x , t ) ∣ ∣ ∣ x ∣ ∣ ≤ t } \{(x,t)|||x||{\le}t\} {(x,t)∣∣∣x∣∣≤t}
為范數(shù)錐，歐幾里得范數(shù)錐也稱為二次錐，范數(shù)錐是凸集
別忘了 t t t也是變量噢，看這個(gè)圖應(yīng)該就很好理解范數(shù)錐了
知乎鏈接：https://zhuanlan.zhihu.com/p/126072881
3.多面體
我們把滿足線性等式和不等式組的點(diǎn)的集合稱為多面體，即
{ x ∣ A x ≤ b , C x = d } \{x|Ax{\le}b,Cx=d\} {x∣Ax≤b,Cx=d}
多面體是有限個(gè)半空間和超平面的交集，所以是凸集
4.(半)正定錐
這個(gè)我直接把書(shū)上的先貼過(guò)來(lái)把，我目前也不太懂，就不能細(xì)說(shuō)
2.4.3 保凸的運(yùn)算
證明一個(gè)集合是凸集有兩種方式，第一種就是利用定義
x 1 , x 2 ∈ C , 0 ≤ θ ≤ 1 ? θ x 1 + ( 1 ? θ x 2 ∈ C ) x_1,x_2{\in}C,0{\le}{\theta}{\le}1{\longrightarrow}{\theta}x_1+(1-{\theta}x_2{\in}C) x1?,x2?∈C,0≤θ≤1?θx1?+(1?θx2?∈C)來(lái)證明集合 C C C是凸集。
第二種方法就是說(shuō)明集合C可以由簡(jiǎn)單的凸集（剛剛說(shuō)的超平面、半空間，范數(shù)球等）經(jīng)過(guò)保凸的運(yùn)算得到。
定理1：任意多個(gè)凸集的交為凸集
定理2：設(shè) f : R n → R m f:R^n{\rightarrow}R^m f:Rn→Rm是仿射變換（ f ( x ) = A x + b , A ∈ R m ? n , b ∈ R n f(x)=Ax+b,A{\in}R^{m*n},b{\in}R^n f(x)=Ax+b,A∈Rm?n,b∈Rn），則
（1）凸集在 f f f下的像是凸集：
S 是凸集 → f ( S ) → { f ( x ) ∣ x ∈ S } 是凸集 S是凸集{\rightarrow}f(S){\rightarrow}\{f(x)|x{\in}S\}是凸集 S是凸集→f(S)→{f(x)∣x∈S}是凸集
（2）凸集在 f f f下的原像是凸集
C 是凸集 → f ? 1 ( C ) → { x ∈ R n ∣ f ( x ) ∈ C } 是凸集 C是凸集{\rightarrow}f^{-1}(C){\rightarrow}\{x{\in}R^n|f(x){\in}C\}是凸集 C是凸集→f?1(C)→{x∈Rn∣f(x)∈C}是凸集
就是經(jīng)過(guò)縮放、平移或者投像仍是凸集
2.4.4 分離超平面定理
這是一個(gè)凸集的重要性質(zhì)，即可以用超平面分離不相交的凸集，最基本的結(jié)果是分離超平面定理和支撐超平面定理
分離超平面定理：如果C和D是不相交的兩個(gè)凸集，則存在非零向量 a a a和常熟 b b b，使得
a T x ≤ b , ? x ∈ C , 且 a T x ≥ b , ? x ∈ D a^Tx{\le}b,{\forall}x{\in}C,且a^Tx{\ge}b,{\forall}x{\in}D aTx≤b,?x∈C,且aTx≥b,?x∈D
即超平面 { x ∣ a T x = b } \{x|a^Tx=b\} {x∣aTx=b}分離了 C C C和 D D D
嚴(yán)格分離定理：即上述成立嚴(yán)格不等號(hào)，具體我就不展開(kāi)了
支撐超平面：給定集合 C C C及其邊界上一點(diǎn) x 0 x_0 x0?，如果 a ≠ 0 a{\neq}0 a=0滿足 a T x ≤ a T x 0 , ? x ∈ C a^Tx{\le}a^Tx_0,{\forall}x{\in}C aTx≤aTx0?,?x∈C,那么稱集合
{ x ∣ a T x = a T x 0 } \{x|a^Tx=a^T{x_0}\} {x∣aTx=aTx0?}
為 C C C在邊界點(diǎn) x 0 x_0 x0?處的支撐超平面
從幾何上來(lái)說(shuō)，此超平面與集合 C C C在點(diǎn) x 0 x_0 x0?處相切
支撐超平面定理：如果C是凸集，則在C的任意邊界點(diǎn)處都存在支撐超平面
這個(gè)定理其實(shí)有非常強(qiáng)的幾何直觀，就是給定一個(gè)平面后，可以把凸集邊界上的任意一點(diǎn)當(dāng)成支撐點(diǎn)將凸集放在該平面上，其他形狀的集合一般沒(méi)有這個(gè)性質(zhì)。