最優化問題可以用什麼方法解決

❶ 最優化問題求解方法

在求解最優化問題中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）條件是兩種最常用的方法。在有等式約束時使用拉格朗日乘子法，在有不等約束時使用KKT條件。

我們這里提到的最優化問題通常是指對於給定的某一函數，求其在指定作用域上的全局最小值(因為最小值與最大值可以很容易轉化，即最大值問題可以轉化成最小值問題)。提到KKT條件一般會附帶的提一下拉格朗日乘子。對學過高等數學的人來說比較拉格朗日乘子應該會有些印象。二者均是求解最優化問題的方法，不同之處在於應用的情形不同。

一般情況下，最優化問題會碰到一下三種情況：

這是最簡單的情況，解決方法通常是函數對變數求導，令求導函數等於0的點可能是極值點。將結果帶回原函數進行驗證即可。

設目標函數為f(x)，約束條件為h_k(x)，形如:
s.t. 表示subject to ，「受限於」的意思，l表示有l個約束條件。

則解決方法是消元法或者拉格朗日法。消元法比較簡單不在贅述，這里主要講拉格朗日法，因為後面提到的KKT條件是對拉格朗日乘子法的一種泛化。

作為一種優化演算法，拉格朗日乘子法主要用於解決約束優化問題，它的基本思想就是通過引入拉格朗日乘子來將含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題。拉格朗日乘子背後的數學意義是其為約束方程梯度線性組合中每個向量的系數。

如何將一個含有n個變數和k個約束條件的約束優化問題轉化為含有（n+k）個變數的無約束優化問題？拉格朗日乘數法從數學意義入手，通過引入拉格朗日乘子建立極值條件，對n個變數分別求偏導對應了n個方程，然後加上k個約束條件（對應k個拉格朗日乘子）一起構成包含了（n+k）變數的（n+k）個方程的方程組問題，這樣就能根據求方程組的方法對其進行求解。

首先定義拉格朗日函數F(x)：

然後解變數的偏導方程：

我們上述討論的問題均為等式約束優化問題，但等式約束並不足以描述人們面臨的問題，不等式約束比等式約束更為常見，大部分實際問題的約束都是不超過多少時間，不超過多少人力，不超過多少成本等等。所以有幾個科學家拓展了拉格朗日乘數法，增加了KKT條件之後便可以用拉格朗日乘數法來求解不等式約束的優化問題了。

設目標函數f(x)，不等式約束為g(x)，有的教程還會添加上等式約束條件h(x)。此時的約束優化問題描述如下：

則我們定義不等式約束下的拉格朗日函數L，則L表達式為：

其中f(x)是原目標函數，hj(x)是第j個等式約束條件，λj是對應的約束系數，gk是不等式約束，uk是對應的約束系數。

常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標函數全部寫為一個式子L(a, b, x)= f(x) + a g(x)+b h(x)，

首先，我們先介紹一下什麼是KKT條件。

KKT條件是指在滿足一些有規則的條件下, 一個非線性規劃(Nonlinear Programming)問題能有最優化解法的一個必要和充分條件. 這是一個廣義化拉格朗日乘數的成果. 一般地, 一個最優化數學模型的列標准形式參考開頭的式子, 所謂 Karush-Kuhn-Tucker 最優化條件，就是指上式的最優點x∗必須滿足下面的條件:

1). 約束條件滿足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q

2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇為梯度運算元;

3). λj≠0且不等式約束條件滿足μi≥0,μigi(x∗)=0,i=1,2,…,p。

❷ 最優化方法

最優化方法，是指解決最優化問題的方法。

所謂最優化問題，指在某些約束條件下，決定某些可選擇的變數應該取何值，使所選定的目標函數達到最優的問題。即運用最新科技手段和處理方法，使系統達到總體最優，從而為系統提出設計、施工、管理、運行的最優方案。

由於實際的需要和計算技術的進步，最優化方法的研究發展迅速。

最優化方法（也稱做運籌學方法）是近幾十年形成的，它主要運用數學方法研究各種系統的優化途徑及方案，為決策者提供科學決策的依據。

