1、第二章 基本概念和理論基礎(chǔ),本章主要內(nèi)容：,1 多元函數(shù)的梯度及其Hesse矩陣 2 多元函數(shù)的極值及其判別條件 3 等高線 4 多元函數(shù)分析（二次函數(shù)） 5 凸集、凸函數(shù)、凸規(guī)劃 6 幾個重要的不等式,凸集、凸函數(shù)和凸規(guī)劃,問題（極小值點(diǎn)和最小值點(diǎn)之間的關(guān)系）： 設(shè)f(x)定義在D內(nèi)，f(x*)為極小值，這是一局部概念，即在x*的鄰域內(nèi)，f(x*)最小。若x*為f(x)的最小值點(diǎn)，則x*為f(x)的極小值點(diǎn)。反過來不一定成立。,一元函數(shù)有結(jié)論： 若f(x)在區(qū)間a,b上是凸的，則x*是f(x)的極小值點(diǎn)等價(jià)于x* 是f(x)的最小值。 且由微分學(xué)知：若 ，則f(x)是凸的。,為研究多元函數(shù)的

2、極值與最值的關(guān)系，下面介紹多元函數(shù)凸性。,規(guī)定：空集和單元素集也是凸集。 三角形，矩形，圓，球，凸多邊形，第一象限，第一卦限等都是凸的。,等價(jià)定義（凸集）：設(shè),凸集與性質(zhì),定義（凸集）：若集合 中任意兩點(diǎn)的連線都屬于 ，則稱 為凸集。,因?yàn)閮牲c(diǎn) 連線上任一點(diǎn)可以表示為,凸集的幾何特征,凸集的代數(shù)特征,稱集合 為凸集 。,恒有,凸集：在點(diǎn)集中任取兩點(diǎn)，則其連線仍在其中。,即沒有凹入的部分；沒有空洞。,A,B,C,D,凸集與性質(zhì),例1: 證明集合 S = xAx = b 是凸集。其中A為 mn矩陣，b為m維向量。,凸集與性質(zhì),所以,即S是凸集。,定義：設(shè) 那么稱 是 的凸組合。,性質(zhì)2：S 是凸集

3、 S 中任意有限個點(diǎn)的凸組合屬于 S。 證明：見書中定理 2.9 (P23). 提示：充分性顯然。必要性用數(shù)學(xué)歸納法。,凸集與性質(zhì),性質(zhì)1：設(shè) 是凸集，則 也是凸集。,注： 不一定是凸集。,定義（凸包）：包含集合D的所有凸集的交集稱為D的凸包，記 作Co(D)或者H(D). 注：由性質(zhì)1可知，Co(D)是包含D的最小凸集。,凸集與性質(zhì),0,定義（凸錐）：設(shè) ，如果對任意的 及所有的 ， 都有 ，則稱 是一個錐。一個同時是凸集的錐，稱為 凸錐。,多胞形：有限個點(diǎn)的凸包,由一元函數(shù)的幾何圖形知：f(x)是凸函數(shù)，任意給定曲線上兩點(diǎn)A，B，則弦AB在與弧AB之上，用數(shù)學(xué)式子表示：,凸函數(shù),弦AB的方

4、程：,令,則,上式可寫為：,所以：,定義（凸函數(shù)）: 設(shè)集合 D Rn 為凸集，函數(shù) f :DR, 若 x, y D, (0 , 1) ，均有 f( x+(1- ) y ) f(x)+(1- )f(y) ， 則稱 f(x)為凸集 D 上的凸函數(shù)。 若進(jìn)一步有上面不等式以嚴(yán)格不等式成立，則稱 f(x)為凸集 D 上的嚴(yán)格凸函數(shù)。 當(dāng)-f(x)為凸函數(shù)(嚴(yán)格凸函數(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

5、, 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ù)值的凸組合。 證明參見文中定理2.10的證明。,定理(一階條件): 設(shè)D Rn 為非空凸集，函數(shù) f :DR 在 D 上可微，則 (1) f在D上為凸函數(shù) 任意x，yD，恒有 f (y) f (x)+ f T(x)(y-x) (1) (2)

6、f在D上為嚴(yán)格凸函數(shù) 任意xyD，恒有 f (y) f (x)+ f T(x)(y-x) . (2) 證明:見書中定理 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ù)。 證明:見書中定理2.12（P28） 由一階條件和多元函數(shù)的泰勒展開式可證。 回憶：一個矩陣半正定充要條件是所有主子式非負(fù)； 一個矩陣正定充要條件是所有順序主子式為正。,凸函數(shù)的判定定理,例：設(shè)二次函數(shù) (1)：若 為半定矩陣，

7、在 中為凸函數(shù) ； (2)：若 為正定矩陣， 在 中為嚴(yán)格凸函數(shù)。,例：判斷f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函數(shù)？ 的順序主子式都是正的，所以正定，因此 f(x)在凸集D上是嚴(yán)格凸函數(shù)。,凸函數(shù)的判定定理,由于,故,證明,為凸函數(shù)。,也是凸函數(shù)。根據(jù)性質(zhì)2，,為凸函數(shù)。,看下述各式是否成立：,證明：首先用定義證明 是凸函數(shù)，即對任意,和,例: 試證明,為凹函數(shù)。,或,即,顯然，不管 和 取什么值，總有,從而,用同樣的方法可以證明,用一階條件證明,只需證,任意選取兩點(diǎn),或,或,或,不管y1、y2、x1、x2取什么值，上式均成立，從而得證。,例: 試證明,為凹函數(shù)。,-f

