第二章優(yōu)化的數(shù)學(xué)基礎(chǔ)

第二章優(yōu)化設(shè)計(jì)的數(shù)學(xué)基礎(chǔ)

§2.1 多元函數(shù)的方向?qū)?shù)和梯度§2.2 多元函數(shù)的泰勒展開§2.3 無約束優(yōu)化問題的極值條件§2.4 凸集、凸函數(shù)與凸規(guī)劃§2.5 等式約束優(yōu)化問題的極值條件

§2.6不等式約束優(yōu)化問題的極值條件

機(jī)械設(shè)計(jì)問題一般是非線性規(guī)劃問題。實(shí)質(zhì)上是多元非線性函數(shù)的極小化問題，因此，機(jī)械優(yōu)化設(shè)計(jì)是建立在多元函數(shù)的極值理論基礎(chǔ)上的。機(jī)械優(yōu)化設(shè)計(jì)問題分為：無約束優(yōu)化約束優(yōu)化無條件極值問題條件極值問題補(bǔ)充：等值（線）面：

對(duì)于可計(jì)算的函數(shù)f(x)，給定一個(gè)設(shè)計(jì)點(diǎn)X(k)(x1(k),x2(k),…,xn

(k))，f(x)總有一個(gè)定值c與之對(duì)應(yīng)；而當(dāng)f(x)取定值c時(shí)，則有無限多個(gè)設(shè)計(jì)點(diǎn)X(i)(x1(i),x2(i),…,xn(i))（i=1,2,…）與之對(duì)應(yīng)，這些點(diǎn)集構(gòu)成一個(gè)曲面，稱為等值面。

當(dāng)c取c1,c2,…等值時(shí)，就獲得一族曲面族，稱為等值面族。

當(dāng)f(x)是二維時(shí)，獲得一族等值線族；當(dāng)f(x)是三維時(shí)，獲得一族等值面族；當(dāng)f(x)大于三維時(shí)，獲得一族超等值面族。等值線的“心”

（以二維為例）

一個(gè)“心”：是單峰函數(shù)的極（?。┲迭c(diǎn)，是全局極（?。┲迭c(diǎn)。沒有“心”：例，線性函數(shù)的等值線是平行的，無“心”，認(rèn)為極值點(diǎn)在無窮遠(yuǎn)處。

多個(gè)“心”：不是單峰函數(shù)，每個(gè)極（?。┲迭c(diǎn)只是局部極（小）值點(diǎn)，必須通過比較各個(gè)極值點(diǎn)和“鞍點(diǎn)”（須正確判別）的值，才能確定極（?。┲迭c(diǎn)。補(bǔ)充：等值（線）面：等值線的形狀：同心圓族、橢圓族，近似橢圓族；等值線的疏密：沿等值線密的方向，函數(shù)值變化快；沿等值線疏的方向，函數(shù)值變化慢。等值線的疏密定性反應(yīng)函數(shù)值變化率。

嚴(yán)重非線性函數(shù)——病態(tài)函數(shù)的等值線族是嚴(yán)重偏心和扭曲、分布疏密嚴(yán)重不一的曲線族。補(bǔ)充：等值（線）面：§2.1多元函數(shù)的方向?qū)?shù)與梯度一、方向?qū)?shù)從多元函數(shù)的微分學(xué)得知，對(duì)于一個(gè)連續(xù)可微函數(shù)f(x)在某一點(diǎn)的一階偏導(dǎo)數(shù)為：，，，…它表示函數(shù)f(x)值在點(diǎn)沿各坐標(biāo)軸方向的變化率。有一個(gè)二維函數(shù)，如圖2-1所示。圖2-1函數(shù)的方向?qū)?shù)

為d的方向角,即與坐標(biāo)軸的夾角§2.1多元函數(shù)的方向?qū)?shù)與梯度其函數(shù)在點(diǎn)沿d方向的方向?qū)?shù)為§2.1多元函數(shù)的方向?qū)?shù)與梯度§2.1多元函數(shù)的方向?qū)?shù)和梯度二維問題中，f(x1,x2)在X(0)點(diǎn)沿方向d的方向?qū)?shù)可以寫為：二.二元函數(shù)梯度§2.1多元函數(shù)的方向?qū)?shù)和梯度其中：是X(0)點(diǎn)的梯度。為d方向的單位向量，