最優化方法的主要研究對象是各種有組織系統的管理問題及其生產經營活動。最優化方法的目的在於針對所研究的系統，求得一個合理運用人力、物力和財力的最佳方案，發揮和提高系統的效能及效益，最終達到系統的最優目標。

實踐表明，隨著科學技術的日益進步和生產經營的日益發展，最優化方法已成為現代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經濟管理、工程建設、國防等各個領域，發揮著越來越重要的作用。

將介紹最優化方法的研究對象、特點，以及最胡亂彎優化方法模型的建立和模型的分析、求解、應用。主要是線性規劃問題陪芹的模型褲悶、求解（線性規劃問題的單純形解法）及其應用――運輸問題；以及動態規劃的模型、求解、應用――資源分配問題。

最優化方法：

1、微分學中求極值

2、無約束最優化問題

3、常用微分公式

4、凸集與凸函數

5、等式約束最優化問題

6、不等式約束最優化問題

7、變分學中求極值

❸ 用優化方法解決實際問題的一般步驟是什麼

用最優化方法解決實際問題，一般可經過下列步驟：
①提出最優化問題，收集有關數據和資料；
②建立最優化問題的數學模型,確定變數,列出目標函數和約束條件；
③分析模型，選擇合適的最優化方法；
④求解，一般通過編製程序，用計算機求最優解；
⑤最優解的檢驗和實施。上述 5個步驟中的工作相互支持和相互制約，在實踐中常常是反復交叉進行。

❹ 數學建模最優化方法

1、多目標優化問題。
對於教師和學生的滿意可以用幾個關鍵性的指標，如衡量老師的工作效率和工作強度及往返強度等，如定義
效率w=教師的實際上課時間/(教師坐班車時間+上課時間+在學校逗留時間)。
然後教師的滿意度S1為幾個關鍵性指標的加權平均。注意一些無量綱量和有量綱量的加權平均的歸一化問題。
對於學生可以定義每門課周頻次，每天上課頻次等等
對於學校滿意，可以定義班車出動次數，這個指標和教師的某一個指標是聯動的，教室和多媒體使用周期頻次和使用時長等等。
2、根據第一問的模型按照數據進行求解
3、教師、學生和學校的滿意度作為指標
4、根據結果提出合理化建議

❺ 解決經濟分析的最優化問題的基本步驟是什麼

從數學角度看,最優化問題可以分為無約束最優化和約束最優化。所謂無約束最優化問題是比較簡單的微分問題,可用微分求解。
管理決策問題往往也就是最優化問題,而比較常用和方便的方法就是邊際分析法。
所謂「無約束」,即產品產量、資源投入量、價格和廣告費的支出等都不受限制。在這種情況下,最優化的原則是:邊際收入等於邊際成本,也就是邊際利潤為零時,利潤最大,此時的業務量為最優業務量。管理決策中的諸多最優化問題,比如投入要素之間如何組合才能使成本最低;企業的產量多大,才能實現利潤最大,當因變數為自變數的連續函數時,經濟學與數學意義是統一的,可用邊際分析法解決;而在處理離散數列的最優化問題時則可以用統計的方法先將離散數列擬合成連續函數,求得最優點,然後在原離散數列中找到離擬合曲線最優點最近的前後兩點,比較其值及其投入量,既而求得最優點。
有約束條件的最優化包括一個或幾個貨幣、時間、生產能力或其他方面的限制,當存在不等式約束條件時,可以採用線性規劃。大多數情況下,管理者知道某些約束是連在一起的,即它們是同樣的約束條件,可以採用拉格朗日乘數法解決這些問題。
從數學上比較一般的觀點來看,所謂最優化問題可以概括為一種數學模型:結合一個函數F(x)以及自變數應滿足一定的條件,求X 為怎樣的值時,F(x)取得其最大值或最小值。通常,稱F(x)為目標函數,X 應滿足的條件為約束條件。求目標函數F(x)
在約束條件X 下的最大值或最小值問題,就是一般最優問題的數學模型,可以用數學符號簡潔地表示為MinF(x)或MaxF(x)。解決最優化問題地關鍵步驟是如何把實際問題,抽象成數學模型,也就是構造出目標函數與約束條件,一旦這一步完成,對於簡單問題,可藉助圖形或微積分來解決,遇到比較復雜地課題,可利用現有地數學軟體或最優化軟體,比如Matlab,Mathematica,Lindo,Lingo 等來計算。下面舉例說明如何計算有約束條件地最優化問題。
例設某種產品的產量是勞動力x和原料y(t)的函數,f(x),y=60X 3y 2,假定每單位勞動力費用100元,每單位原料費用200元,現有2萬元資金用於生產,為了得到最多的產品,應如何安排勞動力和原料。
解:依題意,可歸結為求函數f(x,y)=60x 3y 2在約束條件100x+200y=20000下的最大值,故可用拉格朗日乘數法求解。