8、(x)的海賽矩陣處處負(fù)定，故,為(嚴(yán)格)凹函數(shù)。,下面用二階條件證明:,由于,例: 試證明,為凹函數(shù)。,定義（凸規(guī)劃）: 考慮如下非線性規(guī)劃,當(dāng) 都是凸函數(shù)時,稱規(guī)劃 為凸規(guī)劃,凸規(guī)劃,性質(zhì)1: 設(shè)(1)為凸規(guī)劃，則 i) (1)的可行集R是凸集； ii) (1)的最優(yōu)解集是凸集； iii) (1)的任何局部極小點(diǎn)都是全局極小點(diǎn)。證明：見書中定理 2.13.,性質(zhì)2: 設(shè)(1)為凸規(guī)劃，若f(x)在非空可行集R上是嚴(yán)格凸函 數(shù)，則(1)的全局極小點(diǎn)是唯一的。證明：見書中定理 2.14.,注: 非線性規(guī)劃的局部最優(yōu)解不一定是 整體最優(yōu)解,其可行解和最優(yōu)解集也 不一定是凸集,甚至不是連通集.如 果

9、是凸規(guī)劃, 就有很多好的性質(zhì)。,凸規(guī)劃的性質(zhì),一個凸集有非空的相對內(nèi)部； 一個凸集是連通的并且在任意點(diǎn)具有可行方向； 一個凸函數(shù)的局部極小點(diǎn)都是全局極小點(diǎn)； 一個凸函數(shù)是連續(xù)的并且具有良好的可微性。,為什么凸在最優(yōu)化中如此特殊,課后作業(yè) P38 2.19 2.20(1,3) 2.28 2.29,第二章 基本概念和理論基礎(chǔ),本章主要內(nèi)容：,1 多元函數(shù)的梯度及其Hesse矩陣 2 多元函數(shù)的極值及其判別條件 3 等高線 4 多元函數(shù)分析（二次函數(shù)） 5 凸集、凸函數(shù)、凸規(guī)劃 6 幾個重要的不等式,向量運(yùn)算：x , y Rn x , y 的內(nèi)積：=xTy = xiyi = x1y1+ x2y2+

10、+ xnyn x , y 的距離： x-y= (x-y)T(x-y)(1/2) x 的長度： x= xTx (1/2) 三角不等式： x + yx+y,定理（Cauchy-Schwarz不等式）,重要的不等式,定理1 設(shè)A為 n 階對稱正定矩陣，則 ，恒有 等號成立當(dāng)且僅當(dāng) x 與 線性相關(guān);,等式成立當(dāng)且僅當(dāng) x 與 y 線性相關(guān)。,其中 表示向量的內(nèi)積。,定理3：設(shè)A為 n 階對稱正定矩陣， m與M分別為A的最小 與最大特征值，則 ，恒有,定理2：設(shè)A為 n 階對稱正定矩陣，m與M分別為A的最小 與最大特征值，則 ，恒有,重要的不等式,1/M與 1/m分別為A-1的最小與最大特征值,范數(shù),

11、（A正定）橢球范數(shù),范數(shù),范數(shù),范數(shù),范數(shù)-向量范數(shù),定義1：方陣A的范數(shù)是指與A相關(guān)聯(lián)并記做 的一個非負(fù)數(shù)，它具有下列性質(zhì)： 對于 都有 ，而 時 ； 對于任意 ，都有 ； ； ； 若還進(jìn)一步滿足： 則稱之為與向量范數(shù) 相協(xié)調(diào)（相容）的方陣范數(shù).,范數(shù)-矩陣范數(shù),定義2:設(shè) 與 是 上的兩個范數(shù)，若存在 ， 使得 ，則稱范數(shù) 與 是等價(jià)的。 容易證明： 其中 是 的最大特征值，而 是 的最小特征值。,范數(shù)-范數(shù)等價(jià),中所有向量范數(shù)均等價(jià)。,Cauchy-Schwarz不等式 當(dāng)且僅當(dāng) 與 線性相關(guān)時，等式成立。,關(guān)于范數(shù)的幾個重要不等式,定理（Cauchy-Schwarz不等式）,等式成立當(dāng)

12、且僅當(dāng) x 與 y 線性相關(guān)。,當(dāng)且僅當(dāng) 與 線性相關(guān)時，等式成立。,關(guān)于范數(shù)的幾個重要不等式,定理4：設(shè)A是正定矩陣，則,當(dāng)且僅當(dāng) 與 線性相關(guān)時，等式成立。,Cauchy-Schwarz不等式,設(shè)A是n階正定矩陣，則 等號成立當(dāng)且僅當(dāng) 與 線性相關(guān)。,關(guān)于范數(shù)的幾個重要不等式,定理1 設(shè)A為 n 階對稱正定矩陣，則 ，恒有 等號成立當(dāng)且僅當(dāng) x 與 線性相關(guān);,定理5：,Young不等式：假定p與q都是大于1的實(shí)數(shù)，且滿 足 ，則 ，有 當(dāng)且僅當(dāng) 時，等式成立。,關(guān)于范數(shù)的幾個重要不等式,Hlder不等式 其中p與q都是大于1的實(shí)數(shù)，且滿足 . Minkowski不等式,關(guān)于范數(shù)的幾個重要不等式,定義3（序列收斂）：設(shè) 是 中的一個向量序列， ，如果 ，存在正整數(shù)K，使得當(dāng) 時，有 ，則稱序列收斂到 ；或稱序列 以為極限，記 . 按此定義，序列若存在極限，則該序列的任何子序列有相同的極限，即序列的極限是唯一的. 定義4（聚點(diǎn)）：設(shè) 是 中的一個向量序列，如果存在 一個子序列 ，使得 , 則稱 是序列