方向?qū)?shù)為梯度在方向d上的投影。結(jié)論：函數(shù)在某點(diǎn)沿各方向的方向?qū)?shù)隨

即變化，其最大值在余弦函數(shù)取值為1時(shí)，也就是當(dāng)梯度方向與d方向重合時(shí)其值最大。可見，梯度方向就是函數(shù)值變化最快的方向，而梯度的模就是函數(shù)變化率的最大值。梯度方向和切線方向垂直，即梯度方向?yàn)榈戎得娴姆ň€方向。三、多元函數(shù)的梯度沿d方向的方向向量即§2.1多元函數(shù)的方向?qū)?shù)和梯度總結(jié):

①梯度是X(0)點(diǎn)處最大的方向?qū)?shù)；②梯度的方向是過點(diǎn)的等值線的法線方向；③梯度是X(0)點(diǎn)處的局部性質(zhì)；④梯度指向函數(shù)變化率最大的方向；⑤正梯度方向是函數(shù)值最速上升的方向，負(fù)梯度方向是函數(shù)值最速下降的方向?！?.1多元函數(shù)的方向?qū)?shù)和梯度圖2-5梯度方向與等值面的關(guān)系§2.2多元函數(shù)的泰勒展開n維函數(shù)f(x)在x(k)點(diǎn)的泰勒展開式:二階近似式：其中：增量

ΔX(k)=[Δx1(k),Δx2(k),…,Δxn(k)]T梯度