❻ 幾種常用最優化方法

學習和工作中遇到的大多問題都可以建模成一種最優化模型進行求解，比如我們現在學習的機器學習演算法，大部分的機器學習演算法的本質都是建立優化模型，通過最優化方法對目標函數（或損失函數）進行優化，從而訓練出最好的模型。常見的優化方法(optimization)有梯度下降法、牛頓法和擬牛頓法、共軛梯度法等等。

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最簡單，也是最為常用的最優化方法。梯度下降法實現簡單，當目標函數是凸函數時，梯度下降法的解是全局解。一般情況下，其解不保證是全局最優解，梯度下降法的速度也未必是最快的。 梯度下降法的優化思想是用當前位置負梯度方向作為搜索方向，因為該方向為當前位置的最快下降方向，所以也被稱為是」最速下降法「。最速下降法越接近目標值，步長越小，前進越慢。

梯度下降 法的缺點：

（1）靠近極小值時收斂速度減慢;

（2）直線搜索時可能會產生一些問題；

（3）可能會「之字形」地下降。

在機器學習中，基於基本的梯度下降法發展了兩種梯度下降方法，分別為隨機梯度下降法和批量梯度下降法。

比如對一個線性回歸（Linear Logistics）模型，假設下面的h(x)是要擬合的函數，J( )為損失函數， 是參數，要迭代求解的值，求解出來了那最終要擬合的函數h( )就出來了。其中m是訓練集的樣本個數，n是特徵的個數。

1）批量梯度下降法（Batch Gradient Descent，BGD）

（1）將J( )對 求偏導，得到每個theta對應的的梯度：

