【正文】 故稱這一過程為一維搜索。由于其他約束條件均為線性函數(shù)，所以此非線性規(guī)劃是凸規(guī)劃。（2）一階條件證明：取任意兩點、從而，看下式是否成立： 顯然恒成立所以為嚴格的凸函數(shù)。2．性質(zhì)[性質(zhì)1] 設(shè)為定義在凸集上的凸函數(shù)，則對于任意實數(shù)，函數(shù)也是定義在上的凸函數(shù)。由線性代數(shù)知識可知：若矩陣正定，則其各階左對角方陣的行列式大于零；若矩陣負定，則其各階左對角方陣的行列式負、正交替。均有不等式，則稱為在上的嚴格局部極小點，為嚴格局部極小值；（3）對于均有不等式，則稱為在上的全局極小點，為全局極小值；（4）對于均有不等式，則稱為在上的嚴格全局極小點，為嚴格全局極小值。注意：線性規(guī)劃存在最優(yōu)解，最優(yōu)解只能在其可行域的邊緣上（特別能在可行域的頂點上）得到；而非線性規(guī)劃的最優(yōu)解（如果存在）則可能在可行域的任意一點上得到，并非僅局限在邊緣上。解：設(shè)和分別代表商店經(jīng)銷A、B兩種產(chǎn)品的件數(shù)，于是有如下數(shù)學(xué)模型：[例62] 在層次分析（Analytic Hierarchy Process, 簡記為 AHP）中，為了進行多屬性的綜合評價，需要確定每個屬性的相對重要性，即它們各自的權(quán)重。由于人們對實際問題解的精度要求越來越高，非線性規(guī)劃自20世紀70年代以來得到了長足的發(fā)展；目前，已成為運籌學(xué)的一個重要分支，在管理科學(xué)、最優(yōu)設(shè)計、系統(tǒng)控制等許多領(lǐng)域得到了廣泛的應(yīng)用。一般來講，非線性規(guī)劃問題的求解要比線性規(guī)劃問題的求解困難得多；而且也不象線性規(guī)劃問題那樣具有一種通用的求解方法（單純形法）。為此，將各屬性進行兩兩比較可得如下判斷矩陣：其中：是第個屬性與第個屬性的重要性之比。167。22極值點存在的條件[定理1（必要條件）] 設(shè)是上的一個開集，在上有一階連續(xù)偏導(dǎo)數(shù)，且在點取得局部極值，則必有 （61）或 （62）式（62）中，稱為函數(shù)在點處的梯度?，F(xiàn)以代表矩陣中的元素，上述矩陣正定的條件可表示為：；；188。[性質(zhì)2] 設(shè)和為定義在凸集上的兩個凸函數(shù)，則其和=+仍然是定義在上的凸函數(shù)。（3）二階條件證明：的海賽矩陣，因正定，固為嚴格的凸函數(shù)。32下降迭代算法1．基本思想給定一個初始估計解，然后按某種規(guī)則（即算法）找出一個比更好的解，如此遞推即可得到一個解的序列，若這一解的序列有極限，即則稱為最優(yōu)解。1020圖64一維搜索有一個非常重要的性質(zhì)，即在搜索方向上所得最優(yōu)點的梯度和搜索方向正交；這一性質(zhì)可表達成：()則有：其幾何意義如圖64所示。若要繼續(xù)縮小搜索區(qū)間或，只需在區(qū)間內(nèi)再取一點算出其函數(shù)值并與或加以比較即可。為了進行比較，在此給出函數(shù)的精確最優(yōu)解，最優(yōu)值。因此，符合精度要求的近似極小點為，近似極小值為。5%=1b1=a1=a=0b=20圖611a1=a1=a1=b1=因此，符合精度要求的近似極小點為，近似極小值為。此時，若取l （65）就一定能使目標函數(shù)得到改善。2．基本步驟給定一個初始近似點及其精度e，若e，則即為近似極小點；若e，求步長l0并計算=l0。[例69] 試用梯度法求的極大點。由上例可以看出，當(dāng)二次函數(shù)的等值線為同心橢圓時，采用梯度法其搜索路徑呈直角鋸齒狀；最初幾步函數(shù)值變化顯著，但是越接近最優(yōu)點，收斂的速度越不夠理想。在這種情況下，常按下式選取搜索方向： （68）=lk （69）lk：lk） （610）按照這種方式求函數(shù)極小點的方法稱為牛頓法，式（68）所示的搜索方向稱為牛頓方向。變尺度法最早由Davidon于1959年提出，后經(jīng)Fletcher和Powell二人改進，因此變尺度法也被稱為DFP法。[例612] 試用變尺度法（DFP）求的極小值，初始搜索點。對極小化問題來說，除了要使目標函數(shù)每次迭代都有所下降外，還必須要時刻注意解的可行性（某些算法除外），這就給優(yōu)化工作帶來了許多困難。從而，只要方向滿足式（619），即可保證是點的可行方向。若為前者，該規(guī)劃問題實質(zhì)是一個無約束極值問題，必滿足；若為后者，情況就復(fù)雜多了，接下來我們就對這一復(fù)雜情況進行分析。如此即可得到式（623）所示的庫恩塔克條件（KuhnTucker，簡稱KT條件，滿足這一條件的點稱為KT點）。參照圖617，很容易得到此題的最優(yōu)解，最優(yōu)值。因此，問題等價于求解一組滿足附加條件的線性方程組。為了求解出它的極小點或近似極小點，應(yīng)在點的可行下降方向中選取某一方向并確定步長，使（代表可行域）且。下面通過例題來說明利用可行方向法求解非線性規(guī)劃的一般步驟。由于制約函數(shù)需要求解一系列無約束極值問題，故也稱為序列無約束極小化技術(shù)，簡記為SUMT （Sequential Unconstrained Minimization Technique）。當(dāng)時，仍有；當(dāng)時。下面通過例題來展示外點法求解非線性規(guī)劃的基本步驟。根據(jù)上述分析，一個約束非線性規(guī)劃問題，可以轉(zhuǎn)化為下述一系列無約束非線性規(guī)劃問題： ， （629）其中， （630）或， (631）式（630）和式（631）右端第二項稱為障礙項，稱為障礙因子。然后檢驗，若仍然不是內(nèi)點，減小障礙因子繼續(xù)迭代，直到求得一個內(nèi)點為止。6． 用變尺度法求解，初始點，要求近似極小點梯度的模不大于。9． 二次規(guī)劃 （1） 用KT條件求解；（2） 寫出等價的線性規(guī)劃問題并求解。作為極小化的結(jié)果，我們可以得到一個新的內(nèi)點，即。如果從可行域內(nèi)部的某一點出發(fā)，按無約束極小化方法對式（629）進行迭代（注意：在進行一維搜索時要適當(dāng)控制步長，以免迭代跨越的邊界），則隨著的逐步減少（）障礙項所起到的作用也越來越小，因而所求出的的解也逐步逼近原問題的極小解。令，得的解為：取可得如下結(jié)果：：，：：，：常數(shù)0圖618從此結(jié)果可知從的外部逐步逼近的邊界，當(dāng)趨于無窮時，趨于原問題的極小解，見圖618。若，則必定是原問題的極小解。1． 外點法考慮非線性規(guī)劃，為求其最優(yōu)解，構(gòu)造一個函數(shù)，現(xiàn)把當(dāng)作所構(gòu)造函數(shù)的自變量來看待，顯然當(dāng)（代表可行域）時，（）；當(dāng)時。取，從而：令，可得。此種方法稱為可行方向法，其特點是“迭代所采用的搜索方向為可行方向，所產(chǎn)生的迭代點序列始終在可行域的內(nèi)部，目標函數(shù)單調(diào)下降”。[例615] 求解二次規(guī)劃問題這一問題可以用矩陣形式表示為：這就形成了式（626）所需要的全部信息：引入人工變量和得到第一階段的初始單純形表，見表61。二次規(guī)劃是非線性規(guī)劃中較為簡單的一種，許多方面的問題都可以抽象為二次規(guī)劃，而且它和線性規(guī)劃有著非常直接的關(guān)系。庫恩塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點為極值點的必要條件；但一般來講它并不是充分條件，因此滿足這一條件的點并非一定就是極值點。若是極小點，則必與在同一直線上，且方向相反（這里假定和皆不為“0”）；否則，在點處就一定存在可行下降方向，如圖615所示。將目標函數(shù)在處作一階泰勒展開，若方向滿足 （620）則必是點的一個下降方向。61 最優(yōu)性條件現(xiàn)考慮一般形式的非線性規(guī)劃數(shù)學(xué)模型：假設(shè)、和均具有一階連續(xù)偏導(dǎo)數(shù)，是非線性規(guī)劃的一個可行解。在以上的討論中，第一個尺度矩陣為單位矩陣（對稱正定陣），以后的尺度矩陣由式（617）逐步形成。為避免計算二階導(dǎo)數(shù)矩陣及其逆矩陣，設(shè)法構(gòu)造另一個矩陣來逼近二階導(dǎo)數(shù)矩陣的逆矩陣。[例610] 試用牛頓法求的極小值。52牛頓法利用必要條件來確定駐點的一個障礙是在求解聯(lián)立方程時存在困難。2121圖613設(shè)，因有，所以有。一般地，若e，則即為近似極小點；否則求步長 lk并計算=lk。由于=，當(dāng)與反向（即）時，取最小值。5無約束極值問題求解無約束極值問題通常采用迭代法，迭代法可大體分為兩大類：一類要用到函數(shù)的一階導(dǎo)數(shù)和（或）二階導(dǎo)數(shù)，由于此種方法涉及函數(shù)的解析