第11章非線性規(guī)劃主要內(nèi)容§11-1非線性規(guī)劃基礎(chǔ)§11-2一維搜索§11-3無約束極值問題§11-4有約束極值問題§11-5投資組合決策分析§11-6非線性規(guī)劃的計(jì)算機(jī)求解§11-1非線性規(guī)劃基礎(chǔ)一、非線性規(guī)劃問題的一般模型二、極值問題三、凸函數(shù)四、下降類算法步驟一、非線性規(guī)劃問題的一般模型其中，X=（x1,x2,……,xn）是n維歐氏空間En中的點(diǎn)（向量）

f(X)、gi(X),hi(X)為X的實(shí)函數(shù)，且至少有一個(gè)是非線性函數(shù)。←目標(biāo)函數(shù)←不等式約束 （1）←等式約束例如二、極值問題1、定義定義1：對于非線性規(guī)劃模型（1），稱點(diǎn)集為模型的可行域。定義2：對于非線性規(guī)劃模型（1），設(shè)X*∈Ω,存在正數(shù)δ，使得當(dāng)X∈Ω

且時(shí)，總有f(X)≥f(X*)成立，則稱X*是f在Ω上的一個(gè)局部極小點(diǎn) 若對于一切X∈Ω,,X≠X*，總有f(X)＞f(X*)成立，則稱X*是f在Ω上的一個(gè)嚴(yán)格局部極小點(diǎn)。定義3：對于非線性規(guī)劃模型（1），設(shè)有點(diǎn)X*∈Ω，使得f(X)≥f(X*)對于一切X∈Ω成立，就稱X*是f在Ω上的全局極小點(diǎn)； 若對于一切X∈Ω（X≠X*），總有f(X)＞f(X*)成立，則稱X*是f在Ω上的嚴(yán)格全局極小點(diǎn)。例有三個(gè)局部極小點(diǎn)，但只有中間一個(gè)是全局極小點(diǎn)。二、極值問題2、梯度概念若f(X)具有一階連續(xù)偏導(dǎo)，則稱下式為梯度梯度反映了函數(shù)的一階導(dǎo)數(shù)信息，它是與函數(shù)的等值面正交的，并指向函數(shù)值增大的方向。x0二、極值問題3、極值存在的必要條件

f(X)在X*∈Ω處存在極值的必要條件是或二、極值問題4、海賽矩陣◆若

f(X)二階連續(xù)可微，則稱下述實(shí)對稱矩陣為海賽矩陣◆對于n階矩陣A，若對于任意的n維向量Z≠0

若ZTAZ＞0，則稱該二次型為正定； 若ZTAZ

＜0，則稱該二次型為負(fù)定； 若為“≥”或“≤”關(guān)系，則相應(yīng)地稱為半正定或半負(fù)定。二、極值問題4、海賽矩陣◆二次型ZTAZ正定的充要條件是矩陣H的順序主子式都大于零；二次型負(fù)定的充要條件是矩陣A的順序主子式負(fù)正相間?！艨紤]n階對稱海賽矩陣H，如果二次型ZTHZ為正定、負(fù)定或不定，其對稱矩陣H分別為正定、負(fù)定或不定。◆二元函數(shù)f(X)在駐點(diǎn)X*處取得嚴(yán)格局部極小值（或局部極小值）的充分條件是海賽矩陣H(X*)正定（或半正定），即ZTAZ

＞0一階必要條件二階充分條件一維f(X)f’(X)＝0f’’(X)＞0極小f’’(X)＜0極大多維f(X)H(X)正定或半正定時(shí)極小H(X)負(fù)定或半負(fù)定時(shí)極大二、極值問題例11-1試求下面函數(shù)的極值點(diǎn)和極值解：首先求其駐點(diǎn)，令求駐點(diǎn)解得X*=(1,1,-2)T在此駐點(diǎn)處求其二階偏導(dǎo)得到海賽矩陣：所以H(X*)正定，駐點(diǎn)X*=(1,1,-2)T就是f(X)的極小點(diǎn)，極小值為：二、極值問題1.凸集幾何上，集合內(nèi)任意兩點(diǎn)的連線上的點(diǎn)都在此集合內(nèi)。解析上，對于點(diǎn)集D：X1,X2∈D，則：2.凸函數(shù)幾何上，（弦與曲線的位置）弦在曲線之上，稱之為凸函數(shù)。解析上，任意兩點(diǎn)X1,X2對于函數(shù)f(X)，若則稱之為凸函數(shù)f(x2)f(x1)f(αx1

+(1-α)x2)αf(x1)+(1-α)f(x2)x2x1αx1

