工程優(yōu)化第2章-4

課件下載郵箱郵箱名：

xdgongchengyouhua@126.com(xd+工程優(yōu)化的小寫(xiě)全拼)密碼：xidian123多元函數(shù)的梯度及其Hesse矩陣等高線二次函數(shù)多元函數(shù)的極值及其判別條件凸集、凸函數(shù)、凸規(guī)劃幾個(gè)重要的不等式第2章基礎(chǔ)知識(shí)

由一元函數(shù)的幾何圖形知：f(x)是凸函數(shù)，任意給定曲線上兩點(diǎn)A，B，則弦AB在與弧AB之上，用數(shù)學(xué)式子表示：

凸函數(shù)弦AB的方程：令則上式可寫(xiě)為：所以：

定義（凸函數(shù)）:

設(shè)集合DRn為凸集，函數(shù)f:DR,若

α(0,1)，均有則稱f(x)為凸集D上的凸函數(shù)。若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱f(x)為凸集D上的嚴(yán)格凸函數(shù)。當(dāng)-f(x)為凸函數(shù)(嚴(yán)格凸函數(shù))時(shí)，則稱f(x)為凹函數(shù)

(嚴(yán)格凹函數(shù))。嚴(yán)格凸函數(shù)凸函數(shù)嚴(yán)格凹函數(shù)凸函數(shù)----推廣到多元函數(shù)例：設(shè)1)若A半正定，則在上是凸函數(shù)；2)若A正定，則在上是嚴(yán)格凸函數(shù)。證明:

凸函數(shù)----推廣到多元函數(shù)性質(zhì)2：設(shè)f1,f2

是凸集D上的凸函數(shù)，設(shè)a,b>0,則af1+bf2

是凸函數(shù)；f(x)=max{f1(x),f2

(x)}是凸函數(shù)。思考：af1

-bf2

是否是凸函數(shù)？

g(x)=min{f1(x),f2

(x)}是否是凸函數(shù)？凸函數(shù)的性質(zhì)性質(zhì)1：

f(x)

為凸集S上的凸函數(shù)S上任意有限點(diǎn)的凸組合的函數(shù)值不大于各點(diǎn)函數(shù)值的凸組合。

證明參見(jiàn)文中定理2.10的證明。P39作業(yè)定理(一階條件):

設(shè)D

Rn為非空凸集，函數(shù)f:DR

在D上可微，則

(1)f在D上為凸函數(shù)

恒有

(1)(2)

f在D上為嚴(yán)格凸函數(shù)

恒有

(2)

證明:見(jiàn)書(shū)中定理2.11(P27)凸函數(shù)的判定定理定理5（二階條件）:

設(shè)D

Rn為含有內(nèi)點(diǎn)的非空凸集，函數(shù)f:DR在D上二次可微，則

a)f在D上為凸函數(shù)xD，2f(x)

半正定；

b)若xD，2f(x)

正定，則f在D上為嚴(yán)格凸函數(shù)。證明:見(jiàn)書(shū)中定理2.12（P28）由一階條件和多元函數(shù)的泰勒展開(kāi)式可證?；貞洠阂粋€(gè)矩陣半正定充要條件是所有主子式非負(fù)；一個(gè)矩陣正定充要條件是所有順序主子式為正。凸函數(shù)的判定定理例：設(shè)二次函數(shù)(1)：若為半定矩陣，在中為凸函數(shù)；(2)：若為正定矩陣，在中為嚴(yán)格凸函數(shù)。例：判斷f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函數(shù)？凸函數(shù)的判定定理的順序主子式都是正的，所以正定，因此f(x)在凸集D上是嚴(yán)格凸函數(shù)。由于故證明為凸函數(shù)。也是凸函數(shù)。根據(jù)性質(zhì)2，為凸函數(shù)。

看下述各式是否成立：證明：首先用定義證明是凸函數(shù)，即對(duì)任意和例:

試證明為凹函數(shù)。或即顯然，不管和

取什么值，總有為凹函數(shù)。