一.Hessian矩陣與正定§2.2多元函數(shù)的泰勒展開Hesse矩陣：將函數(shù)進(jìn)行泰勒展開取到二次項(xiàng)時(shí)得到二次函數(shù)形式，優(yōu)化計(jì)算經(jīng)常把目標(biāo)函數(shù)表示成二次函數(shù)以便使問題簡化。Hesse矩陣的特性：是實(shí)對(duì)稱矩陣。矩陣正定的充要條件：主子式det(ait)＞0當(dāng)主子式det(ait)≥0時(shí)，矩陣半正定det(ait)＜0時(shí)，矩陣負(fù)定det(ait)≤0時(shí)，矩陣半負(fù)定Hesse矩陣的正定性：H(x*)正定，是x*為全局極小值點(diǎn)的充分條件；H(x*)半正定,是x*為局部極小值點(diǎn)的充分條件；H(x*)負(fù)定，是x*為全局極大值點(diǎn)的充分條件；H(x*)半負(fù)定,是x*為局部極大值點(diǎn)的充分條件。正定的二次函數(shù)：曲面為橢圓拋物面；等值線族為橢圓曲線族，橢圓中心為極小值點(diǎn)。正定Hesse矩陣§2.2多元函數(shù)的泰勒展開若目標(biāo)函數(shù)f(x)處處存在一階導(dǎo)數(shù)，則極值點(diǎn)的必要條件一階偏導(dǎo)數(shù)等于零，即滿足此條件僅表明該點(diǎn)為駐點(diǎn)，不能肯定為極值點(diǎn)，即使為極值點(diǎn)，也不能判斷為極大點(diǎn)還是極小點(diǎn)，還得給出極值點(diǎn)的充分條件設(shè)目標(biāo)函數(shù)在點(diǎn)至少有二階連續(xù)的偏導(dǎo)數(shù)，則在這一點(diǎn)的泰勒二次近似展開式為：§2.3無約束優(yōu)化問題的極值條件為N維函數(shù)f(x)在點(diǎn)處的Hesse矩陣多元函數(shù)f(x)在處取得極值，則極值的條件為（1）▽F(X*)=0；必要條件（2）Hesse矩陣G(X*)為正定。充分條件為無約束極小點(diǎn)的充分條件是其Hesse矩陣G(X*)為正定的。為無約束優(yōu)化問題的極值條件同學(xué)考慮二元函數(shù)在處取得極值的充分必要條件。各階主子式大于零§2.3無約束優(yōu)化問題的極值條件極值點(diǎn)存在的必要條件：如果函數(shù)f（x）的一階導(dǎo)數(shù)f’（x）存在的話，則欲使x*為極值點(diǎn)的必要條件為：f’（x*）=0極值點(diǎn)存在的的充分條件：f’’（x）<0，則該點(diǎn)為極大值；f’’（x）>0，則改點(diǎn)為極小值。一.一元函數(shù)二.二元函數(shù)極值點(diǎn)存在的必要條件：如果函數(shù)f（x1，x2）在某點(diǎn)處取得極值，必要條件為：極值點(diǎn)存在的的充分條件：如果函數(shù)f（x1，x2）在某點(diǎn)處取得極值，充分條件為在該點(diǎn)處的海塞矩陣正定。例1：例2：第四節(jié)凸集、凸函數(shù)與凸規(guī)劃前面我們根據(jù)函數(shù)極值條件確定了極小點(diǎn)則函數(shù)f(x)在附近的一切x均滿足不等式所以函數(shù)f(x)在處取得局部極小值，稱為局部極小點(diǎn)。而優(yōu)化問題一般是要求目標(biāo)函數(shù)在某一區(qū)域內(nèi)的全局極小點(diǎn)。函數(shù)的局部極小點(diǎn)是不是一定是全局極小點(diǎn)呢？圖2-7下凸的一元函數(shù)一、凸集的線段都全部包含在該集合內(nèi)，就稱該點(diǎn)集為凸集，否則為非凸集。一個(gè)點(diǎn)集（或區(qū)域），如果連接其中任意兩點(diǎn)凸集的性質(zhì)：（1）若A是一個(gè)凸集，b是一個(gè)實(shí)數(shù)，則bA還是凸集。（2）若A和B是凸集，則集合A+B還是凸集。（3）任何一組凸集的交集還是凸集。二、凸函數(shù)函數(shù)f(x）為凸集定義域內(nèi)的函數(shù)，若對(duì)任何的及凸集域內(nèi)的任意兩點(diǎn)存在如下不等式：稱是定義在凸集上的一個(gè)凸函數(shù)。當(dāng)上式中的≤為＜時(shí)，f(x)是嚴(yán)格凸函數(shù)。圖2-10凸函數(shù)的定義§2.4凸集、凸函數(shù)與凸規(guī)劃凸函數(shù)的性質(zhì)：若f(x)是定義在凸集D上的嚴(yán)格凸函數(shù)，則f(x)在D上的一個(gè)極小點(diǎn)，也就是全局最小點(diǎn)。

凸函數(shù)的線性組合仍然為凸函數(shù)。

設(shè)x(1),x(2)為凸函數(shù)f(x)上的兩個(gè)最小點(diǎn)，則其連線上的任意點(diǎn)也都是最小點(diǎn)。三、凸性條件（判別函數(shù)為凸函數(shù)）1.根據(jù)一階導(dǎo)數(shù)（函數(shù)的梯度）來判斷函數(shù)的凸性設(shè)f(x)為定義在凸集R上，且具有連續(xù)的一階導(dǎo)數(shù)的函數(shù)，則f(x)在R上為凸函數(shù)的充要條件是對(duì)凸集R內(nèi)任意不同兩點(diǎn)，不等式恒成立。設(shè)f(x)為定義在凸集R上且具有連續(xù)二階導(dǎo)數(shù)的函數(shù)，則f(x)在R上為凸函數(shù)的充要條件：Hesse矩陣在R上處處半正定。若Hesse矩陣處處正定，則f(x)為嚴(yán)格凸函數(shù)。2.根據(jù)二階導(dǎo)數(shù)（

Hesse矩陣)來判斷函數(shù)的凸性四、凸規(guī)劃對(duì)于約束優(yōu)化問題若都為凸函數(shù)，則此問題為凸規(guī)劃。凸規(guī)劃的性質(zhì)：1.若給定一點(diǎn)，則集合為凸集。2.可行域?yàn)橥辜?.凸規(guī)劃的任何局部最優(yōu)解就是全局最優(yōu)解。當(dāng)f(x)為二元函數(shù)時(shí)，其等值線呈現(xiàn)大圈套小圈形式。§2.4凸集、凸函數(shù)與凸規(guī)劃總結(jié)：第五節(jié)等式約束優(yōu)化問題的極值條件約束優(yōu)化等式約束不等式約束求解這一問題的方法消元法拉格朗日乘子法一、消元法（降維法）以二元函數(shù)為例討論?；舅枷耄焊鶕?jù)等式約束條件將一個(gè)變量x1表示成另一個(gè)變量x2的函數(shù)關(guān)系。然后將這一函數(shù)關(guān)系帶入到目標(biāo)函數(shù)中消去x1，使目標(biāo)函數(shù)變成一元函數(shù)這就將等式約束轉(zhuǎn)化為無約束優(yōu)化問題。對(duì)于n維，有幾個(gè)等式約束就可以消去幾個(gè)變量。

