非線性規劃

非線性規劃是一種求解目標函式或約束條件中有一個或幾個非線性函式的最最佳化問題的方法。運籌學的一個重要分支。20世紀50年代初，庫哈(H.W.Kuhn) 和托克 (A.W.Tucker) 提出了非線性規劃的基本定理，為非線性規劃奠定了理論基礎。這一方法在工業、交通運輸、經濟管理和軍事等方面有廣泛的套用，特別是在“最優設計”方面，它提供了數學基礎和計算方法，因此有重要的實用價值。

基本介紹

• 中文名：非線性規劃
• 外文名：nonlinear programming
• 套用：工程、管理、經濟
• 意義：為最優設計提供了有力的工具
• 所屬學科：運籌學
• 基本概念：具有非線性約束或目標的數學規劃

發展歷史

非線性規劃是20世紀50年代才開始形成的一門新興學科。1951年H.W.庫恩和A.W.塔克發表的關於最優性條件（後來稱為庫恩－塔克條件）的論文是非線性規劃正式誕生的一個重要標誌。在50年代還得出了可分離規劃和二次規劃的n種解法，它們大都是以G.B.丹齊克提出的解線性規劃的單純形法為基礎的。50年代末到60年代末出現了許多解非線性規劃問題的有效的算法。20世紀80年代以來，隨著計算機技術的快速發展，非線性規劃方法取得了長足進步，在信賴域法、稀疏擬牛頓法、並行計算、內點法和有限存儲法等領域取得了豐碩的成果。

深入解析

常見問題

對於一個實際問題，在把它歸結成非線性規劃問題時，一般要注意如下幾點

（i）確定供選方案：首先要收集同問題有關的資料和數據，在全面熟悉問題的基礎上，確認什麼是問題的可供選擇的方案，並用一組變數來表示它們。

（ii）提出追求目標：經過資料分析，根據實際需要和可能，提出要追求極小化或極大化的目標。並且，運用各種科學和技術原理，把它表示成數學關係式。

（iii）給出價值標準：在提出要追求的目標之後，要確立所考慮目標的“好”或“壞”的價值標準，並用某種數量形式來描述它。

（iv）尋求限制條件：由於所追求的目標一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變數之間的一些不等式或等式來表示。

數學模型

對實際規劃問題作定量分析，必須建立數學模型。建立數學模型首先要選定適當的目標變數和決策變數，並建立起目標變數與決策變數之間的函式關係，稱之為目標函式。然後將各種限制條件加以抽象，得出決策變數應滿足的一些等式或不等式，稱之為約束條件。非線性規劃問題的一般數學模型可表述為求未知量x1，x2，…，xn，使滿足約束條件：

