非線性規(guī)劃是具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃，是運(yùn)籌學(xué)的一個重要分支。非線性規(guī)劃研究一個n元實函數(shù)在一組等式或不等式的約束條件下的極值問題，且目標(biāo)函數(shù)和約束條件至少有一個是未知量的非線性函數(shù)。目標(biāo)函數(shù)和約束條件都是線性函數(shù)的情形則屬于線性規(guī)劃。

公元前 500年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了長方形長與寬的最佳比例為0.618,稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。在微積分出現(xiàn)以前，已有許多學(xué)者開始研究用數(shù)學(xué)方法解決最優(yōu)化問題。例如阿基米德證明：給定周長，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的原因。但是 最優(yōu)化方法真正形成為科學(xué)方法則在17世紀(jì)以后。17世紀(jì)，I.牛頓和G.W.萊布尼茨在他們所創(chuàng)建的微積分中，提出求解具有多個自變量的實值函數(shù)的最大值和最小值的方法。以后又進(jìn)一步討論具有未知函數(shù)的函數(shù)極值，從而形成變分法。這一時期的最優(yōu)化方法可以稱為古典最優(yōu)化方法。

最優(yōu)化方法不同類型的最優(yōu)化問題可以有不同的最優(yōu)化方法，即使同一類型的問題也可有多種最優(yōu)化方法。反之,某些最優(yōu)化方法可適用于不同類型的模型。最優(yōu)化問題的求解方法一般可以分成解析法、直接法、數(shù)值計算法和其他方法。

• ① 解析法：這種方法只適用于目標(biāo)函數(shù)和約束條件有明顯的解析表達(dá)式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導(dǎo)數(shù)的方法或變分法求出必要條件，通過必要條件將問題簡化，因此也稱間接法。
• ② 直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述時，無法用解析法求必要條件。此時可采用直接搜索的方法經(jīng)過若干次迭代搜索到最優(yōu)點(diǎn)。這種方法常常 根據(jù)經(jīng)驗或通過試驗得到所需結(jié)果。對于一維搜索(單變量極值問題)，主要用消去法或多項式插值法；對于多維搜索問題(多變量極值問題)主要應(yīng)用爬山法。
• ③ 數(shù)值計算法：這種方法也是一種直接法。它以梯度法為基礎(chǔ)，所以是一種解析與數(shù)值計算相結(jié)合的方法。
• ④ 其他方法：如網(wǎng)絡(luò)最優(yōu)化方法等。

根據(jù)函數(shù)的解析性質(zhì)，還可以對各種方法作進(jìn)一步分類。例如，如果目標(biāo)函數(shù)和約束條件都是線性的，就形成線性規(guī)劃。線性規(guī)劃有專門的解法，諸如單純形法、解乘數(shù)法、橢球法和卡馬卡法等。當(dāng)目標(biāo)或約束中有一非線性函數(shù)時,就形成非線性規(guī)劃。當(dāng)目標(biāo)是二次的,而約束是線性時，則稱為二次規(guī)劃。二次規(guī)劃的理論和方法都較成熟。如果目標(biāo)函數(shù)具有一些函數(shù)的平方和的形式，則有專門求解平方和問題的優(yōu)化方法。目標(biāo)函數(shù)具有多項式形式時，可形成一類幾何規(guī)劃。

非線性規(guī)劃是20世紀(jì)50年代才開始形成的一門新興學(xué)科。1951年H.W.庫恩和A.W.塔克發(fā)表的關(guān)于最優(yōu)性條件(后來稱為庫恩·塔克條件)的論文是非線性規(guī)劃正式誕生的一個重要標(biāo)志。在50年代還得出了可分離規(guī)劃和二次規(guī)劃的n種解法,它們大都是以G.B.丹齊克提出的解線性規(guī)劃的單純形法為基礎(chǔ)的。50年代末到60年代末出現(xiàn)了許多解非線性規(guī)劃問題的有效的算法，70年代又得到進(jìn)一步的發(fā)展。非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有 廣泛的應(yīng)用，為最優(yōu)設(shè)計提供了有力的工具。