+(1-α)x2f(x)x凸函數(shù)二、極值問題凹函數(shù)f(x2)f(x1)f(αx1+(1-α)x2)αf(x1)+(1-α)f(x2)x2x1αx1+(1-α)x2f(x)x三、凸函數(shù)類似的可以定義凹函數(shù)：幾何上，弦在曲線之下；解析上，任意兩點(diǎn)X1,X2對于函數(shù)f(X)有：

三、凸函數(shù)4.凸函數(shù)的判斷（1）根據(jù)定義判斷，弦在曲線上，即弦＞曲（2）根據(jù)定理判斷，曲＞切，即（3）二階條件：在n維歐式空間En中，有一個(gè)凸集Ω，f(X)在其上具有二階的連續(xù)偏導(dǎo)數(shù)，則f(X)為凸函數(shù)的充要條件為其海賽矩陣為正定或半正定。三、凸函數(shù)若f(X)凸，gj(X)凹，則稱之為凸規(guī)劃?？梢宰C明，凸規(guī)劃所對應(yīng)的可行域?yàn)橥辜?，所以，對于凸?guī)劃求到一個(gè)局部極小，即為全局極小。5.凸函數(shù)的極值（1）一般而言，局部極小不等于全局極小；（2）對于凸函數(shù)而言，局部極小就等于全局極小。6.凸規(guī)劃對于一般的數(shù)學(xué)規(guī)劃三、凸函數(shù)四、無約束下降類算法步驟采用逐步迭代算法：步驟：

1）確定初始點(diǎn)X0

2）確定搜索方向Pk 3）確定步長

4）終止準(zhǔn)則§11-2一維搜索一維搜索即求單變量函數(shù)的極值問題，其方法很多，可概括為二類

（1）試探法： Fibonacci法；0.618法（2）插值法： 切線法；拋物線法1.原理①思想：函數(shù)f(t)在[a，b]區(qū)間內(nèi)有極小點(diǎn)t*，逐步縮小該區(qū)間直至[ar,br]，使其寬度滿足精度要求為止。②取點(diǎn)：可以證明，按Fibonacci法取點(diǎn)是最優(yōu)的。③Fibonacci級數(shù)n01234567…Fn1123581321…a

t1

t*t2

btf(t)f(t1)f(t2)一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）2.算法步驟

①根據(jù)精度要求確定取點(diǎn)數(shù)n：

精度要求有：

絕對精度：│bn－an│≤ε

相對精度：（bn－an

）/（b0－a0

）≤δ

根據(jù)給定的精度ε和初始區(qū)間[a,b]，確定取點(diǎn)數(shù)n：一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）（2）算法步驟

②第一次取點(diǎn)，取兩點(diǎn)t1，t1’，按Fn-1/Fn的比例a0b0FnFn-1Fn-2t1t1’Fn-1Fn-2t1點(diǎn)坐標(biāo)為：t1’點(diǎn)坐標(biāo)為：一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）（2）算法步驟

③第二次取點(diǎn)，取一點(diǎn)t2（或t2’）。從t1和t1’中選擇函數(shù)值較大者作為新的邊界點(diǎn)，另外計(jì)算一點(diǎn)t2（或t2’）。a0b0FnFn-1Fn-2t1t1’例如：假設(shè)f(t1)＞f(t1’)，則取a1

＝t1，b1

＝b0，t2

