目標函數是非線性函數或約束條件不全是線性等式(或不等式)的一類數學規劃,即在問題
中,若
f(
x)為非線性的,或
Ω不能用用線性(不)等式表出,則此規劃問題就稱為非線性規劃問題。由於問題的這種描述過於廣泛,使得難於得到任何有深刻意義的結果。同時,對於某些特殊類型的
Ω(例如
Ω中點的坐標僅限於取某些整數值),需要特殊的方法去處理因而形成瞭一些獨立的分支。非線性規劃問題一般取如下的形式:
這裡
g(
x)=(
g
1(
x),
g
2(
x),…,
g
m(
x))為一給定的
m維向量實函數,
g(
x)≤0表示它的所有分量皆不大於0,
G為一給定的凸域,在多數情況下,
![](/img3/4757.gif)
。
Ω={
x∈
R
n│
g(
x)≤0,
x∈
G}稱為問題(P)的約束集,
Ω中的點稱為問題的可行解。若
Ω=
R
n,則此規劃稱為無約束規劃,否則稱為帶約束規劃。非線性規劃主要包括以下四個方面的內容。
算法 在f(x) 和Ω給定時,如何求出一個(或多個)點x*∈Ω,使得f(x*)≤f(x)對所有x∈Ω成立,是研究非線性規劃的主要目的。因此,尋求能找出此x*的算法便成為非線性規劃研究的核心。目前尚未出現可以用來解決所有非線性規劃問題的任何算法,算法的研究將是一個長期的課題。一般的算法都是迭代算法。除瞭某些特殊情況之外,求解的過程是一種無限過程,即逐漸逼近於所求的解。為瞭要判斷一個算法所產生的點或所產生的極限點是否為所給問題的解,從而導致尋求解的充分必要條件。
充分必要條件 對一般的約束非線性規劃問題:
設函數
f、
g
i、
h
j都是一階可微函數,
![](/img3/4759.gif)
是一可行解。如果梯度
![](/img3/4760.gif)
和▽
h
j(
![](/img3/4759.gif)
)(
j=1,2,…,
l)線性無關,那麼
![](/img3/4759.gif)
是一個局部極小點的必要條件為:存在
u
1,
u
2,…,
u
m和
v
1,
v
2,…,
v
l,滿足條件
這一組條件稱為庫恩-塔克爾條件,又稱為一階必要條件。它是由H.W.庫恩和A.W.塔克爾於1951年提出的。但是在凸性假設下,它又是充分條件。
庫恩-塔克爾條件對於任意一個局部極小點並不一定成立。約束規格,是指約束條件在局部極小點處具有使庫恩-塔克爾條件成立的性質。例如上述的“梯度▽gi(
![](/img3/4762.gif)
)和▽
h
j(
![](/img3/4762.gif)
)是線性無關(
I∈
I,
j=1,2,…,
l)”,就是一種約束規格。此外,還有其他類型的約束規格。若
g
i,
h
i都是線性函數,則無需任何約束規格,此時庫恩-塔克爾條件對於任意的局部極小點都成立。較之庫恩-塔克爾條件為弱的必要條件是弗裡茨·約翰條件,即對於局部極小點
![](/img3/4759.gif)
存在不全為零的數
u
0、
u
i和
v
j,滿足條件
式中
f、
g
i、
h
j均為一階可微函數。F.約翰在1948年提出這個條件,由於他沒有考慮約束規格,因此他的條件中,主要參數
u
0可能為零而使此條件失效。
對於不可微的凸規劃,有推廣的庫恩-塔克爾條件。在推廣庫恩-塔克爾條件時需要引入次梯度的概念。設f是Rn中的凸函數,若向量ξ滿足
![](/img3/4764.gif)
,
![](/img3/4765.gif)
,則向量
ξ稱為凸函數
f在點
x
0處的一個次梯度。函數
f在
x
0處的次梯度不一定是惟一的。若凸函數
f在
x
0處可微,它在
x
0的次梯度即等於它在
x
0的梯度▽
f(
x
0)。對於不可微的凸規劃
式中
f和
g
i都是凸函數。設
g
i滿足斯雷特約束規格:存在一點
x
0,使得
g
i(
x
0)<0,
i=1,2,…,
m。則可行點
![](/img3/4759.gif)
是凸規劃的極小點的充分必要條件是存在數
u
1,
u
2,…,
u
m和
f在
![](/img3/4767.gif)
處的次梯度
ξ、
g
i在
![](/img3/4762.gif)
處的次梯度
ξ
i,
i=1,2,…,
m,滿足條件
i=1,2,…,
m。
對偶問題 是指根據(P)中的數據建立起來的一個與所給的問題(P)伴隨的問題(P*)。(P)與(P*)之間有如下的關系:
①若(P)是求目標函數f(x)的極小(大)值,則(P*)是求某一目標函數l(у)的極大(小)值;②對於(P)與(P*)的可行解x與у,常有f(x)≥l(у)(f(x)≤l(у));③(P)與(P*)在x*與у*取最優值的充分必要條件是l(у*)=f(x*)。
對於所給定的(P),能滿足上述三種性質的(P*)一般並不是惟一的。因此就存在構造(P*)的不同途徑。目前研究對偶性主要有兩條途徑。
其一是利用拉格朗日乘子。例如線性規劃(P):
![](/img3/4770.gif)
已知其對偶問題(
P
*)是
![](/img3/4772.gif)
記
![](/img3/4773.gif)
是(P)的拉格朗日函數,則(P,P
*)顯然分別等價於以下兩個極值問題
這裡,I(I
*)中之min(max)隻限於就
![](/img3/4776.gif)
(或
![](/img3/4777.gif)
)之
x(或у)來取。
一般,令
![](/img3/4778.gif)
作(P)的拉格朗日函數
![](/img3/4779.gif)
則(P)即等價於
其對偶問題為
更一般言之,設φ(x,у)為定義在X×Y上的實函數,於此,X⊆Rn,Y⊆Rm。作
![](/img3/4783.gif)
記
![](/img3/4785.gif)
則(P):
![](/img3/4786.gif)
與
![](/img3/4787.gif)
分別稱為原規劃和對偶規劃。不難證明,若
X與
Y皆為緊致凸集,
φ(
x,у)在
X×
Y上為連續,且對於固定的у∈
Y(
x∈
X),
φ(
x,
y)為
X(
Y)上的凸(凹)函數,則上述性質①、②、③皆成立。
其二是利用共軛函數。若f(或l)為定義在凸集C⊆Rn(D⊆Rn)上之凸(凹)函數,則稱
![](/img3/4789.gif)
為
f(或
l)的凸(凹)共軛函數。記
![](/img3/4790.gif)
,
![](/img3/4791.gif)
,則(P):
![](/img3/4792.gif)
與
![](/img3/4793.gif)
即互為對偶。實際上,性質①與②是顯然成立的。至於③,則有下面定理:設
C與
D有公共內點,且
![](/img3/4794.gif)
為有限,則存在
![](/img3/4795.gif)
,使得
![](/img3/4796.gif)
。
上述兩條途徑皆得到瞭深入的發展,特別是R.T.洛卡費勒基於增廣拉格朗日函數發展瞭一般的對偶理論。
研究對偶理論的目的主要有三:一是某些實際問題,特別是某些經濟問題,其中所出現的某些現象用對偶理論容易得到解釋;二是可以利用它來幫助求解原問題;三是判定原問題是否有解。例如,有時(P*)比(P)容易得到解決,利用性質③即可得出f(x)的極值;性質②有助於求f(x)的下界。這一點在分枝定界法中常用到。對偶問題的出現是相當普遍的。數學規劃中的許多分支,例如整數規劃,參數規劃、模糊規劃等皆有類似的問題和不同深度的處理。
穩定性 一個數學規劃問題
![](/img3/4797.gif)
已經給定,意即
f(
x)和
Ω已經用某種關系和數據具體表出。所謂穩定性,是指當這些數據作微小變動時問題的解所受到的影響的程度。關於這類問題的研究也稱為靈敏度研究。參數規劃就是這類問題的一個擴充。
形如
![](/img3/4798.gif)
的規劃稱為參數規劃,式中的
![](/img3/4799.gif)
是參數。對於一個給定的
z∈
Z,就得出一個具體的數學規劃。參數規劃的研究目的之一,就是要在
Z中求出一個子集
Z′,使得
Op(
z)對所有的
z∈
Z′具有某種給定的性質。例如要在
Z中求出使得
Ω(
z)非空的
z所成之集,使得
Op(
z)為可解的
z所成之集(即存在
x
*∈
Ω(
z),使得
f(
x
*,
z)=
Op(
z)),以及使得
Op(
z)的解集是具有某種共同給定的結構的
z所成之集,等等。求解參數規劃
Op(
z)(
z∈
Z)是指尋求
Z中的一個子集,對於其中的
z,
Op(
z)成為一個關於某種性質是不變的數學規劃問題。參數規劃的研究內容主要包括以下幾個方面:解的穩定性問題;解對於初始數據的依存關系;初始數據依某種方式具有不確定性的問題(例如,某些量隻知其屬於某一區間、某些量是隨機變量,等等);在一類數學規劃問題中,尋求其中容易解決者;尋求可以用來處理和衡量其他最優化問題的輔助手段;研究某些問題類的一般性質,並發展一般性的方法,等等。
非線性規劃是極值理論的一部分。早在17世紀P.de費馬提出如下的問題:對於平面上給定的三點,要作一點使其與這三點的距離之和為最小。它的對偶問題:過所給三點作一最大的等邊三角形,也早在18世紀初即已提出,並證明瞭這兩問題之間存在對偶關系。
對具有等式約束的非線性規劃的解應滿足的必要條件的研究,可上溯到L.歐拉和J.-L.拉格朗日時代。W.卡魯什在1939年開始瞭對具有不等式約束的非線性規劃的類似問題的研究,但由於他的工作沒有正式發表,同時由於當時計算機尚未出現,數學規劃不能在生產實際中產生影響,這項工作便湮沒無聞。非線性規劃的發展是由於線性規劃的出現而引起的。1951年H.W.庫恩和A.W.塔克爾的研究工作,雖是重復瞭W.卡魯什的結果,但可以看作是非線性規劃理論工作的先驅。這組條件更合適的名稱應該是卡魯什-庫恩-塔克爾條件。
參考書目
M.阿弗裡耳著,李元熹等譯:《非線性規劃──分析與方法》,上海科學技術出版社,上海,1979。(M.Avriel,Nonlinear Programming-Analysis and Methods,Prentice-Hall,Englewood Ciffs,New Jersey,1976.)