第二次世界大戰(zhàn)前后，由于軍事上的需要和科學(xué)技術(shù)和生產(chǎn)的迅速發(fā)展，許多實際的最優(yōu)化問題已經(jīng)無法用古典方法來解決，這就促進(jìn)了近代最優(yōu)化方法的產(chǎn)生。近代最優(yōu)化方法的形成和發(fā)展過程中最重要的事件有：

• 以蘇聯(lián)康托羅維奇和美國G.B.丹齊克為代表的線性規(guī)劃；
• 以美國庫恩和塔克爾為代表的非線性規(guī)劃；
• 以美國R.貝爾曼為代表的動態(tài)規(guī)劃；
• 以蘇聯(lián)龐特里亞金為代表的極大值原理等。

這些方法后來都形成體系，成為近代很活躍的學(xué)科，對促進(jìn)運(yùn)籌學(xué)、管理科學(xué)、控制論和系統(tǒng)工程等學(xué)科的發(fā)展起了重要作用

對實際規(guī)劃問題作定量分析，必須建立數(shù)學(xué)模型。建立數(shù)學(xué)模型首先要選定適當(dāng)?shù)哪繕?biāo)變量和決策變量，并建立起目標(biāo)變量與決策變量之間的函數(shù)關(guān)系,稱之為目標(biāo)函數(shù)。然后將各種限制條件加以抽象,得出決策變量應(yīng)滿足的一些等式或不等式，稱之為約束條件。非線性規(guī)劃問題的一般數(shù)學(xué)模型可表述為求未知量x1,x2,…,xn,使?jié)M足約束條件：

• gi(x1，…，xn)≥0　i＝1,…,m
• hj(x1，…，xn)＝0　j＝1,…,p

并使目標(biāo)函數(shù)f(x1，…,xn)達(dá)到最小值(或最大值)。其中f，諸gi和諸hj都是定義在n維向量空間Rn的某子集D(定義域)上的實值函數(shù),且至少有一個是非線性函數(shù)。

上述模型可簡記為：

• 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中滿足約束條件的點(diǎn)稱為問題的可行解。全體可行解所成的集合稱為問題的可行集。對于一個可行解x*,如果存在x*的一個鄰域，使目標(biāo)函數(shù)在x*處的值f(x*)優(yōu)于(指不大于或不小于)該鄰域中任何其他可行解處的函數(shù)值，則稱x*為問題的局部最優(yōu)解（簡稱局部解）。如果f(x*)優(yōu)于一切可行解處的目標(biāo)函數(shù)值,則稱x*為問題的整體最優(yōu)解（簡稱整體解）。實用非線性規(guī)劃問題要求整體解，而現(xiàn)有解法大多只是求出局部解。

一維最優(yōu)化方法 　

指尋求一元函數(shù)在某區(qū)間上的最優(yōu)值點(diǎn)的方法。這類方法不僅有實用價值，而且大量多維最優(yōu)化方法都依賴于一系列的一維最優(yōu)化。常用的一維最優(yōu)化方法有黃金分割法、切線法和插值法。

• ① 黃金分割法：又稱0.618法。它適用于單峰函數(shù)。其基本思想是：在初始尋查區(qū)間中設(shè)計一列點(diǎn)，通過逐次比較其函數(shù)值，逐步縮小尋查區(qū)間，以得出近似最優(yōu)值點(diǎn)。
• ② 切線法：又稱牛頓法。它也是針對單峰函數(shù)的。其基本思想是：在一個猜測點(diǎn)附近將目標(biāo)函數(shù)的導(dǎo)函數(shù)線性化，用此線性函數(shù)的零點(diǎn)作為新的猜測點(diǎn)，逐步迭代去逼近最優(yōu)點(diǎn)。
• ③ 插值法：又稱多項式逼近法。其基本思想是用多項式（通常用二次或三次多項式）去擬合目標(biāo)函數(shù)。

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

無約束最優(yōu)化方法 　

指尋求 n元實函數(shù)f在整個n維向量空間Rn上的最優(yōu)值點(diǎn)的方法。這類方法的意義在于：雖然實用規(guī)劃問題大多是有約束的，但許多約束最優(yōu)化方法可將有約束問題轉(zhuǎn)化為若干無約束問題來求解。

