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

第二章優(yōu)化設計的數(shù)學基礎

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

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

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

對于可計算的函數(shù)f(x)，給定一個設計點X(k)(x1(k),x2(k),…,xn

(k))，f(x)總有一個定值c與之對應；而當f(x)取定值c時，則有無限多個設計點X(i)(x1(i),x2(i),…,xn(i))（i=1,2,…）與之對應，這些點集構成一個曲面，稱為等值面。

當c取c1,c2,…等值時，就獲得一族曲面族，稱為等值面族。

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

（以二維為例）

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

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

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

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

方向導數(shù)為梯度在方向d上的投影。結論：函數(shù)在某點沿各方向的方向導數(shù)隨

即變化，其最大值在余弦函數(shù)取值為1時，也就是當梯度方向與d方向重合時其值最大。可見，梯度方向就是函數(shù)值變化最快的方向，而梯度的模就是函數(shù)變化率的最大值。梯度方向和切線方向垂直，即梯度方向為等值面的法線方向。三、多元函數(shù)的梯度沿d方向的方向向量即§2.1多元函數(shù)的方向導數(shù)和梯度總結:

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

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

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

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

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

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

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

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

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

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

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

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

三.K-T(Kuhn-Tucker庫恩-塔克)條件它是約束極值點存在條件，用來判斷某個可行點是否為約束極值點?！?.5約束優(yōu)化問題的極值條件

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

K—T條件的圖形說明：

幾何上，x(k)成為約束最優(yōu)點（極小點）x*時，目標函數(shù)的負梯度向量位于m適時約束梯度向量所張成的子空間內?！?.5約束優(yōu)化問題的極值條件

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

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

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

2.有二個適時約束時：

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

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

相反，不符合以上條件：

不能表達成和的