(2）由於是要最小化風險函數，所以按每個參數 的梯度負方向，來更新每個 ：

        （3）從上面公式可以注意到，它得到的是一個全局最優解，但是每迭代一步，都要用到訓練集所有的數據，如果m很大，那麼可想而知這種方法的迭代速度會相當的慢。所以，這就引入了另外一種方法——隨機梯度下降。

對於批量梯度下降法，樣本個數m，x為n維向量，一次迭代需要把m個樣本全部帶入計算，迭代一次計算量為m*n2。

2）隨機梯度下降（Stochastic Gradient Descent，SGD）

        （1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：

（2）每個樣本的損失函數，對 求偏導得到對應梯度，來更新 ：

（3）隨機梯度下降是通過每個樣本來迭代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能只用其中幾萬條或者幾千條的樣本，就已經將

迭代到最優解了，對比上面的批量梯度下降，迭代一次需要用到十幾萬訓練樣本，一次迭代不可能最優，如果迭代10次的話就需要遍歷訓練樣本10次。但是，SGD伴隨的一個問題是噪音較BGD要多，使得SGD並不是每次迭代都向著整體最優化方向。

隨機梯度下降每次迭代只使用一個樣本，迭代一次計算量為n2，當樣本個數m很大的時候，隨機梯度下降迭代一次的速度要遠高於批量梯度下降方法。 兩者的關系可以這樣理解：隨機梯度下降方法以損失很小的一部分精確度和增加一定數量的迭代次數為代價，換取了總體的優化效率的提升。增加的迭代次數遠遠小於樣本的數量。

對批量梯度下降法和隨機梯度下降法的總結：

批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小，但是對於大規模樣本問題效率低下。

隨機梯度下降---最小化每條樣本的損失函數，雖然不是每次迭代得到的損失函數都向著全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近，適用於大規模訓練樣本情況。

2. 牛頓法和擬牛頓法（Newton's method & Quasi-Newton Methods）

1）牛頓法（Newton's method）

牛頓法是一種在實數域和復數域上近似求解方程的方法。方法使用函數 f  ( x )的泰勒級數的前面幾項來尋找方程 f  ( x ) = 0的根。牛頓法最大的特點就在於它的收斂速度很快。

具體步驟：

首先，選擇一個接近函數 f  ( x )零點的x0，計算相應的 f  ( x 0)和切線斜率 f  '  ( x 0)（這里 f '  表示函數 f   的導數）。然後我們計算穿過點( x 0, f   ( x 0))並且斜率為 f  '( x 0)的直線和 x  軸的交點的 x 坐標，也就是求如下方程的解：

我們將新求得的點的 x  坐標命名為 x 1，通常 x 1會比 x 0更接近方程 f   ( x ) = 0的解。因此我們現在可以利用 x 1開始下一輪迭代。迭代公式可化簡為如下所示：

已經證明，如果 f   '是連續的，並且待求的零點 x 是孤立的，那麼在零點 x 周圍存在一個區域，只要初始值 x 0位於這個鄰近區域內，那麼牛頓法必定收斂。 並且，如果 f   ' ( x )不為0, 那麼牛頓法將具有平方收斂的性能. 粗略的說，這意味著每迭代一次，牛頓法結果的有效數字將增加一倍。下圖為一個牛頓法執行過程的例子。

由於牛頓法是基於當前位置的切線來確定下一次的位置，所以牛頓法又被很形象地稱為是"切線法"。

關於牛頓法和梯度下降法的效率對比：

從本質上去看，牛頓法是二階收斂，梯度下降是一階收斂，所以牛頓法就更快。如果更通俗地說的話，比如你想找一條最短的路徑走到一個盆地的最底部，梯度下降法每次只從你當前所處位置選一個坡度最大的方向走一步，牛頓法在選擇方向時，不僅會考慮坡度是否夠大，還會考慮你走了一步之後，坡度是否會變得更大。所以，可以說牛頓法比梯度下降法看得更遠一點，能更快地走到最底部。（牛頓法目光更加長遠，所以少走彎路；相對而言，梯度下降法只考慮了局部的最優，沒有全局思想。）

根據wiki上的解釋，從幾何上說，牛頓法就是用一個二次曲面去擬合你當前所處位置的局部曲面，而梯度下降法是用一個平面去擬合當前的局部曲面，通常情況下，二次曲面的擬合會比平面更好，所以牛頓法選擇的下降路徑會更符合真實的最優下降路徑。

註：紅色的牛頓法的迭代路徑，綠色的是梯度下降法的迭代路徑。

牛頓法的優缺點總結：

優點：二階收斂，收斂速度快；

缺點：牛頓法是一種迭代演算法，每一步都需要求解目標函數的Hessian矩陣的逆矩陣，計算比較復雜。

2）擬牛頓法（Quasi-Newton Methods）

擬牛頓法是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。

擬牛頓法的本質思想是改善牛頓法每次需要求解復雜的Hessian矩陣的逆矩陣的缺陷，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復雜度。 擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。如今，優化軟體中包含了大量的擬牛頓演算法用來解決無約束，約束，和大規模的優化問題。

具體步驟：

擬牛頓法的基本思想如下。首先構造目標函數在當前迭代xk的二次模型：

這里Bk是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點：

其中我們要求步長ak 滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣Bk 代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣Bk的更新。現在假設得到一個新的迭代xk+1，並得到一個新的二次模型：

我們盡可能地利用上一步的信息來選取Bk。具體地，我們要求

從而得到

這個公式被稱為割線方程。常用的擬牛頓法有DFP演算法和BFGS演算法。

原文鏈接： [Math] 常見的幾種最優化方法 - Poll的筆記 - 博客園

❼ 數學優化問題(最優化問題)

  數學優化（Mathematical Optimization）問題，也叫最優化問題，是指在一定約束條件下，求解一個目標函數的最大值（或最小值）問題。
  數學優化問題的定義為：給定一個目標函數（也叫代價函數） f : A → R ，尋找一個變數（也叫參數） x ^∗ ∈ D ，使得對於所有 D 中的 x ， f(x ^∗ ) ≤ f(x) （最小化）；或者 f(x ^∗ ) ≥ f(x) （最大化），其中 D 為變數 x 的約束集，也叫可行域； D 中的變數被稱為是可行解。

  根據輸入變數 x 的值域是否為實數域，數學優化問題可以分為離散優化問題和連續優化問題。

  離散優化（Discrete Optimization）問題是目標函數的輸入變數為離散變數，比如為整數或有限集合中的元素。連續優化（Continuous Optimization）問題是目標函數的輸入變數為連續變數 x ∈ R ^d ，即目標函數為實函數。離散優化問題主要有兩個分支：

  離散優化問題的求解一般都比較困難，優化演算法的復雜度都比較高。後面的內容主要以連續優化為主。

  在連續優化問題中，根據是否有變數的約束條件，可以將優化問題分為無約束優化問題和約束優化問題。
   無約束優化問題（Unconstrained Optimization） 的可行域為整個實數域 D = R ^d ，可以寫為
其中 x ∈ R ^d 為輸入變數， f : R ^d → R 為目標函數。
   約束優化問題（Constrained Optimization） 中變數 x 需要滿足一些等式或不等式的約束。約束優化問題通常使用拉格朗日乘數法來進行求解。

  如果目標函數和所有的約束函數都為線性函數，則該問題為 線性規劃問題（Linear Programming） 。相反，如果目標函數或任何一個約束函數為非線性函數，則該問題為 非線性規劃問題（Nonlinear Programming） 。
  在非線性優化問題中，有一類比較特殊的問題是 凸優化問題（Convex Programming） 。在凸優化問題中，變數 x 的可行域為凸集，即對於集合中任意兩點，它們的連線全部位於在集合內部。目標函數 f 也必須為凸函數，即滿足
  凸優化問題是一種特殊的約束優化問題，需滿足目標函數為凸函數，並且等式約束函數為線性函數，不等式約束函數為凹函數。

   優化問題 一般都是通過 迭代 的方式來求解：通過猜測一個初始的估計 x ₀ ，然後不斷迭代產生新的估計 x ₁ , x ₂ , · · · x _t ，希望 x _t 最終收斂到期望的最優解 x ^∗旅散納 。一個好的優化演算法應該是在 一定的時間或空間復雜度下能夠快速准確地找到最優解。同時，好的優化演算法受初始掘培猜測點的影響較小，通過迭代能穩定地找到最優解 x ^∗ 的鄰域，然後迅速收斂於 x ^∗ 。
  優化演算法中常用的迭代方法有 線性搜索和置信域方法 等。線性搜索的策略是尋找方向和步長，具體演算法有梯度下降法、牛頓拆沒法、共軛梯度法等。

  對於很多非線性優化問題，會存在若干個局部的極小值。局部最小值，或局部最優解 x ^∗ 定義為：存在一個δ > 0，對於所有的滿足|| x − x∗|| ≤ δ 的 x ，公式 f(x ^∗ ) ≤ f(x) 成立。也就是說，在 x ^∗ 的附近區域內，所有的函數值都大於或者等於 f(x ^∗ ) 。對於所有的 x ∈ A ，都有 f(x∗) ≤ f(x) 成立，則 x ^∗ 為全局最小值，或全局最優解。一般的，求局部最優解是容易的，但很難保證其為全局最優解。 對於線性規劃或凸優化問題，局部最優解就是全局最優解 。