因此

從而用同樣的方法可以證明用一階條件證明只需證任意選取兩點(diǎn)或或或不管a1、a2、b1、b2取什么值，上式均成立，從而得證。是凹函數(shù)，

要證

例:

試證明為凹函數(shù)。其Hesse矩陣處處負(fù)定，故為(嚴(yán)格)凹函數(shù)。

下面用二階條件證明:由于例:

試證明為凹函數(shù)。定義（凸規(guī)劃）:

考慮如下非線性規(guī)劃當(dāng)都是凸函數(shù)時(shí),稱規(guī)劃為凸規(guī)劃凸規(guī)劃性質(zhì)1:

設(shè)(1)為凸規(guī)劃，則

i)(1)的可行集是凸集；

ii)(1)的最優(yōu)解集是凸集；

iii)(1)的任何局部極小點(diǎn)都是全局極小點(diǎn)。

證明：見(jiàn)書(shū)中定理2.13.性質(zhì)2:

設(shè)(1)為凸規(guī)劃，若f(x)在非空可行集R上是嚴(yán)格凸函

數(shù)，則(1)的全局極小點(diǎn)是唯一的。

證明：見(jiàn)書(shū)中定理2.14.注:

非線性規(guī)劃的局部最優(yōu)解不一定是全局最優(yōu)解,其可行解和最優(yōu)解集也不一定是凸集,甚至不是連通集.如果是凸規(guī)劃,就有很多好的性質(zhì)。凸規(guī)劃的性質(zhì)性質(zhì)3：設(shè)(1)為凸規(guī)劃，則為(1)的最優(yōu)解

的充要條件為：，有利用凸函數(shù)的一階判別條件（證明參見(jiàn)文中定理2.15）凸規(guī)劃的性質(zhì)多胞形：有限個(gè)點(diǎn)的凸包閉半空間是凸的多面體、極點(diǎn)、極方向閉半空間：稱為正閉半空間;稱為負(fù)閉半空間;H+和H-統(tǒng)稱為閉半空間。多面體：有限個(gè)閉半空間的交多面體的極點(diǎn)（頂點(diǎn)）：多面體、極點(diǎn)、極方向

對(duì)任意xS，不存在S

中的另外兩個(gè)點(diǎn)x1和x2，及極方向：方向d

不能表示為兩個(gè)不同方向的組合使方向：xS,dRn,d

0及總有時(shí)，稱d1和d2同方向。當(dāng)定理（極點(diǎn)特征）設(shè)A

滿秩，x

是S極點(diǎn)的充分必要條件是:存在分解A=[B,N]，其中B為m階非奇異矩陣，使xT=[xBT,xNT],這里xB=B-1b≥0,xN=0.S中必存在有限多個(gè)極點(diǎn)。(≤Cnm)定理（極方向特征）設(shè)A=[p1,p2,…,pn]滿秩，d

是S

極方向的充分必要條件是:存在分解A=[B,N]，其中B為m階非奇異矩陣，對(duì)于N中的列向量pj

使B-1pj≤0,dT=[dBT,dNT],dB=-B-1pj

,

dN=(0,...,1,…,0)TS中必存在有限多個(gè)極方向。(≤(n-m)Cnm)多面體S={xRnAx=b,x≥0}的極點(diǎn)和極方向定理（表示定理）考慮上述多面體S，設(shè)A滿秩，

為所有極點(diǎn)，

為所有極方向。那么，對(duì)于xS，且多面體S={xRnAx=b,x≥0}的極點(diǎn)和極方向使

一個(gè)凸集有非空的相對(duì)內(nèi)部；一個(gè)凸集是連通的并且在任意點(diǎn)具有可行方向；一個(gè)多面體的凸集可以由一個(gè)有限的極點(diǎn)和極方向的集合來(lái)刻畫(huà)；凸集上凸函數(shù)的全局極小值的存在可以非常方便的按照收縮方向來(lái)描述；為什么凸在最優(yōu)化中如此特殊