＝t1’，并計(jì)算點(diǎn)t2’坐標(biāo)t2’點(diǎn)坐標(biāo)為：Fn-3Fn-2a1b1t2t2’一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）（2）算法步驟③第二次取點(diǎn)，取一點(diǎn)t2（或t2’）。從t1和t1’中選擇函數(shù)值較大者作為新的邊界點(diǎn)，另外計(jì)算一點(diǎn)t2（或t2’）。a0b0FnFn-1Fn-2t1t1’例如：假設(shè)f(t1)＜f(t1’)，則

取b1

＝t1’，a1

＝t0，t2’＝t1，并計(jì)算點(diǎn)t2坐標(biāo)t2點(diǎn)坐標(biāo)為：Fn-2Fn-3t2t2’a1b1一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）（2）算法步驟④第k次取點(diǎn)，取點(diǎn)tk（或tk’）ak-1bk-1tktk’⑤第n-1次取點(diǎn)，取點(diǎn)tn-1（或tn-1’），取點(diǎn)比例為F1/F2＝1/2，兩者較小者即為所求極小點(diǎn)一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）例11-2

試用分?jǐn)?shù)法求函數(shù)在區(qū)間[-2,2]上近似的極小點(diǎn)和近似極小值，要求誤差不超過0.2。解：不難驗(yàn)證，函數(shù)是區(qū)間[-2,2]上僅有唯一極小點(diǎn)的單峰函數(shù)。極小點(diǎn)為，極小值為，以供下面求解驗(yàn)證。要求絕對誤差查Fibonacci級數(shù)表得n=7，又知道區(qū)間端點(diǎn)為a0=－2，b0=2一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）并取x6=0.4762為近似極小點(diǎn)，近似極小值為f(x6)=0.7506不難驗(yàn)證：即為所求。一、Fibonacci法（斐波那契法或分?jǐn)?shù)法）在Fibonacci搜索法中，若用n個(gè)點(diǎn)來縮短區(qū)間長度時(shí)，其各次縮短率分別為：

二、0.618法（黃金分割法）這些值是在逐步變動(dòng)的。這種取點(diǎn)方式雖然是最優(yōu)的，但每次變動(dòng)的區(qū)間縮短率卻給計(jì)算帶來一定的麻煩。如果每次縮短區(qū)間長度都按固定比值來進(jìn)行，那計(jì)算起來就方便多了。0.618法就是這樣一種方法。Fibonacci法縮短率的極限是0.618，取0.618的不變的縮短率代替Fibonacci的變動(dòng)的縮短率，進(jìn)行等速對稱的搜索，每次的試點(diǎn)均取在區(qū)間的0.382和0.618處，這是比較容易實(shí)現(xiàn)、效果良好的辦法。事實(shí)上，F(xiàn)ibonacci搜索法的縮短率的極限為：取0.618的不變縮短率代替Fibonacci的變動(dòng)縮短率，進(jìn)行等速對稱的搜索，每次的試點(diǎn)均取在區(qū)間的0.382和0.618處，這是個(gè)實(shí)現(xiàn)容易、效果良好的辦法，故又稱黃金分割術(shù)。0.618法的計(jì)算步驟如下：二、0.618法（黃金分割法）給定[a,b]和ε及kK=1:ak=a;bk=b│bk－ak│≤ε？xk+1=bk－0.618(bk－ak)x’k+1=ak+0.618(bk－ak)k=k+1ak+1=xk；bk+1=bkak+1=ak；bk+1=xk+1求f(xk+1)和f(x’k+1)f(xk+1)＞f(x’k+1)yesno0.618法的計(jì)算步驟：設(shè)f(X)是區(qū)間[a，b]上只有一個(gè)極小點(diǎn)的單峰函數(shù)，給定精度ε二、0.618法（黃金分割法）三、切線法（Newton法）分?jǐn)?shù)法和0.618法只是對給定區(qū)間上的部分點(diǎn)的函數(shù)值進(jìn)行了比較，而函數(shù)的一些解析性質(zhì)卻絲毫未被利用。而切線法卻較好的利用了函數(shù)的解析性質(zhì)。假定f(x)是區(qū)間[a,b]上僅有一個(gè)極值點(diǎn)的單峰函數(shù)，且具有三階導(dǎo)數(shù)。如果f(x)在x*處取得極小值，則必有f’(x*)=0。因此，只要求出f’(x)