gi(x1，…，xn）≥0　i=1，…，m

hj(x1，…，xn)=0　j=1，…，p

並使目標函式f(x1，…，xn）達到最小值（或最大值）。其中f，諸gi和諸hj都是定義在n維向量空間Rn的某子集D（定義域）上的實值函式，且至少有一個是非線性函式。

上述模型可簡記為：

min f(x)

s.t. gi(x）≥0　i=1，…，m

hj(x)=0 j=1，…，p

其中x=(x1，…，xn）屬於定義域D，符號min表示“求最小值”，符號s.t.表示“受約束於”。

定義域D 中滿足約束條件的點稱為問題的可行解。全體可行解所成的集合稱為問題的可行集。對於一個可行解x*，如果存在x*的一個鄰域，使目標函式在x*處的值f(x*）優於 （指不大於或不小於）該鄰域中任何其他可行解處的函式值，則稱x*為問題的局部最優解（簡稱局部解）。如果f(x*）優於一切可行解處的目標函式值，則稱x*為問題的整體最優解（簡稱整體解）。實用非線性規劃問題要求整體解，而現有解法大多只是求出局部解。

最優方法

指尋求一元函式在某區間上的最優值點的方法。這類方法不僅有實用價值，而且大量多維最最佳化方法都依賴於一系列的一維最最佳化。常用的一維最最佳化方法有黃金分割法、切線法和插值法。

①　黃金分割法　又稱0.618法。它適用於單峰函式。其基本思想是：在初始尋查區間中設計一列點，通過逐次比較其函式值，逐步縮小尋查區間，以得出近似最優值點。

②　切線法　又稱牛頓法。它也是針對單峰函式的。其基本思想是：在一個猜測點附近將目標函式的導函式線性化，用此線性函式的零點作為新的猜測點，逐步疊代去逼近最優點。

③　插值法　又稱多項式逼近法。其基本思想是用多項式（通常用二次或三次多項式）去擬合目標函式。

此外，還有斐波那契法、割線法、有理插值法、分批搜尋法等。

無約束法

指尋求 n元實函式f在整個n維向量空間Rn上的最優值點的方法。這類方法的意義在於：雖然實用規劃問題大多是有約束的，但許多約束最最佳化方法可將有約束問題轉化為若干無約束問題來求解。

無約束最最佳化方法大多是逐次一維搜尋的疊代算法。這類疊代算法可分為兩類。一類需要用目標函式的導函式，稱為解析法。另一類不涉及導數，只用到函式值，稱為直接法。這些疊代算法的基本思想是：在一個近似點處選定一個有利搜尋方向，沿這個方向進行一維尋查，得出新的近似點。然後對新點施行同樣手續，如此反覆疊代，直到滿足預定的精度要求為止。根據搜尋方向的取法不同，可以有各種算法。屬於解析型的算法有：①梯度法：又稱最速下降法。這是早期的解析法，收斂速度較慢。②牛頓法：收斂速度快，但不穩定，計算也較困難。③共軛梯度法：收斂較快，效果較好。④變尺度法：這是一類效率較高的方法。其中達維登-弗萊徹-鮑威爾變尺度法，簡稱 DFP法，是最常用的方法。屬於直接型的算法有交替方向法（又稱坐標輪換法）、模式搜尋法、旋轉方向法、鮑威爾共軛方向法和單純形加速法等。

約束法

指前述一般非線性規劃模型的求解方法。常用的約束最最佳化方法有 4種。

①拉格朗日乘子法：它是將原問題轉化為求拉格朗日函式的駐點。

②制約函式法：又稱系列無約束最小化方法，簡稱SUMT法。它又分兩類，一類叫懲罰函式法，或稱外點法；另一類叫障礙函式法，或稱內點法。它們都是將原問題轉化為一系列無約束問題來求解。

③可行方向法：這是一類通過逐次選取可行下降方向去逼近最優點的疊代算法。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡約梯度法都屬於此類算法。

④近似型算法：這類算法包括序貫線性規劃法和序貫二次規劃法。前者將原問題化為一系列線性規劃問題求解，後者將原問題化為一系列二次規劃問題求解。

凸規劃

這是一類特殊的非線性規劃。在前述非線性規劃數學模型中，若f是凸函式，諸gi都是凹函式，諸hj都是一次函式，則稱之為凸規劃。所謂f是凸函式，是指f有如下性質：它的定義域是凸集，且對於定義域中任意兩點x和y及任一小於1的正數α，下式都成立：

f(（1-α）x +αy）α≤（1-α）f(x)+αf(y)

將上述不等式中的不等號反向即得凹函式的定義。所謂凸集，是指具有如下性質的集合：連結集合中任意兩點的直線段上的點全部屬於該集合。

對於一般的非線性規劃問題，局部解不一定是整體解。但凸規劃的局部解必為整體解，而且凸規劃的可行集和最優解集都是凸集。

二次規劃

一類特殊的非線性規劃。它的目標函式是二次函式，約束條件是線性的。求解二次規劃的方法很多。較簡便易行的是沃爾夫法。它是依據庫恩－塔克條件，線上性規劃單純形法的基礎上加以修正而成的。此外還有萊姆基法、畢爾法、凱勒法等。

幾何規劃

幾何規劃　一類特殊的非線性規劃它的目標函式和約束函式都是正定多項式（或稱正項式）。幾何規劃本身一般不是凸規劃，但經適當變數替換，即可變為凸規劃。幾何規劃的局部最優解必為整體最優解。求解幾何規劃的方法有兩類。一類是通過對偶規划去求解；另一類是直接求解原規劃，這類算法大多建立在根據幾何不等式將多項式轉化為單項式的思想上。

套用範圍

在經營管理、工程設計、科學研究、軍事指揮等方面普遍地存在著最最佳化問題。例如：如何在現有人力、物力、財力條件下合理安排產品生產，以取得最高的利潤；如何設計某種產品，在滿足規格、性能要求的前提下，達到最低的成本；如何確定一個自動控制系統的某些參數，使系統的工作狀態最佳；如何分配一個動力系統中各電站的負荷，在保證一定指標要求的前提下，使總耗費最小；如何安排庫存儲量，既能保證供應，又使儲存費用最低；如何組織貨源，既能滿足顧客需要，又使資金周轉最快等。對於靜態的最最佳化問題，當目標函式或約束條件出現未知量的非線性函式，且不便於線性化，或勉強線性化後會招致較大誤差時，就可套用非線性規劃的方法去處理。