暴雪退款申請(qǐng)快速入口seo 0xu
?? 本系列文章主要是我在學(xué)習(xí)《數(shù)值優(yōu)化》過(guò)程中的一些筆記和相關(guān)思考，主要的學(xué)習(xí)資料是深藍(lán)學(xué)院的課程《機(jī)器人中的數(shù)值優(yōu)化》和高立編著的《數(shù)值最優(yōu)化方法》等，本系列文章篇數(shù)較多，不定期更新，上半部分介紹無(wú)約束優(yōu)化，下半部分介紹帶約束的優(yōu)化，中間會(huì)穿插一些路徑規(guī)劃方面的應(yīng)用實(shí)例
??
?? 三十三、伴隨靈敏度分析
?? 伴隨靈敏度分析可以避免冗余信息的計(jì)算，在下面的例子中，我們想要求解Ax=b1、Ax=b2 … Ax=bm等一系列方程組，第一種求解思路是將A矩陣進(jìn)行LU分解, A = L U A=LU A=LU，求逆后可得到 A ? 1 = U ? 1 L ? 1 A^{-1}=U^{-1}L^{-1} A?1=U?1L?1,然后依次將b1~bm代入下式即可得到這一系列方程組的解
?? x i = U ? 1 L ? 1 b i x_i=U^{-1}L^{-1}b_i xi?=U?1L?1bi?
?? 但如果我們事先知道需要使用那些數(shù)據(jù)，那么我們能不能僅把需要使用的變量求出來(lái)？比如我們的目標(biāo)是求每個(gè)xi的平均值ai，比如所有x1的平均值a1，那么我們是不是不需要求出每個(gè)xi的具體值，而僅僅需要他們的平均值ai。
?? a i = c T x i = c T A ? 1 b i = b i T A ? T c a_{i}=c^{T}x_{i}=c^{T}A^{-1}b_{i}=b_{i}^{T}A^{-T}c ai?=cTxi?=cTA?1bi?=biT?A?Tc
?? 之前需要先算 A ? 1 b i A^{-1}b_{i} A?1bi? 部分，再算 c T A ? 1 b i c^TA^{-1}b_i cTA?1bi?,現(xiàn)在可以先算 A ? T c A^{-T}c A?Tc,再算 b i T A ? T c b_i^TA^{-T}c biT?A?Tc，我們不需要對(duì)每個(gè)bi求一個(gè)線性方程組了，僅需要求一個(gè)方程組 q ≡ A ? T c q\equiv A^{-T}c q≡A?Tc，求出 q q q之后，再與bi做一個(gè)點(diǎn)積即可， a i = b i T q a_i=b_i^Tq ai?=biT?q
?? 伴隨靈敏度分析的思想是在計(jì)算矩陣相乘的時(shí)候考慮那個(gè)先乘，那個(gè)后乘。線性方程組有一個(gè)伴隨線性方程組，伴隨靈敏度分析允許優(yōu)化一小部分設(shè)計(jì)參數(shù)，而不是全部參數(shù)。
?? 假設(shè)x是一個(gè)線性方程組的解，它的維度很大，它是一個(gè)完備的參數(shù)，從x可以獲得所有我們想要的信息，但我們不能直接處理這么大維度的優(yōu)化，我們需要設(shè)一組設(shè)計(jì)參數(shù) p = ( p 1 , p 2 , . . . , p M ) \mathbf{p}=(p_{1},p_{2},...,p_{M}) p=(p1?,p2?,...,pM?)，我們要算的是一些目標(biāo)函數(shù) g ( p , x ) g(\mathbf{p},\mathbf{x}) g(p,x)關(guān)于參數(shù) p 1 , p 2 , … , p M p_{1},p_{2},\ldots,p_{M} p1?,p2?,…,pM?的梯度
?? d g d p j = ? g ? p j + ∑ i = 1 N ? g ? x i ? x i ? p j d g d p = g p + g x x p \begin{aligned}\frac{dg}{dp_j}&=\frac{\partial g}{\partial p_j}+\sum_{i=1}^N\frac{\partial g}{\partial x_i}\frac{\partial x_i}{\partial p_j}\\\\\frac{dg}{d\mathbf{p}}&=g_\mathbf{p}+g_\mathbf{x}\mathbf{x_p}\end{aligned} dpj?dg?dpdg??=?pj??g?+i=1∑N??xi??g??pj??xi??=gp?+gx?xp??
?? 一般認(rèn)為 ? g ? p j 和 ? g ? x i \frac{\partial g}{\partial p_j}和\frac{\partial g}{\partial x_i} ?pj??g?和?xi??g?是容易獲得的， ? x i ? p j \frac{\partial x_{i}}{\partial p_{j}} ?pj??xi??是不知道的
?? A p j x + A x p j = b p j ? x p j = A ? 1 [ b p j ? A p j x ] A_{p_j}\mathbf{x}+A\mathbf{x}_{p_j}=b_{p_j}\quad\Rightarrow\quad\mathbf{x}_{p_j}=A^{-1}[b_{p_j}-A_{p_j}\mathbf{x}] Apj??x+Axpj??=bpj???xpj??=A?1[bpj???Apj??x]
?? 我們使用矩陣相乘交換順序的思想，把解m次 N 2 N^2 N2復(fù)雜度的方程組，轉(zhuǎn)換為解一次就可以了
?? 應(yīng)用示例一：
?? 應(yīng)用示例二：
?? 當(dāng)路徑上選取的優(yōu)化點(diǎn)變密集后，安全性會(huì)更好，那么我們能不能，不選取那么多的優(yōu)化點(diǎn)，而同樣使其有較好的安全性
?? 對(duì)于任意階樣條，我們可以解耦線段的數(shù)目和約束的數(shù)目。所有的路徑點(diǎn)和持續(xù)時(shí)間都是我們軌跡的設(shè)計(jì)參數(shù)(決策變量)。樣條系數(shù)是由路點(diǎn)確定的線性方程組的解。
?? A ( T ) c ( p , T ) = b ( p ) \mathbf{A(T)c(p,T)=b(p)} A(T)c(p,T)=b(p)
?? A和b構(gòu)成了樣條系數(shù)的線性方程組。這很自然地符合伴隨敏感性分析的模型。
?? 三十四、線性方程組求解器的分類和特點(diǎn)
?? 線性方程組求解器可分為兩大類或三小類，兩大類即直接求解和迭代求解，直接求解可以得到Ax=b的精確解，迭代求解隨著迭代次數(shù)的增多，所得到的近似解與精確解的誤差也逐漸減小。三小類是因?yàn)橛械那蠼馄鲿?huì)利用矩陣的稀疏結(jié)構(gòu)，而有的求解器不利用，因此，直接法又分為稠密法和稀疏直接法。
?? （1）稠密法
?? 具有簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)，不需要索引數(shù)據(jù)結(jié)構(gòu)等特殊的數(shù)據(jù)結(jié)構(gòu)，采用矩陣的直接表示，主要是O(N3)分解算法
?? （2）稀疏直接法
?? 當(dāng)矩陣中有很多0元素時(shí)，我們可以僅儲(chǔ)存非0元素的位置和具體的值，使其占較少的內(nèi)存。
?? 因子分解成本取決于問(wèn)題結(jié)構(gòu)（1D低成本；2D可接受成本；3D高成本；不容易給出一般規(guī)則，NP難以排序以獲得最佳稀疏性）
?? （3）迭代法
?? 迭代求取近似解，僅需要知道 y = A x ( m a y b e y = A T x ) y=Ax\mathrm{~(maybe~}y=A^Tx) y=Ax?(maybe?y=ATx)，良好的收斂性取決于預(yù)條件。
–
?? 當(dāng)我們求解Ax=b時(shí)，如果是稠密的矩陣，盡可能的根據(jù)矩陣的對(duì)稱性、半正定性、帶狀結(jié)構(gòu)等特點(diǎn)，以此來(lái)挑選不同的稠密求解器，比如使用LAPACK/ScaLAPACK庫(kù)，或者Eigen庫(kù)
?? 若，我們知道矩陣的非零元素比零元素少很多，可以選用稀疏直接法中的求解器，看看能不能提前把矩陣預(yù)分解
?? 如果問(wèn)題比較大，如 1 0 5 10^5 105，此時(shí)采用稠密法會(huì)有問(wèn)題，可以用CG方法處理正定對(duì)稱矩陣，還有一系列迭代法可以處理對(duì)稱不定或非對(duì)稱的矩陣。
?? 因式分解有很多種方法，比如
?? L U , L L T / L L H , L D L T / L D L H , Q R , L Q , Q R Z , generalized?QR?and?RQ \begin{aligned}LU,LL^T /LL^H,LDL^T/LDL^H,QR,LQ,QRZ,\end{aligned}\text{generalized QR and RQ} LU,LLT/LLH,LDLT/LDLH,QR,LQ,QRZ,?generalized?QR?and?RQ
?? 除了因式分解，還有對(duì)稱/Hermitian和非對(duì)稱特征值、奇異值分解、廣義特征值與奇異值分解
?? LU分解其實(shí)就是高斯消元法，把一個(gè)矩陣進(jìn)行高斯消元，進(jìn)行一些行變換
?? A = P L U A=PLU A=PLU
?? 稀疏LU分解法不僅需要做行變換，還需要做列變換。
?? Cholesky分解：
?? 稀疏Cholesky分解：
?? LDL分解：
?? 稀疏矩陣：
?? 稀疏矩陣分解：
?? 稀疏排序會(huì)對(duì)虛實(shí)化的稀疏性產(chǎn)生巨大的影響：
?? 選擇產(chǎn)生最小二乘分解的排序的一般問(wèn)題是困難的，但是，幾個(gè)簡(jiǎn)單的啟發(fā)式方法是非常有效的。例如嵌套排序方法，可以起作用。
?? 迭代法：
?? 三十五、優(yōu)化軟件
?? 1、swMATH
?? 里面包含優(yōu)化、線性代數(shù)、大規(guī)模矩陣運(yùn)算等豐富的資源
?? 鏈接：https://zbmath.org/software/
?? 2、gamsworld
?? gamsworld收錄了很多的工具，在這里可以找到錐規(guī)劃等性能測(cè)評(píng)的手段
?? 鏈接：https://gamsworld.org/
?? 鏈接：https://github.com/GAMS-dev/gamsworld
?? 3、DECISION TREE FOR OPTIMIZATION SOFTWARE
?? 可以根據(jù)優(yōu)化問(wèn)題的結(jié)構(gòu)，查找某個(gè)問(wèn)題有哪些現(xiàn)有的方案
?? 鏈接：http://plato.asu.edu/guide.html
?? 4、Mathematical Software
?? 里面包含優(yōu)化、非線性求解器等豐富的資源
?? 鏈接：https://arnold-neumaier.at/software.html
?? 5、neos solvers
?? neos solvers是比較有名的求解器
?? 鏈接：https://neos-server.org/neos/solvers/index.html
?? 6、netlib
?? 里面幾乎包含所有的線性求解辦法
?? 鏈接：https://netlib.org/
?? 7、GAMS
?? 里面包含一些數(shù)學(xué)庫(kù)，不僅僅是優(yōu)化
?? 鏈接：https://gams.nist.gov/
?? 8、HSL Software
?? 專門的線性方程組求解器，包含很多源代碼
?? 鏈接：https://www.hsl.rl.ac.uk/catalogue/
?? 9、autodiff
?? 收集了一些求微分的方法的網(wǎng)站
?? 鏈接：https://www.autodiff.org/
?? 10、Local Optimization Software
?? 鏈接：https://arnold-neumaier.at/glopt/software_l.html
?? 11、Global Optimization Software
?? 鏈接：https://arnold-neumaier.at/glopt/software_g.html
?? 參考資料：
?? 1、數(shù)值最優(yōu)化方法（高立 編著）
?? 2、機(jī)器人中的數(shù)值優(yōu)化