在區(qū)間[a,b]上的零點(diǎn)即求得極小值。1.是凸函數(shù)，即，為求的零點(diǎn)，在區(qū)間[a，b]內(nèi)靠近b點(diǎn)處選取一點(diǎn)x0，并在點(diǎn)[]處作的切線(如圖)，切線方程為：令得到切線與橫軸的交點(diǎn)x1令得與x軸的交點(diǎn)：如此迭代，直至滿足所要求的精度為止。類似的再在[x1,f’(x1)]處作切線,其方程為：

三、切線法（Newton法）yesno三、切線法（Newton法）切線法的一般計(jì)算步驟如下：2.

是凹函數(shù)，即[注：此種情況的任給初始點(diǎn)x0只能在a端附近，而不能在b端附近，其余的均與上相同。]例11-3求在區(qū)間[1，5]上的極小點(diǎn)，精度要求為解：由可知在區(qū)間[1，5]上有唯一的極小點(diǎn)，不難看出這個(gè)極小點(diǎn)是。在靠近右端值5附近，取一初始值，顯然有：三、切線法（Newton法）現(xiàn)有，故停止迭代。得到近似極小點(diǎn)為3.0001，近似極小值為:三、切線法（Newton法）

這里表示為n維歐氏空間的一個(gè)點(diǎn)，或是一個(gè)n為向量，而f(x)

則表示一個(gè)n元函數(shù)。n元函數(shù)的無約束極值問題的一般表達(dá)式為：n元函數(shù)的極值問題的解法大體上分為兩類：解析法和直接法。§11-3無約束極值問題

這里的方向p(0)

和步長λ0是待定的，為了使函數(shù)f(X)的值在X(0)點(diǎn)沿p(0)方向移動(dòng)步長λ0之后有所下降，將f(X)在點(diǎn)展成泰勒級數(shù)：一、最速下降法（梯度法）此法是1847年由柯西（Cauchy）給出的，它是解析法中最古老的一種，其它方法或是它的變形或是受它的啟發(fā)而得到的，因此，它是最優(yōu)化方法的基礎(chǔ)。算法思想：設(shè)目標(biāo)函數(shù)f(x)二次連續(xù)可微且有極小點(diǎn)x*

，取一初始近似點(diǎn)x(0)

作射線其中：為函數(shù)在點(diǎn)的梯度。則有：為保證即選定的方向p(0)

該與該點(diǎn)的梯度的內(nèi)積要小于0，也即：必須使得：一、最速下降法（梯度法）即函數(shù)f(x)在點(diǎn)x(0)處沿梯度的反方向是函數(shù)值下降最快的方向，所以稱這個(gè)方法為梯度法。由此得到：推而廣之，梯度法的一般公式為：剩下的問題就是如何確定步長λk一、最速下降法（梯度法）下面介紹兩種確定步長λk

的方法。(1)定步長法：每次迭代的λk

都取相同的值λ，不過這時(shí)的搜索方向p(k)應(yīng)取單位向量，即： 此法的優(yōu)點(diǎn)是簡單，而缺點(diǎn)是步長取多大合適沒有明確標(biāo)準(zhǔn)，若取的過小，則收斂太慢；步長過大又很難滿足的要求，甚至造成往復(fù)振蕩而達(dá)不到極小點(diǎn)。一、最速下降法（梯度法）(2)最速下降法：λk不取固定的值，而是與X(k)有關(guān)的一個(gè)變量?？挛鹘o出了一個(gè)最優(yōu)步長梯度法——最速下降法，此法要求從x(k)

點(diǎn)沿方向走下去達(dá)到極小點(diǎn)，由此確定步長λk

：即：