第五節(jié)等式約束優(yōu)化問題的極值條件二、拉格朗日乘子法（升維法）對(duì)于具有L個(gè)等式約束的n維優(yōu)化問題處有第五節(jié)等式約束優(yōu)化問題的極值條件基本思想：通過增加變量將等式約束優(yōu)化問題變成無約束優(yōu)化問題：拉格朗日函數(shù)待定系數(shù)新目標(biāo)函數(shù)的極值的必要條件將原來的目標(biāo)函數(shù)作如下改造：例2-4用拉格朗日乘子法計(jì)算在約束條件的情況下，目標(biāo)函數(shù)的極值點(diǎn)坐標(biāo)。第六節(jié)不等式約束優(yōu)化問題的極值條件在工程中大多數(shù)優(yōu)化問題，可表示為不等式約束條件的優(yōu)化問題。有必要引出非線性優(yōu)化問題的重要理論，不等式約束的多元函數(shù)的極值的必要條件是：庫恩-塔克（Kuhn-Tucker）條件一、一元函數(shù)在給定區(qū)間上的極值條件一元函數(shù)f(x)在給定區(qū)間[a,b]上的極值問題，可以寫成下列具有不等式約束條件的優(yōu)化問題：拉格朗日乘子法，除了可以應(yīng)用于等式的極值問題，還可以用于不等式的極值問題。用拉格朗日乘子法時(shí)，需引入松弛變量，將不等式約束變成等式約束。設(shè)a1和b1為兩個(gè)松弛變量，則上述的不等式約束可寫為：第六節(jié)不等式約束優(yōu)化問題的極值條件則該問題的拉格朗日函數(shù)：根據(jù)拉格朗日乘子法，此問題的極值條件：第六節(jié)不等式約束優(yōu)化問題的極值條件由（起作用約束）（不起作用約束）同樣，來分析起作用何不起作用約束。因此，一元函數(shù)在給定區(qū)間的極值條件，可以表示為：第六節(jié)不等式約束優(yōu)化問題的極值條件多元庫恩-塔克條件分析極值點(diǎn)在區(qū)間的位置，有三種情況第六節(jié)不等式約束優(yōu)化問題的極值條件當(dāng)時(shí)，此時(shí)，則極值條件為：當(dāng)時(shí)，此時(shí)則極值條件為即第六節(jié)不等式約束優(yōu)化問題的極值條件當(dāng)時(shí)，此時(shí)，則極值條件為即第六節(jié)不等式約束優(yōu)化問題的極值條件從以上分析可以看出，對(duì)應(yīng)于不起作用的約束的拉格朗日乘子取零值，因此可以引入起作用約束的下標(biāo)集合。一元函數(shù)在給定區(qū)間的極值條件，可以改寫為：極值條件中只考慮起作用的約束和相應(yīng)的乘子。第六節(jié)不等式約束優(yōu)化問題的極值條件二、庫恩-塔克條件仿照一元函數(shù)給定區(qū)間上極值條件的推導(dǎo)過程，可以得到具有不等式約束多元函數(shù)極值條件：用起作用約束的下標(biāo)集合表示第六節(jié)不等式約束優(yōu)化問題的極值條件用梯度形式表示，可得或庫恩-塔克條件的幾何意義：在約束極小點(diǎn)處，函數(shù)的負(fù)梯度一定能表示成所有起作用約束在該點(diǎn)梯度的非負(fù)線性組合。下面以二維問題為例，說明K-T條件的幾何意義第六節(jié)不等式約束優(yōu)化問題的極值條件從圖中可以看出，處在和角錐之內(nèi)，即線性組合的系數(shù)為正，是在取得極值的必要條件。第六節(jié)不等式約束優(yōu)化問題的極值條件三、庫恩-塔克條件應(yīng)用舉例若給定優(yōu)化問題的數(shù)學(xué)模型為K-T條件第六節(jié)不等式約束優(yōu)化問題的極值條件§2.5約束優(yōu)化問題的極值條件一.優(yōu)化設(shè)計(jì)最優(yōu)解無約束優(yōu)化設(shè)計(jì)問題最優(yōu)解：約束優(yōu)化設(shè)計(jì)問題最優(yōu)解：