無約束最優(yōu)化方法大多是逐次一維搜索的迭代算法。這類迭代算法可分為兩類。一類需要用目標(biāo)函數(shù)的導(dǎo)函數(shù),稱為解析法。另一類不涉及導(dǎo)數(shù)，只用到函數(shù)值,稱為直接法。這些迭代算法的基本思想是：在一個近似點(diǎn)處選定一個有利搜索方向,沿這個方向進(jìn)行一維尋查,得出新的近似點(diǎn)。然后對新點(diǎn)施行同樣手續(xù)，如此反復(fù)迭代，直到滿足預(yù)定的精度要求為止。根據(jù)搜索方向的取法不同，可以有各種算法。屬于解析型的算法有：

• ① 梯度法：又稱最速下降法。這是早期的解析法，收斂速度較慢。
• ② 牛頓法：收斂速度快，但不穩(wěn)定，計算也較困難。
• ③ 共軛梯度法：收斂較快，效果較好。
• ④ 變尺度法：這是一類效率較高的方法。其中達(dá)維登-弗萊徹-鮑威爾變尺度法，簡稱 DFP法，是最常用的方法。

屬于直接型的算法有交替方向法（又稱坐標(biāo)輪換法）、模式搜索法、旋轉(zhuǎn)方向法、鮑威爾共軛方向法和單純形加速法等。

約束最優(yōu)化方法

指前述一般非線性規(guī)劃模型的求解方法。常用的約束最優(yōu)化方法有四種。

• ① 拉格朗日乘子法：它是將原問題轉(zhuǎn)化為求拉格朗日函數(shù)的駐點(diǎn)。
• ② 制約函數(shù)法：又稱系列無約束最小化方法，簡稱SUMT法。它又分兩類，一類叫懲罰函數(shù)法，或稱外點(diǎn)法；另一類叫障礙函數(shù)法，或稱內(nèi)點(diǎn)法。它們都是將原問題轉(zhuǎn)化為一系列無約束問題來求解。
• ③ 可行方向法：這是一類通過逐次選取可行下降方向去逼近最優(yōu)點(diǎn)的迭代算法。如佐坦迪克法、弗蘭克－沃爾夫法、投影梯度法和簡約梯度法都屬于此類算法。
• ④ 近似型算法：這類算法包括序貫線性規(guī)劃法和序貫二次規(guī)劃法。前者將原問題化為一系列線性規(guī)劃問題求解，后者將原問題化為一系列二次規(guī)劃問題求解。

凸規(guī)劃

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

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

將上述不等式中的不等號反向即得凹函數(shù)的定義。所謂凸集，是指具有如下性質(zhì)的集合：連結(jié)集合中任意兩點(diǎn)的直線段上的點(diǎn)全部屬于該集合。對于一般的非線性規(guī)劃問題，局部解不一定是整體解。但凸規(guī)劃的局部解必為整體解，而且凸規(guī)劃的可行集和最優(yōu)解集都是凸集。

二次規(guī)劃

一類特殊的非線性規(guī)劃。它的目標(biāo)函數(shù)是二次函數(shù)，約束條件是線性的。求解二次規(guī)劃的方法很多。較簡便易行的是沃爾夫法。它是依據(jù)庫恩·塔克條件，在線性規(guī)劃單純形法的基礎(chǔ)上加以修正而成的。此外還有萊姆基法、畢爾法、凱勒法等。

幾何規(guī)劃

一類特殊的非線性規(guī)劃。它的目標(biāo)函數(shù)和約束函數(shù)都是正定多項式（或稱正項式）。幾何規(guī)劃本身一般不是凸規(guī)劃，但經(jīng)適當(dāng)變量替換，即可變?yōu)橥挂?guī)劃。幾何規(guī)劃的局部最優(yōu)解必為整體最優(yōu)解。求解幾何規(guī)劃的方法有兩類。一類是通過對偶規(guī)劃去求解；另一類是直接求解原規(guī)劃，這類算法大多建立在根據(jù)幾何不等式將多項式轉(zhuǎn)化為單項式的思想上。

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