也就是說，要沿著負(fù)梯度方向進(jìn)行一維搜索，確定出使f(X)達(dá)到該方向極小化的λk

。此方法固然最優(yōu)，但也太繁雜。為此，我們還可以求出一個(gè)近似的最優(yōu)步長，將此函數(shù)展成泰勒級數(shù)：一、最速下降法（梯度法）對上式求導(dǎo)并令其等于零：得到近似最優(yōu)步長：一、最速下降法（梯度法）最速下降法的算法流程圖一、最速下降法（梯度法）3.優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，搜索方向很容易找，且理論上證明是收斂的。缺點(diǎn)：收斂慢。(越靠近極小點(diǎn)時(shí)收斂越慢，而且在靠近極小點(diǎn)處收斂的軌跡呈鋸齒狀)一、最速下降法（梯度法）1.

正定二次函數(shù)（1）二次函數(shù)一般形式為：四、共軛梯度法（2）其中A是一個(gè)對稱方陣，如果A正定，則此二次函數(shù)為正定二次函數(shù)。（3）討論二次函數(shù)的原因 除了一次函數(shù)之外，二次函數(shù)是最簡單的函數(shù)；等值面是橢球面；一般函數(shù)在極小點(diǎn)附近，其形態(tài)近似于一個(gè)二次正定函數(shù)。2.共軛方向 設(shè)A為n×n對稱正定陣，X和Y是n維歐氏空間En中的兩個(gè)向量，若有XTAY=0，則稱X和Y關(guān)于A共軛，當(dāng)A=I，則X與Y正交。 設(shè)A為n×n對稱正定陣，若向量組P1，P2

，…，Pn∈En中任意兩個(gè)向量關(guān)于A共軛，即滿足條件PiTAPj=0(i≠j,i,j=1,2,…,n)，則稱該向量組為A共軛。2.共軛方向

(1)正交：對于n為歐氏空間E(n)中的兩個(gè)非零 向量X和Y，如果有：XTY=0，則稱X和Y是正交的。(2)共軛：假定A是對稱正定矩陣，如果向量X和AY正交， 即：XTAY=0，則稱x和y關(guān)于A共軛。

顯然當(dāng)A為單位矩陣時(shí)，(2)時(shí)就變?yōu)?1)式，所以A共軛概念實(shí)際上是通常正交概念的推廣。不過要注意的是A共軛與通常正交之間并無任何聯(lián)系。也就是說，兩個(gè)向量關(guān)于A是共軛的，這兩個(gè)向量可能正交，也可能不正交。四、共軛梯度法例關(guān)于A共軛。四、共軛梯度法定義：對于n階對稱正定矩陣A，如果非零向量組滿足條件：則稱該向量組為關(guān)于A共軛的向量組。定理：設(shè)A為n階對稱正定矩陣，為A共軛的非零向量組，則該向量組一定是線性無關(guān)的。[證明略]注意：在n維歐氏空間中，任意n個(gè)線性無關(guān)的向量組都可以構(gòu)成n維向量空間的一個(gè)基（即任何一個(gè)向量都可以由n個(gè)基向量線性表示）。所以，如上所述的n個(gè)關(guān)于A共軛的非零向量組同樣構(gòu)成n維向量空間的一個(gè)基。四、共軛梯度法3．正定二次函數(shù)的共軛梯度法求極小值其中：A是n階正定矩陣，x、b是n維向量，c是常數(shù)。設(shè)為極小點(diǎn)，為任意給定的初始點(diǎn)，如果為A共軛向量組，它們構(gòu)成n維向量空間的一個(gè)基，所以，向量可以唯一的表示為這組共軛向量的線性組合：四、共軛梯度法3．正定二次函數(shù)的共軛梯度法求極小值顯而易見，只要能求出系數(shù)便可以求出極小點(diǎn)X*。為此，將(1)式兩邊都左乘以得到：另一方面，因X*是二次函數(shù)的極小點(diǎn)，應(yīng)有：代入(2)式得：X四、共軛梯度法需要指出的是，這樣求得的ak實(shí)際上是二次函數(shù)f(X)從X(k)出發(fā)沿方向p(k)

