09非線性規(guī)劃：無約束極值問題.ppt

第四章 非線性規(guī)劃 一 什么是非線性規(guī)劃 目標(biāo)函數(shù)和約束條件中有非線性函數(shù)的規(guī)劃問題 例1某企業(yè)生產(chǎn)一種產(chǎn)品y需要生產(chǎn)資料x1和x2 用經(jīng)濟(jì)計量學(xué)方法根據(jù)統(tǒng)計資料可寫出生產(chǎn)函數(shù)為 但是投入的資源有限 能源總共1O個單位 而每單位生產(chǎn)資料x1要消耗1單位能源 每單位生產(chǎn)資料x2要消耗2單位能源 問 應(yīng)如何安排生產(chǎn)資料使產(chǎn)出最大 解 Max 例2某廠生產(chǎn)兩種產(chǎn)品 第一種產(chǎn)品每件售價30元 第二種產(chǎn)品每件售價450元 設(shè)x1與x2分別為第一 二種產(chǎn)品的數(shù)量 據(jù)統(tǒng)計 生產(chǎn)第一種產(chǎn)品所需工作時間平均為0 5小時 生產(chǎn)第二種產(chǎn)品所需工作時間平均為 2 0 25x2 小時 已知該工廠在這段時間內(nèi)允許的總工作時間為800小時 試確定使總收入最大的生產(chǎn)計劃 解 max 二 非線性規(guī)劃問題的特點(diǎn)局部最優(yōu)點(diǎn)不是全局最優(yōu)點(diǎn) 三 極值問題1 一元函數(shù)y f x 局部極值點(diǎn)存在的必要條件 f x0 0 此時求出的x0為駐點(diǎn) 局部極值點(diǎn)存在的充分條件 a 若f x0 0 則該點(diǎn)x0為局部極小值點(diǎn) 2 多元函數(shù)y f X f x1 x2 xn 在X0附近作泰勒展開 得 極值點(diǎn)存在的必要條件 f x 0 此時求出的x0為駐點(diǎn) 極值點(diǎn)存在的充分條件 二次型ZTHZ稱為半正定 如果對任意Z 0 有ZTHZ 0二次型ZTHZ稱為正定 如果對任意Z 0 有ZTHZ 0 四 凸函數(shù)與凹函數(shù) 1 定義 y f x 是En中某凸集R上的函數(shù) 對 0 1 及 X1 X2 R 且X1 X2若f X1 1 X2 f X1 1 f X2 則f x 為R上的凸函數(shù) 若f X1 1 X2 f X1 1 f X2 則f x 為R上的嚴(yán)格凸函數(shù) 對 0 1 及 X1 X2 R 且X1 X2若f X1 1 X2 f X1 1 f X2 則f x 為R上的凹函數(shù) 若f X1 1 X2 f X1 1 f X2 則f x 為R上的嚴(yán)格凹函數(shù) 2 性質(zhì) fi X 為凸集R上的凸函數(shù) 則對 ki 0 i 1 2 m 有k1f1 X k2f2 X kmfm X 仍為凸函數(shù) 3 凸函數(shù)的判定 f X 定義在凸集R上 若f X 有連續(xù)的二階導(dǎo)數(shù) 則f X 為凸函數(shù) H為半正定 f X 為嚴(yán)格凸函數(shù) H為正定 4 凸函數(shù)的局部極值與全局極值的關(guān)系若目標(biāo)函數(shù)在可行域中為凸函數(shù) 則其極值點(diǎn)為最優(yōu)值點(diǎn) 若目標(biāo)函數(shù)在可行域中為嚴(yán)格凸函數(shù) 則其極值點(diǎn)為唯一最優(yōu)值點(diǎn) 五 凸規(guī)劃 1 定義 非線性規(guī)劃 若f X gi X 為凸函數(shù) 則 p 稱為凸規(guī)劃 2 性質(zhì) p 的可行解集R是凸集 最優(yōu)解集R 也是凸集 p 的任何局部最優(yōu)解均是全局最優(yōu)解 若f X 為嚴(yán)格凸函數(shù)時 其最優(yōu)解必唯一 特例 線性函數(shù)既是凸函數(shù)又是凹函數(shù) 故L P 為凸規(guī)劃 六 尋優(yōu)方法概述 1 非線性規(guī)劃問題分類 無約束條件的非線性規(guī)劃 有約束條件的非線性規(guī)劃 2 尋優(yōu)方法 間接法 解析法 適應(yīng)于目標(biāo)函數(shù)有簡單明確的數(shù)學(xué)表達(dá)式 直接法 搜索法 目標(biāo)函數(shù)復(fù)雜或無明確的數(shù)學(xué)表達(dá)式 a 消去法 對單變量函數(shù)有效 不斷消去部分搜索區(qū)間 逐步縮小極值點(diǎn)存在的范圍 b 爬山法 對多變量函數(shù)有效 根據(jù)已求得的目標(biāo)值 判斷前進(jìn)方向 逐步改善目標(biāo)值 迭代法 無約束極值問題的解法 一 梯度法 最速下降法 選擇負(fù)梯度方向為搜索方向 2 算法步驟 設(shè)求S f X f x1 x2 xn 的極值點(diǎn) 第一步 從給定起點(diǎn)X 0 出發(fā) 第二步 從點(diǎn)X 1 出發(fā) 照此進(jìn)行下去 直至滿足給定的精度 為止 f X k 1 f X k or f X k 例求S f x x12 x22 x1x2 10 x1 4x2 60的極小值點(diǎn) 0 1 解 從點(diǎn)X 1 出發(fā) 照此進(jìn)行下去 直至滿足給定的精度 0 1為止 f X k 1 f X k 0 1或 G k 0 1 計算結(jié)果見下表 缺點(diǎn) 愈接近極值點(diǎn) 步長愈小 目標(biāo)值改進(jìn)愈小 當(dāng)遇到山脊時 會慢慢爬行 在遠(yuǎn)離極點(diǎn)時 收斂速度較快 在極點(diǎn)附近 收斂速度不快 二 共軛梯度法 選擇共軛方向為搜索方向 問題的提出 在極值點(diǎn)附近 如何加快收斂速度 須對函數(shù)在極值點(diǎn)附近的性質(zhì)進(jìn)行研究 設(shè)有n維目標(biāo)函數(shù)S f X f x1 x2 xn 在極值點(diǎn)X 附近展開成泰勒級數(shù) 特別 對二元正定二次函數(shù) 可證明 在極值點(diǎn)附近 其等高線可近似視為同心橢園族 而同心橢園族的任意兩根平行切線的切點(diǎn)連線必通過橢園中心 故 在極值點(diǎn)附近 沿搜索方向P 0 上巳得到一個切點(diǎn)X 1 則只要得出通過極值點(diǎn)的連線方向P 1 在此方向上尋優(yōu) 可一步直達(dá)極值點(diǎn) 而這個連線方向P 1 是上一次搜索方向P 0 的共軛方向 共軛方向的定義 1 定義 設(shè)X Y是n維向量空間En中兩個向量 A為n n對稱正定矩陣 若XTAY 0 則稱向量X與Y對于矩陣A共軛 特例 若A I 得XTY 0 則稱向量X與Y正交 2 幾何意義 共軛方向是通過極值點(diǎn)的方向 尋優(yōu)原理 設(shè)n元函數(shù)S f X f x1 x2 xn 在極值點(diǎn)X 附近可用一個二次函數(shù)逼近 其中H為n n對稱正定矩陣 特別 對二元正定二次函數(shù)S f X f x1 x2 從某點(diǎn)X 0 出發(fā) 以P 0 方向搜索 使f X 達(dá)到極小值點(diǎn)X 1 則 X 1 必為該點(diǎn)處等高線的切點(diǎn) P 0 為切線方向 且點(diǎn)X 1 的梯度方向 f X 1 為該等高線的法線方向 這兩個方向正交 從另一點(diǎn)X 0 出發(fā) 仍以P 0 方向搜索 使f X 達(dá)到另一個極小值點(diǎn)X 2 則 X 2 也必為該點(diǎn)處等高線的切點(diǎn) P 0 為切線方向 且點(diǎn)X 2 的梯度方向 f X 2 為該等高線的法線方向 這兩個方向正交 故 對二元正定二次函數(shù) 只須搜索兩個方向P 0 和P 1 就可達(dá)到極值點(diǎn)X 一般 對n元正定二次函數(shù) 可用不超過n次搜索就可達(dá)到極值點(diǎn)X 而n元非二次函數(shù)在極值點(diǎn)附近可用二次函數(shù)逼近 尋優(yōu)步驟 例求S f x x12 x22 x1x2 10 x1 4x2 60的極小值點(diǎn) 解 對二元二次函數(shù) 只須兩次搜索就可達(dá)到極值點(diǎn)X 一般 對n元二次函數(shù) 可用不超過n次搜索就可達(dá)到極值點(diǎn)X 而n元非二次函數(shù)在極值點(diǎn)附近可用二次函數(shù)逼近 適用于一般目標(biāo)函數(shù)的共軛梯度法 f x 為嚴(yán)格凸函數(shù) 且具有二階連續(xù)偏導(dǎo)數(shù) 4 搜索