【正文】 ............................... 19 共軛梯度法 ............................................................................................................................. 23 變尺度法 ................................................................................................................................. 26 結(jié)束語(yǔ) ................................................................................................................................................. 37 參考文獻(xiàn) ............................................................................................................................................. 38 致謝 ..................................................................................................................................................... 39 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 4 第一章 緒論 研究背景與意義追求最優(yōu)化目標(biāo)是人類共同的理想，最優(yōu)化就是從眾多可能方案中選出最佳方案，來(lái)的一門新興的應(yīng)用數(shù)學(xué)分支，以追朔到很古老的極值問(wèn)題，但是直到 1947 年 Dantzig 提出一般線性規(guī)劃問(wèn)題的單純形法之后，、四十年來(lái)隨著現(xiàn)代科技的發(fā)展和電子計(jì)算機(jī)的廣泛應(yīng)用，進(jìn)一步推動(dòng)了最優(yōu)化的迅猛發(fā)展及其理論和算法、管理、軍事國(guó)防、政府決策、交通運(yùn)輸、經(jīng)濟(jì)規(guī)劃等方面.無(wú)約束最優(yōu)化計(jì)算方法不僅本身有著不少實(shí)際應(yīng)用，而且與約束最優(yōu)化計(jì)算方法有著緊密的聯(lián)系：一方面有些處理無(wú)約束最優(yōu)化問(wèn)題的方法能直接推廣應(yīng)用于約束最優(yōu)化問(wèn)題；另一方面，還可以把一些約束最優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約，無(wú)約束最優(yōu)化計(jì)算方法也是處理約束最優(yōu)化問(wèn)題的基本方法.研究求解無(wú)約束最優(yōu)化問(wèn)題的有關(guān)理論和算法，在近幾十年來(lái)迅速發(fā)展并，作為一種有效的最優(yōu)化方法無(wú)約束最優(yōu)化方法在工程設(shè)計(jì)、管理優(yōu)化、系統(tǒng)分析等方面的應(yīng)用日益開拓，愈來(lái)愈受到應(yīng)用部門的重視，所以研究無(wú)約束最優(yōu)化問(wèn)題的計(jì)算方法是意義重大的 問(wèn)題闡述及簡(jiǎn)介 無(wú)約束法指尋求 元實(shí)函數(shù) 在整個(gè) 維向量空間 上的最優(yōu)值點(diǎn)n??fXnnA：雖然實(shí)用規(guī)劃問(wèn)題大多是有約束的，但許多約束最優(yōu)化方法可將有約束問(wèn)題轉(zhuǎn)化為若干無(wú)約束問(wèn)題來(lái)求解. ，只用到函數(shù)值，的導(dǎo)函數(shù)，：在一個(gè)近似點(diǎn)處選定一個(gè)有利搜索方向，沿這個(gè)方向進(jìn)行一維尋查，樣手續(xù)，如此反復(fù)迭代，同，（又稱坐標(biāo)輪換法） 、模式搜索法、旋轉(zhuǎn)方向法、法有：梯度法：，：收斂速度快，但不穩(wěn)定，：收斂較快，安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 5 尺度法：，簡(jiǎn)稱 DFP 法，的算法理論，并對(duì)各個(gè)方法進(jìn)行了舉例分析和 matlab 軟件實(shí)現(xiàn).安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 6 第二章 無(wú)約束問(wèn)題的極值條件. 無(wú)約束極值問(wèn)題考慮非線性規(guī)劃問(wèn)題 （）??nminRf?X其中 是定義在 上的實(shí)函數(shù)，這個(gè)問(wèn)題是求 在 維歐式空間的極小??fX??fXn點(diǎn)，稱為無(wú)約束極值問(wèn)題，這是一個(gè)古典的極值問(wèn)題. 必要條件為研究函數(shù) 的極值條件，先介紹一個(gè)定理??f定理 設(shè)函數(shù) 在點(diǎn) 可微，如果存在方向 ，使 ，則fXd??0f??Xd存在 ，使得對(duì)每個(gè) ，有 .0????0,????ff???X證明 函數(shù) 在 的一階 Taylor 展開式為f?d ?=+dTff??X （）???Tff????????X其中當(dāng) 時(shí)， .0??0?d由于 ，當(dāng) 充分小時(shí)，在（）式中??f??X? ??d+0,Tf??因此存在 ，使得 時(shí)，有0??0,??? ??+0Tf??????????dX從而由（）式得出安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 7 .??ff???Xd利用上述定理可以證明局部極小點(diǎn)的一階必要條件.定理 設(shè)函數(shù) 在點(diǎn) 可微，若 時(shí)局部最小點(diǎn)，則梯度f(wàn) ??=f?X0證明 用反證法，設(shè) ，令方向 ，則有??0f????d=f?X 2=0TTff?Xd根據(jù)定理 ，必存在 ，使得當(dāng) 時(shí)，成立???,??? ?ff??X這與 是局部極小點(diǎn)矛盾X下面，利用函數(shù) 的 Hesse 矩陣，給出局部極小點(diǎn)的二階必要條件??f定理 設(shè)函數(shù) 在點(diǎn) 處二次可微，若 是局部極小點(diǎn)，則梯度XX，并且 Hesse 矩陣 半正定??0f??X??2f?證明 定理 已經(jīng)證明 ，現(xiàn)在只需證明 Hesse 矩陣 半正=0??2f?X定.設(shè) 是任意一個(gè) 維向量，由于 在 處二次可微，且 ，則有dn??fXf?0 ，???221=+Tfff???????ddd經(jīng)移項(xiàng)整理，得到 （）???2221Tfff?????XdX由于 是局部極小點(diǎn)，當(dāng) 充分小時(shí)，必有x ?ff??因此由（）式推得 ，?20Tf?dX安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 8 即 是半正定的.??2f?X 二階充分條件 下面給出局部極小點(diǎn)的二階充分條件 定理 設(shè)函數(shù) 在點(diǎn) 處可微，若梯度 ，且 Hesse 矩陣??fX??f??X0正定，則 是局部極小點(diǎn).??2f?證明 由于 在 的二階 Taylor 展開式為,f?0??f （）????221Tf??????XXX設(shè) 的最小特征值為 ，由于 正定，必有2f?min0??2f ?22minTf??從而由（）式得出 ???22min12ff??????????XX當(dāng) 時(shí)， ，因此存在 的 鄰域 ，當(dāng)?20?????,N?X時(shí) ，即 是 的局部極小點(diǎn)??,N??X??ff?X??f 充要條件前面的幾個(gè)定理分別給出無(wú)約束極值的必要條件和充分條件，這些條件都不是充分必要條件，下，給出全局極小點(diǎn)的充分必要條件定理 設(shè) 是定義在 上的可微凸函數(shù)， ，則 為全局極小點(diǎn)??fXnAn?XA的充分必要條件是梯度 f??0證明 必要性是顯然的，若 是全局極小點(diǎn)，自然是局部極小點(diǎn)，根據(jù)定理，必有 .??fX安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 9 現(xiàn)在證明充分性，設(shè) ，則對(duì)任意的 ，有??f??X0n?XA，由于 是可微的凸函數(shù)，則有??0Tf???X ，????=Tffff???即 是全局極小點(diǎn) 在上述定理中，如果 是嚴(yán)格凸函數(shù)，則全局極小值是唯一的??fX 上面介紹的幾個(gè)極值條件，是針對(duì)極小化問(wèn)題給出的，對(duì)于極大化問(wèn)題，可以給出類似的定理例 利用極值條件解下列問(wèn)題 ??22111mindefxx???X ， 314fx?2fx??令 ，即??f??x0 31420x?? ，解此方程組，得到駐點(diǎn) .??12,0Tx?X再利用極值條件判斷 是否為極小點(diǎn)，由于目標(biāo)函數(shù)的 Hesse 矩陣 ，??2210xf????????由此可知 .22f???????X顯然 為正定矩陣，根據(jù)定理 ，駐點(diǎn) 是局部最小點(diǎn)??2f???1,0T?X安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 10 第三章 求解無(wú)約束最優(yōu)化的幾種主要方法 最速下降法 最速下降法又稱為梯度法，是 1847 年由著名數(shù)學(xué)家 Cauchy 給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的，他在最優(yōu)化方法中占有重要地位. 最速下降法的算法原理最速下降法的搜索法向是目標(biāo)函數(shù)的負(fù)梯度方向，最速下降法從目標(biāo)函數(shù)的負(fù)梯度方向一直前進(jìn)，直到到達(dá)目標(biāo)函數(shù)的最低點(diǎn).已知目標(biāo)函數(shù)在 點(diǎn)的梯度為：()kX??????()()()() nffffxxx? ???? ????? ?X當(dāng)求目標(biāo)函數(shù)的最小點(diǎn)時(shí)，由于函數(shù)沿負(fù)梯度方向下降最快，故在 點(diǎn)的探()kX索方向應(yīng)取該點(diǎn)的負(fù)梯度方向，即 ??()()kkf???SX顯然， 次迭代計(jì)算所得的新點(diǎn)為()kS1???()()(1)()()()kkkkkf??????XS負(fù)梯度僅給出了最優(yōu)化方向，而沒(méi)有給出步長(zhǎng)的大小，所以可能有各種各樣的最速下降的過(guò)程，它們依賴于 的大小.??()kf? 步長(zhǎng) 的兩種取法：??k?一種方法是任意給定一個(gè)初始步長(zhǎng)，使?jié)M足條件： ()()()kkkff???XSX另外一種方法是沿負(fù)梯度方向做一維探索，以求解一維最優(yōu)化問(wèn)題的最優(yōu)步長(zhǎng) ，即對(duì)目標(biāo)函數(shù)極小，以得到最優(yōu)步長(zhǎng)：?安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 11 ()()()0minkkkkff? ?????XSS以此最優(yōu)步長(zhǎng)作為由 點(diǎn)出發(fā)沿該點(diǎn)的負(fù)梯度方向探索的步長(zhǎng) .()k ()k這種方法的迭代計(jì)算的收斂性，可用以下三式中的任一式或二式作為準(zhǔn)則來(lái)進(jìn)行判斷： ??()1()()2)()(13kkkff????????????X 最速下降法算法步驟用最速下降法求無(wú)約束多維極值問(wèn)題 的算法步驟如下：min(),nf?XA（1） 取初始點(diǎn) ，精度 ， 令??0X0??k?（2） 計(jì)算搜索方向 ，其中 表示函數(shù) 在點(diǎn)()()kf???V()kf()fX處的梯度；()k（3） 若 ，則停止計(jì)算；否則，從 出發(fā)，沿 進(jìn)行一維搜索，??()kX()kV即求 ，使得 .此處的一維搜索k?(