線性搜索演算法

『壹』 線性規劃(LP)基本概念和搜索演算法

可以用一個符號描述一系列類似的數量值

一個方程，如果他是關於決策變數的常熟加權求和形式，則該方程式 線性方程(liner) ，佛則該方程為 非線性方程(non-linear)

目標函數 以及約束方程 中均為關於決策變數的線性方程，則該優化模型為 線性規劃(linear program, LP) ，其中目標函數可以為滿足約束的任意整數或者分數

目標函數 以及約束方程 中存在關於決策變數的線性方程，則該優化模型為 非線性規劃(nonlinear program, LP) ，其中目標函數可以為滿足約束的任意整數或者分數

一個優化模型，如果他的決策變數中存在離散變數，則該優化模型位 整數規劃(integer program, IP) ，如果整數規劃的所有決策變數均為離散變數，則該整數規劃為 純整數規劃(pure integer program) ；否則為 混合整數規劃(mixed integer program) 。

搜索演算法(improving search) 通過檢查鄰域來尋找比當前更好地解，若有改進則替換當前解，繼續迭代，直到鄰域中沒有更好的解為止。搜索演算法又稱為 局部改進(local improvement) ， 爬山演算法(hillclimbing) ， 局部搜索(local search) 或 鄰域搜索(neighborhood search)

倘若一組可行解周圍足夠小的的鄰域內沒有優於該解的可行點，則稱為 局部最優解(local optimum) ，最小化(最大化)問題存在 局部最小(最大)解 。

如果在全局范圍內不存在目標值優於某可行解的其他可行點，則稱為 全局最優解(global optimum) ，最小化(最大化)問題存在 全局最小(最大)解

搜索演算法沿 由當前點 向下一個搜索點 移動，其中 是當前點 處的 搜索方向(move direction) ， 是沿該方向前進的 步長 ， 。

對於所有足夠小的 都有 ,則稱 是當前解的一個 改進方向(improving direction) ,如果滿足所有約束條件，則為 可行改進方向 。

如果優化模型的目標函數 是光滑的(所有決策變數都是可微的)，那麼，當 是一個n維向量的函數，當它有一個一階片倒數，這些導數組成的n維向量稱為 梯度

導數(derivative) ，描述函數隨參數的變化率，可以看做斜率。 偏導數(partial derivative) ，是保持其他變數恆定時，關於其中一個變數的導數

對於最大化目標函數 ,若 ，搜索方向 是 處的可改進方向，若 ，搜索方向 不是 處的可改進方向。

對於最小化目標函數 ,若 ，搜索方向 是 處的可改進方向，若 ，搜索方向 不是 處的可改進方向。

當目標函數梯度 ，是最大化目標 的一個改進方向， 是最小化目標函數 的一個改進方向

如果可行域內任意兩點的連線都在可行域內，則稱該可行域為 凸集 。

離散的可行集總是非凸集

若優化模型的可行集是凸集，那麼對任意可行解始終存在指向另一個解的可行方向，意味著，只要存在最優解，可能性不會阻礙局部最優解發展為全局最優解。

線性約束的可行集又稱為多面體集。

如果優化模型的所有約束都是線性的，那麼該模型的可行域是凸集

兩階段法

大M法

『貳』 梯度下降中的線性搜索計算學習率是怎麼理解

梯度下降法是一個最優化演算法，通常也稱為最速下降法。最速下降法是求解無約束優化問題最簡單和最古老的方法之一，雖然現在已經不具有實用性，但是許多有效演算法都是以它為基礎進行改進和修正而得到的。最速下降法是用負梯度方向為搜索方向的，最速下降法越接近目標值，步長越小，前進越慢。
梯度下降法可以用於求解非線性方程組。
顧名思義，梯度下降法的計算過程就是沿梯度下降的方向求解極小值（也可以沿梯度上升方向求解極大值）。

表示梯度方向上的搜索步長。梯度方向我們可以通過對函數求導得到，步長的確定比較麻煩，太大了的話可能會發散，太小收斂速度又太慢。一般確定步長的方法是由線性搜索演算法來確定，即把下一個點的坐標看做是ak+1的函數，然後求滿足f(ak+1)的最小值即可。
因為一般情況下，梯度向量為0的話說明是到了一個極值點，此時梯度的幅值也為0.而採用梯度下降演算法進行最優化求解時，演算法迭代的終止條件是梯度向量的幅值接近0即可，可以設置個非常小的常數閾值。