最優(yōu)化方法第二次

1、第二次自學(xué)、討論內(nèi)容第二次自學(xué)、討論內(nèi)容 1. 極值點的一階必要條件、二階充分條件及其幾何意義。 2. 最優(yōu)化為何不用直接法，而常采用迭代法？ 3. 迭代法的基本思想及迭代法的四個關(guān)鍵問題。 4. 下降算法的基本思想與迭代格式。 5. 下降算法中最關(guān)鍵的問題是什么？ 6. 如何理解迭代法的停止準則或最優(yōu)性條件？在編程時如何具體實現(xiàn)？ 7. 迭代方向 滿足什么條件時， 才是下降方向？試證明你的結(jié)論。 (提示:可用Taylor展式)kpkp 二、最優(yōu)化的基本概念二、最優(yōu)化的基本概念 1. 優(yōu)化問題的一般形式優(yōu)化問題的一般形式 最優(yōu)化問題的數(shù)學(xué)模型為 稱為決策變量， 稱為目標(biāo)函數(shù)， 稱為約束條件。

2、滿足約束條件的解稱為可行解，否則稱為不可行解；可行解的集合稱為可行集。能 1212min,. .,01,2,niinf xf x xxst gxgx xxim12,nx xx12,nf x xx12,0ingx xx使目標(biāo)函數(shù)達到最優(yōu)值的可行解稱為(全局) 最優(yōu)解，能使目標(biāo)函數(shù)達到局部最優(yōu)值的可行解稱為局部最優(yōu)解。對大多數(shù)優(yōu)化問題，求全局最優(yōu)解是很困難的，所以很多優(yōu)化軟件往往只能求到局部最優(yōu)解。 2. 優(yōu)化問題的基本類型優(yōu)化問題的基本類型 優(yōu)化問題可以從不同的角度進行分類。 不包含約束條件的最優(yōu)化問題稱為 “ 無約束優(yōu)化”，否則稱為 “約束優(yōu)化”。 通常，人們按照可行集的性質(zhì)對優(yōu)化問題分類：若

3、可行集中的元素是離散的，則稱之為“組合優(yōu)化”或“離散優(yōu)化”，如整數(shù)規(guī)劃、0-1規(guī)劃等。若可行集是有限維空間中的一個連續(xù)子集，則稱之為“數(shù)學(xué)規(guī)劃”；此時，若目標(biāo)函數(shù)和約束函數(shù)均為線性，則稱之為“線性規(guī)劃”，否則稱之為“非線性規(guī)劃”。如果可行集中的元素是依賴時間的決策序列，則歸結(jié)為“動態(tài)規(guī)劃”。如果可行集是無窮維空間中的連續(xù)子集，則歸結(jié)為“最優(yōu)控制”。 此外，根據(jù)決策變量是否具有不確定性,可以把優(yōu)化問題分成確定性規(guī)劃、不確定性規(guī)劃（如隨機規(guī)劃、模糊規(guī)劃等）。根據(jù)需要優(yōu)化目標(biāo)的數(shù)目，可以把優(yōu)化問題分成單目標(biāo)優(yōu)化、多目標(biāo)優(yōu)化。 線性規(guī)劃與非線性規(guī)劃是最優(yōu)化方法中最基本、最重要的兩類問題。 一般來說，各

4、優(yōu)化分支有其相應(yīng)的應(yīng)用領(lǐng)域。線性規(guī)劃、網(wǎng)絡(luò)規(guī)劃、動態(tài)規(guī)劃通常用于管理與決策科學(xué)；最優(yōu)控制往往用于控制工程；非線性規(guī)劃更多地用于工程優(yōu)化設(shè)計。 3. 最優(yōu)性條件最優(yōu)性條件 由微積分知識可得出下列最優(yōu)性條件： 定理定理1.3（一階必要條件） 設(shè) 可微，若 為 的一個極小點，則 。 本定理的幾何意義是，函數(shù)在 處取極小值的必要條件是該函數(shù)曲面在 處的切平面是水平的； 梯度為零的點可能是極小或極大點，也可能是鞍點即既非極小也非極大的點。*X*X XfnRX * Xf* 0fX 定理定理1.4（二階充分條件） 設(shè) 二階連續(xù)可微，若 ，且 處的二階導(dǎo)數(shù)矩陣 正定，則 為極小點。 本定理的幾何意義是， 為極