進(jìn)行一維搜索的的最佳步長。四、共軛梯度法下面介紹兩種確定共軛方向的方法(1)單位向量法設(shè)給定初始點(diǎn)，并取第一個(gè)方向，求得下一點(diǎn)：

其中，λ0為最佳步長。再取第二個(gè)方向：其中，且，所以，將上式兩邊左乘得：四、共軛梯度法假定已經(jīng)求出X(k)

以及k個(gè)A共軛方向，為求X(k+1)

需求：利用(j=0,1,2,…,k-1)的共軛性，在上面等式的兩邊同時(shí)左乘得：這里ek

是單位向量

，將αj

依次代入上式便求得p(k)

，由此便求得：四、共軛梯度法(2)梯度法（Gram-Schnid法）滿足：四、共軛梯度法四、共軛梯度法§11-4有約束極值一般非線性規(guī)劃模型：解決上述問題的思路可以分為三類：一、最優(yōu)性條件1.起作用約束和可行下降方向：起作用約束：選定點(diǎn)X0滿足直觀上講，起作用約束落在可行域的邊界上。等式約束都是起作用約束；對于大于等于約束在可行點(diǎn)X0滿足的約束為起作用約束，否則為不起作用約束。則X0點(diǎn)可行，如果有：則對于叫做起作用約束。起作用約束示意圖可行方向D：對于n維空間的點(diǎn)，使得當(dāng)時(shí)，可行下降方向D：可行方向示意圖一、最優(yōu)性條件2.一階必要條件（Kuhn－Tucker條件，簡稱K－T條件）正則點(diǎn)：X*是可行域內(nèi)的一點(diǎn)，若在該點(diǎn)處起作用約束的梯度線性無關(guān)，則X*點(diǎn)為正則點(diǎn)。K－T條件：若X*是極小點(diǎn)，且是正則點(diǎn)，則定存在常數(shù)向量滿足：即目標(biāo)函數(shù)在X*點(diǎn)的梯度等于起作用約束在該點(diǎn)梯度的線性組合。一、最優(yōu)性條件3.二階充分條件若X*是滿K－T條件的點(diǎn)，且對于滿足：的一切非零向量Y有：則X*是最優(yōu)點(diǎn)。一、最優(yōu)性條件例11-8試驗(yàn)證h(x)與g1(x)=0的交點(diǎn)A是否為最小點(diǎn)。一、最優(yōu)性條件解：A點(diǎn)的坐標(biāo)為：(1)是否滿足K-T條件①X*∈R，可行②正則點(diǎn)：，兩者線性無關(guān)。由μjgj(X*)=0,得μ2=0一、最優(yōu)性條件(2)是否滿足二階充分條件：對于一切Y成立，所以滿足二階充分條件，A點(diǎn)是最小點(diǎn)。（注：若不給出點(diǎn)，則要用K-T條件同時(shí)找λ、μ和X*。）一、最優(yōu)性條件4.二次規(guī)劃(1)問題形式：目標(biāo)函數(shù)二次，約束函數(shù)線性稱此規(guī)劃為二次規(guī)劃。二次規(guī)劃是除線性規(guī)劃之外的比較簡單的一類數(shù)學(xué)規(guī)劃。一、最優(yōu)性條件(2)求解極值（利用K-T條件轉(zhuǎn)化為線性規(guī)劃）上述二次規(guī)劃中目標(biāo)函數(shù)及約束的梯度如下：K-T條件：注意m+n個(gè)乘子：一、最優(yōu)性條件給（1）式中加入人工變量zj,給原約束加入松弛變量xn+i，構(gòu)造出如下的線性規(guī)劃模型：（注：zj≥0，且其前符號與cj同號，此舉為了形成初始可行基）一、最優(yōu)性條件解此線性規(guī)劃得到最優(yōu)解：其中：即為原二次規(guī)劃問題的最優(yōu)解但應(yīng)注意，所得解要滿足K-T條件的第二條：；以及。一、最優(yōu)性條件二、可行方向法可行方向法是一種搜索法，它是通過在可行域內(nèi)直接搜索最優(yōu)解的辦法來求解。現(xiàn)在的問題是：⑴如何尋求下降可行方向D(k)；⑵沿下降可行方向D(k)行進(jìn)的步長λk如何選取。根據(jù)本節(jié)第一個(gè)問題中所述的可行下降方向，可行下降方向D應(yīng)滿足：容易看出這個(gè)不等式組等價(jià)于存在數(shù)β＜0，使得：為了求出x(k)處的可行下降方向，只需求出滿足上述不等式組的方向D及數(shù)β。為使步長盡可能大，β則應(yīng)盡可能?。é拢?）。因此構(gòu)造如下線性規(guī)劃模型：其中，限定方向D的各個(gè)分量|dj|≤1，為的是該線性規(guī)劃有有限最優(yōu)解；確定搜索方向D時(shí)，只需知道其各個(gè)分量的相對大小即可。二、可行方向法可行方向法的迭代過程：給定x(0)及ε1,ε2＞0；置k=0確定下標(biāo)集合：yesx(k)為最有解，停止yesnono得解：noyesk=k+1得到：λk二、可行方向法投資組合決策問題投資組合決策是非線性規(guī)劃的重要應(yīng)用領(lǐng)域之一。作為大公司的高層管理者的首要任務(wù)之一就是如何最有效地運(yùn)用其巨額資金。一般而言，在風(fēng)險(xiǎn)投資中管理者會(huì)從兩個(gè)基本目標(biāo)考慮：投資組合的收益值最大；投資組合的風(fēng)險(xiǎn)最小。一般情況下此兩目標(biāo)是相互沖突的，即增大期望收益就要冒較大的風(fēng)險(xiǎn)；要減小投資的風(fēng)險(xiǎn)性就會(huì)減小期望收益。因此，管理者的目標(biāo)是：在獲得一定的期望收益前提下盡可能減小風(fēng)險(xiǎn)；或在一定的風(fēng)險(xiǎn)率條件下使期望收益值最大。馬拉松公司的最佳投資組合決策問題分析：§11-5投資組合決策分析§11-5投資組合決策分析馬拉松公司的投資方向組合是：愛德文特、GSS、數(shù)字設(shè)備馬拉松投資三個(gè)公司的股票資產(chǎn)歷史統(tǒng)計(jì)信息為§11-5投資組合決策分析現(xiàn)在假定馬拉松公司的投資組合目標(biāo)為：期望收益率為11.0%，在此基礎(chǔ)上使投資組合風(fēng)險(xiǎn)最小——投資組合期望收益的標(biāo)準(zhǔn)差最小。因此，得到規(guī)劃模型1為：投資組合目標(biāo)的另一種設(shè)定：希望組合投資的風(fēng)險(xiǎn)率不超過3.1%，在此基礎(chǔ)上使期望收益值最大。則規(guī)劃模型2為：§11-5投資組合決策分析§11-6非線性規(guī)劃的計(jì)算機(jī)求解正如前面所述，非線性規(guī)劃的求解一般是比較困難的，通常利用函數(shù)的微分性質(zhì)進(jìn)行近似逼近而得到近似最優(yōu)解。由于非線性函數(shù)結(jié)構(gòu)上的多樣性，使得大多數(shù)算法和計(jì)算機(jī)軟件只能求的規(guī)劃模型的局部最優(yōu)解。了解這一點(diǎn)是非常重要的。有許多規(guī)劃求解軟件都可以求解非線性規(guī)劃，但隨其起作用程度的不同而有很大的差別。通常用于教學(xué)或演示的軟件只能求解很小的非線性規(guī)劃模型（幾個(gè)變量幾個(gè)約束），而能夠求解較大模型的專業(yè)的軟件包通常是很昂貴的。Excel電子制表軟件中的規(guī)劃求解