一個(gè)凸函數(shù)的局部極小點(diǎn)都是全局極小點(diǎn)；一個(gè)非凸函數(shù)可以被“凸化的”同時(shí)保持了全局極小值的最優(yōu)性；一個(gè)凸函數(shù)是連續(xù)的并且具有良好的可微性；閉凸錐關(guān)于極是自對(duì)偶的；凸且下半連續(xù)的函數(shù)關(guān)于共軛是自對(duì)偶的。為什么凸在最優(yōu)化中如此特殊向量運(yùn)算：x,yRn

x,y

的內(nèi)積：<x,y>=xTy=xiyi=x1y1+x2y2+…+xnyn

x,y

的距離：‖x-y‖=[(x-y)T(x-y)](1/2)x

的長(zhǎng)度：‖x‖=[xTx](1/2)

三角不等式：‖x+y‖≤‖x‖+‖y‖

定理（Cauchy-Schwarz不等式）重要的不等式定理1設(shè)A為n階對(duì)稱正定矩陣，則，恒有等號(hào)成立當(dāng)且僅當(dāng)x與線性相關(guān);

等式成立當(dāng)且僅當(dāng)x

與y線性相關(guān)。其中表示向量的內(nèi)積。定理3：設(shè)A為n階對(duì)稱正定矩陣，m與M分別為A的最小與最大特征值，則，恒有定理2：設(shè)A為n階對(duì)稱正定矩陣，m與M分別為A的最小與最大特征值，則，恒有

重要的不等式1/M與

1/m分別為A-1的最小與最大特征值范數(shù)

（A正定）橢球范數(shù)范數(shù)

范數(shù)

范數(shù)

范數(shù)----向量范數(shù)定義1：方陣A的范數(shù)是指與A相關(guān)聯(lián)并記做的一個(gè)非負(fù)數(shù)，它具有下列性質(zhì)：對(duì)于都有，而時(shí)；對(duì)于任意，都有；；；若還進(jìn)一步滿足：則稱之為與向量范數(shù)相協(xié)調(diào)（相容）的方陣范數(shù).

范數(shù)----矩陣范數(shù)定義2:設(shè)與是上的兩個(gè)范數(shù)，若存在，使得，則稱范數(shù)與是等價(jià)的。容易證明：其中是的最大特征值，而是的最小特征值。范數(shù)----范數(shù)等價(jià)中所有向量范數(shù)均等價(jià)。Cauchy-Schwarz不等式

當(dāng)且僅當(dāng)與線性相關(guān)時(shí)，等式成立。關(guān)于范數(shù)的幾個(gè)重要不等式定理（Cauchy-Schwarz不等式）

等式成立當(dāng)且僅當(dāng)x

與y線性相關(guān)。當(dāng)且僅當(dāng)與線性相關(guān)時(shí)，等式成立。關(guān)于范數(shù)的幾個(gè)重要不等式定理4：設(shè)A是正定矩陣，則當(dāng)且僅當(dāng)與線性相關(guān)時(shí)，等式成立。Cauchy-Schwarz不等式

設(shè)A是n階正定矩陣，則等號(hào)成立當(dāng)且僅當(dāng)與線性相關(guān)。關(guān)于范數(shù)的幾個(gè)重要不等式定理1設(shè)A為n階對(duì)稱正定矩陣，則，恒有等號(hào)成立當(dāng)且僅當(dāng)x與線性相關(guān);定理5：Young不等式：假定p與q都是大于1的實(shí)數(shù)，且滿足，則，有

當(dāng)且僅當(dāng)時(shí)，等式成立。關(guān)于范數(shù)的幾個(gè)重要不等式H?lder不等式其中p與q都是大于1的實(shí)數(shù)，且滿足.Minkowski不等式

關(guān)于范數(shù)的幾個(gè)重要不等式

定義3（序列收斂）：設(shè)是中的一個(gè)向量序列，，如果，存在正整數(shù)K，使得當(dāng)時(shí)，有，則稱序列收斂到