5、小點的充分條件是函數(shù)曲面在 處有水平切平面且向上彎曲。 Xf0*Xf*2Xf*X*X*X*X 定理定理1.5（凸函數(shù)的最優(yōu)性條件） 設(shè) 為二階可微的凸函數(shù)，且 ,則 為全局極小點。 Xf0*Xf*X 4. 算法結(jié)構(gòu)算法結(jié)構(gòu) 根據(jù)最優(yōu)條件，從理論上講，可以先解非線性方程組 ，然后再判定其解的二階導(dǎo)數(shù)矩陣 是否正定，即可求出函數(shù)的最優(yōu)解。但由于解非線性方程組和判定矩陣是否正定是極為復(fù)雜和困難的，其難度甚至已超過優(yōu)化問題本身。因此，上述想法在實際上是不可行的。 0Xf Xf2 求解最優(yōu)化問題常用的方法是迭代法。 迭代法的基本思想是：從最優(yōu)點的一個初始值 出發(fā)，按一定迭代法則產(chǎn)生點序列 ，使目標(biāo)函數(shù)值

6、 逐步減小。當(dāng) 是有限點列時，其最后一點即為最優(yōu)解；當(dāng) 是無窮點列時，其極限點即為最優(yōu)解。 0 x (1,2,)kxk kxf kx kx 對于迭代法有下列四個問題： 如何由 產(chǎn)生 ，即迭代格式或算法結(jié)構(gòu)； 迭代何時中止，即停止準則或最優(yōu)性條件； 迭代產(chǎn)生的序列是否收斂于最優(yōu)解 ，即收斂性問題； 收斂算法的收斂速度問題。 kx1kx*x 最優(yōu)化中多采用逐步下降算法，其基本思想是：根據(jù)當(dāng)前解選擇一個適當(dāng)?shù)南陆捣较?，沿此方向下降到一個合適位置從而得到新解，然后判斷新解是否為最優(yōu)解；若是，則停止，否則重復(fù)上述過程。經(jīng)過有限次迭代后，在一定條件下即可得出近似最優(yōu)解。 下降算法的迭代格式為： ，其中 是

7、第 次迭代點， 是第 次迭代方向， kkkkptXX1kXkkpk 是第 次迭代步長。 顯然，用迭代法求解無約束最優(yōu)化問題的關(guān)鍵是：構(gòu)造迭代方向 和確定迭代步長 。確定迭代步長 可通過一維搜索方法進行，而選擇不同的方法構(gòu)造迭代方向 ，將會得到不同的算法。 )0(kkttkpktktkpk 5. 收斂性與收斂速度收斂性與收斂速度 一個算法是否收斂，往往同初始點 的選取有關(guān)。如果只有當(dāng) 充分接近最優(yōu)解 時，由算法產(chǎn)生的點列才收斂于 ，則該算法稱為具有局部收斂性的算法。如果對于任意的初始點 ，由算法產(chǎn)生的點列都收斂于最優(yōu)解 ，則這個算法稱為具有全局收斂性的算法。由于一般情況下最優(yōu)解 是未知的，所以嚴格來說只有具有0 x0 x*x*x0 x*x*x全局收斂性的算法才是有實用意義的。令人遺憾的是大多數(shù)經(jīng)典優(yōu)化算法都是局部優(yōu)化算法，全局優(yōu)化的理論和算法遠不及局部優(yōu)化那么成熟，至今為止還沒有得到類似于局部極小點那樣的解析條件，即沒有肯定的方法能判