最優(yōu)化理論與方法概述課件.ppt

第一章最優(yōu)化問題與凸分析基礎(chǔ),在日常生活中，無論做什么事情，總是有多種方案可供選擇，并且可能出現(xiàn)多種不同的結(jié)果。我們在做這些事情的時候，總是自覺不自覺的選擇一種最優(yōu)方案，以期達到最優(yōu)結(jié)果。這種追求最優(yōu)方案以達到最優(yōu)結(jié)果的學(xué)科就是最優(yōu)化。尋求最優(yōu)方案的方法就是最優(yōu)化方法。這種方法的理論基礎(chǔ)就是最優(yōu)化理論，而凸分析又是最優(yōu)化理論的基礎(chǔ)之一。,1.最優(yōu)化問題,最優(yōu)化問題：求一個一元函數(shù)或多元函數(shù)的極值。在微積分中，我們曾經(jīng)接觸過一些比較簡單的極值問題。下面通過具體例子來看看什么是最優(yōu)化問題。,1.1最優(yōu)化問題的例子,例1對邊長為a的正方形鐵板，在四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最大？解：設(shè)剪去的正方形邊長為x，由題意易知，此問題的數(shù)學(xué)模型為，,配料,每磅配料中的營養(yǎng)含量,鈣,蛋白質(zhì),纖維,每磅成本（元）,石灰石谷物大豆粉,0.3800.000.000.0010.090.020.0020.500.08,0.01640.04630.1250,例2.（混合飼料配合）設(shè)每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)成分如下表所示。試以最低成本確定滿足動物所需營養(yǎng)的最優(yōu)混合飼料。,解:根據(jù)前面介紹的建模要素得出此問題的數(shù)學(xué)模型如下:設(shè)是生產(chǎn)100磅混合飼料所須的石灰石、谷物、大豆粉的量（磅）。,1.2最優(yōu)化問題的數(shù)學(xué)模型,一般形式向量形式其中,目標函數(shù),不等式約束,等式約束,稱滿足所有約束條件的向量為可行解，或可行點，全體可行點的集合稱為可行集，記為。,若是連續(xù)函數(shù)，則是閉集。,在可行集中找一點，使目標函數(shù)在該點取最小值，即滿足：的過程即為最優(yōu)化的求解過程。稱為問題的最優(yōu)點或最優(yōu)解，稱為最優(yōu)值。,定義1：整體（全局）最優(yōu)解：若，對于一切，恒有則稱是最優(yōu)化問題的整體最優(yōu)解。定義2：局部最優(yōu)解：若，存在某鄰域，使得對于一切，恒有則稱是最優(yōu)化問題的局部最優(yōu)解。其中嚴格最優(yōu)解：當，有則稱為問題的嚴格最優(yōu)解。,f(X),局部最優(yōu)解,整體最優(yōu)解,1.3最優(yōu)化問題的分類,與時間的關(guān)系：靜態(tài)問題，動態(tài)問題是否有約束條件：有約束問題，無約束問題函數(shù)類型：線性規(guī)劃，非線性規(guī)劃,2、梯度與Hesse矩陣,2.1等值線二維問題的目標函數(shù)表示三維空間中的曲面。在空間直角坐標系中，平面與曲面的交線在平面上的投影曲線為取不同的值得到不同的投影曲線。每一條投影曲線對應(yīng)一個值，所以我們稱此投影曲線為目標函數(shù)的等值線或等高線。,當常數(shù)取不同的值時，重復(fù)上面的討論，在平面上得到一族曲線等值線.等值線的形狀完全由曲面的形狀所決定；反之，由等高線的形狀也可以推測出曲面的形狀,例在坐標平面上畫出目標函數(shù)的等值線解:因為當目標函數(shù)取常數(shù)時，曲線表示是以原點為圓心，半徑為的圓因此等值線是一族以原點為圓心的同心圓（如圖所示）,2.2n元函數(shù)的可微性與梯度,梯度：多元函數(shù)關(guān)于的一階導(dǎo)數(shù),Hesse矩陣：多元函數(shù)關(guān)于的二階偏導(dǎo)數(shù)矩陣,例：求目標函數(shù)的梯度和Hesse矩陣。解：因為則又因為：故Hesse陣為：,下面幾個公式是今后常用到的：（1），則（2），則(單位陣）（3），Q對稱，則（4）若，其中f：則：,3、多元函數(shù)的Taylor展開,多元函數(shù)Taylor展開式在最優(yōu)化理論中十分重要。許多方法及其收斂性的證明都是從它出發(fā)的。定理：設(shè)具有二階連續(xù)偏導(dǎo)數(shù)。則：其中而01,多元函數(shù)Taylor展開其他形式：,2019/12/15,25,可編輯,凸集和凸函數(shù)在非線性規(guī)劃的理論中具有重要作用，下面給出凸集和凸函數(shù)的一些基本知識。,5、凸集、凸函數(shù)和凸規(guī)劃,例,規(guī)定：歐式空間是凸集，空集是凸集，單點集x為凸集,例:證明集合是凸集。其中，A為mn矩陣，b為m維向量。證明：任取，則所以，,例：給定線性規(guī)劃，其中，若令，則是凸集。,凸集的性質(zhì),有限個凸集的交集仍然是凸集。設(shè)是凸集，則是凸集。,設(shè)是凸集，則是凸集。,凸集的和集仍然是凸集。設(shè)是凸集，則是凸集。,推論：設(shè)是凸集，則也是凸集，其中。,定義3極點（頂點）：設(shè)D是凸集,若D中的點x不能成為D中任何線段上的內(nèi)點，則稱x為凸集D的極點。設(shè)D為凸集，XD,若X不能用X(1)D,X(2)D兩點的一個凸組合表示為X=X(1)+(1-)X(2),其中01，則稱X為D的一個極點。,定義2.凸組合：設(shè)X(1)，X(2)，X(k)是n維歐式空間中的k個點，若存在1,2,k滿足0i1,(i=1,2,k),使X=1X(1)+2X(2)+kX(k)，則稱X為X(1)，X(2)，X(k)的凸組合。,多邊形的頂點是凸集的極點（頂點）。,圓周上的點都是凸集的極點（頂點）。,性質(zhì)1：f(x)是凸集D上的凹函數(shù)的充要條件是-f(x)是D上的凸函數(shù)。,例：證明線性函數(shù)是上的凸函數(shù)。,同理可證線性函數(shù)也是上的凹函數(shù)。,證明：必要性,即,由Taylor公式,令得,設(shè)則,充分性,令,即,所以,同理,定理3（二階條件）：設(shè)D是R中非空開凸集,是定義在D上的二次可微函數(shù),則是凸函數(shù)的充要條件為對xD,0,即Hesse矩陣半正定。,n,證明：必要性,所以,由Taylor公式,令得,因為為開集。,由一階條件,所以,由p的任意性，半正定。,充分性,其中,因為半正定,故為凸函數(shù)。,所以,嚴格凸函數(shù)？,充分性,其中,因為正定，,故為嚴格凸函數(shù)。,所以,例：判斷下列函數(shù)的凹凸性。（1）（2）解：,定義6:凸規(guī)劃設(shè)D為凸集,是定義在D上的凸函數(shù)，則稱規(guī)劃問題為凸規(guī)劃。,例：線性規(guī)劃是凸規(guī)劃。,例：數(shù)學(xué)規(guī)劃易知，與都是凸函數(shù)，所以該規(guī)劃是凸規(guī)劃。,對于一般的規(guī)劃（P），其局部最優(yōu)解不一定是全局最優(yōu)解，其可行集也未必是凸集。但若（P）是凸規(guī)劃，則有下面的結(jié)論。定理4：設(shè)規(guī)劃（P）是凸規(guī)劃，則（1）（P）的可行集R為凸集；（2）（P）的最優(yōu)解集合R*是凸集；（3）（P）的任何局部最優(yōu)解都是全局最優(yōu)解。,定理5：（1)凸規(guī)劃的