不受約束條件限制，使目標(biāo)函數(shù)達(dá)到最小值的一組設(shè)計(jì)變量，即最優(yōu)點(diǎn)x*=[x1*,x2*,…,xn*]和最優(yōu)值f(x*)構(gòu)成無約束問題最優(yōu)解。

滿足約束條件，使目標(biāo)函數(shù)達(dá)到最小值的一組設(shè)計(jì)變量，即最優(yōu)點(diǎn)x*=[x1*,x2*,…,xn*]和最優(yōu)值f(x*)構(gòu)成約束問題最優(yōu)解。二.有約束問題最優(yōu)點(diǎn)的幾種情況有適時(shí)約束目標(biāo)函數(shù)是凸函數(shù),可行域是凸集，則目標(biāo)函數(shù)等值線與適時(shí)約束曲面的切點(diǎn)為最優(yōu)點(diǎn)，而且是全局最優(yōu)點(diǎn)。無適時(shí)約束目標(biāo)函數(shù)是凸函數(shù)，可行域是凸集，則最優(yōu)點(diǎn)是內(nèi)點(diǎn)。相當(dāng)于無約束問題的最優(yōu)點(diǎn)。x(k)為最優(yōu)點(diǎn)x*的條件：必要條件：充分條件：Hesse矩陣H(x(k))是正定矩陣·f(x)·x*·X*§2.5

約束優(yōu)化問題的極值條件

有適時(shí)約束目標(biāo)函數(shù)是非凸函數(shù)（圖a），或可行域是非凸集（圖b）：

則目標(biāo)函數(shù)等值線與適時(shí)約束曲面可能存在多個(gè)切點(diǎn)，是局部極值點(diǎn)，其中只有一個(gè)點(diǎn)是全局最優(yōu)點(diǎn)。二.有約束問題最優(yōu)點(diǎn)的幾種情況pQQp§2.5等式約束優(yōu)化問題的極值條件

三.K-T(Kuhn-Tucker庫恩-塔克)條件它是約束極值點(diǎn)存在條件，用來判斷某個(gè)可行點(diǎn)是否為約束極值點(diǎn)。§2.5約束優(yōu)化問題的極值條件

§2.5約束優(yōu)化問題的極值條件

K—T條件的圖形說明：

幾何上，x(k)成為約束最優(yōu)點(diǎn)（極小點(diǎn)）x*時(shí)，目標(biāo)函數(shù)的負(fù)梯度向量位于m適時(shí)約束梯度向量所張成的子空間內(nèi)。§2.5約束優(yōu)化問題的極值條件

§2.5約束優(yōu)化問題的極值條件

1.有一個(gè)適時(shí)約束時(shí)：從幾何上看，當(dāng)從x(k)點(diǎn)出發(fā)不存在一個(gè)S方向能同時(shí)滿足:與x(k)點(diǎn)目標(biāo)函數(shù)的負(fù)梯度方向成銳角，即沿S方向目標(biāo)函數(shù)值下降；與x(k)點(diǎn)約束函數(shù)的梯度方向成鈍角，即保證S方向上各點(diǎn)在可行域內(nèi)。此時(shí)，獲得最優(yōu)解x(k)為最優(yōu)點(diǎn)x*，f(x(k))為最優(yōu)值f(x*)。§2.5約束優(yōu)化問題的極值條件

從幾何上看，當(dāng)從x(k)點(diǎn)出發(fā)存在一個(gè)S方向能同時(shí)滿足：與x(k)點(diǎn)目標(biāo)函數(shù)的負(fù)梯度方向成銳角，即沿S方向目標(biāo)函數(shù)值下降；與x(k)點(diǎn)約束函數(shù)的梯度方向成鈍角，即保證S方向上各點(diǎn)在可行域內(nèi)。此時(shí)，x(k)不是最優(yōu)點(diǎn)x*。§2.5約束優(yōu)化問題的極值條件

2.有二個(gè)適時(shí)約束時(shí)：

x(k)成為約束最優(yōu)點(diǎn)x*的必要條件為:

幾何上位于和所張的扇形子空間內(nèi)。即不存在一個(gè)S方向能同時(shí)滿足：§2.5約束優(yōu)化問題的極值條件

相反，不符合以上條件：

不能表達(dá)成和的