1、第二章最優(yōu)化問題數(shù)學(xué)基礎(chǔ)為了便于學(xué)習(xí)最優(yōu)化方法，本章將對與優(yōu)化方法密切相關(guān)的數(shù)學(xué)知識作一簡要介紹，而有些數(shù)學(xué)知識將在講解各種算法時(shí)，隨之介紹2.1 二次型與正定矩陣一、二次型與實(shí)對稱矩陣二次型理論在最優(yōu)化設(shè)計(jì)中應(yīng)用十分廣泛應(yīng)用矩陣的乘法運(yùn)算，二次型與實(shí)對稱矩陣緊密地聯(lián)系在一起了，從而二次型的基本問題又可轉(zhuǎn)化成實(shí)對稱矩陣問題二次型理論問題起源于化二次曲線和二次曲面的方程為標(biāo)準(zhǔn)形式的問題推廣到n維空間中，二次超曲面的一般方程為用矩陣表示可簡記為其中矩陣A的元素正是二次型的項(xiàng)的系數(shù)的一半，是二次型的項(xiàng)的系數(shù)因此，二次型和它的矩陣A是相互唯一決定的，且二、正定矩陣定義2.1 如果二次型對于任何一組不全

2、為零的數(shù)恒有，則稱正定，且二次型矩陣A也稱為正定簡言之，一個(gè)對稱矩陣A如果是正定的，則二次型對于所有非零向量X其值總為正類似可以給出定義，若二次型，則A為半正定矩陣；若，則A為半負(fù)定矩陣；若二次型既不是半正定又不是半負(fù)定，就稱矩陣A為不定的矩陣A為正定的充要條件是它的行列式的順序主子式全部大于零，即由此可見，正定矩陣必然是非奇異的例2.1 判斷矩陣是否正定解，A是正定的2.2 方向?qū)?shù)與梯度一、方向?qū)?shù)所謂方向?qū)?shù)的概念是作為偏導(dǎo)數(shù)的一個(gè)推廣而引入的，它主要研究函數(shù)沿任一給定方向的變化率定義2.2 設(shè)在點(diǎn)處可微，P是固定不變的非零向量，是方向P上的單位向量，則稱極限（2.1）為函數(shù)在點(diǎn)處沿P方

3、向的方向?qū)?shù)，式中是它的記號定義2.3 設(shè)是連續(xù)函數(shù)，且，若存在，當(dāng)時(shí)都有，則稱P為在點(diǎn)處的下降方向若，則稱P為在點(diǎn)處的上升方向由以上兩個(gè)定義可立刻得到如下的結(jié)論：若，則從出發(fā)在附近沿P方向是下降；若，則從出發(fā)在附近沿P方向是上升事實(shí)上，若，則當(dāng)充分小時(shí)，根據(jù)式（2.1）必有，即，其中是從出發(fā)在P方向上的點(diǎn)，說明是下降的同理可以說明，若，則是上升的二、梯度定義2.4 以的n個(gè)偏導(dǎo)數(shù)為分量的向量稱為在X處的梯度，記為梯度也可以稱為函數(shù)關(guān)于向量的一階導(dǎo)數(shù)以下幾個(gè)特殊類型函數(shù)的梯度公式是常用的：（1）若（常數(shù)），則，即；（2）證設(shè)，則于是的第個(gè)分量是所以（3）（4）若是對稱矩陣，則三、梯度與方向?qū)?shù)

4、之間的關(guān)系定理2.1 設(shè)在點(diǎn)處可微，則，其中是方向上的單位向量證明在相應(yīng)的數(shù)學(xué)分析中可找到（故略去）由這個(gè)定理容易得到下列結(jié)論：(1) 若，則P的方向是函數(shù)在點(diǎn)處的下降方向；(2) 若，則的方向是函數(shù)在點(diǎn)處的上升方向方向?qū)?shù)的正負(fù)決定了函數(shù)值的升降，而升降的快慢就由它的絕對值大小決定絕對值越大，升降的速度就越快，即=，上式中的等號，當(dāng)且僅當(dāng)?shù)姆较蚺c的方向相同時(shí)才成立由此可得如下重要結(jié)論(如圖2.1所示）：(1)梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值的最速

5、下降方向?qū)τ谝粋€(gè)最優(yōu)化問題，為了盡快得到最優(yōu)解，在每一步迭代過程中所選取的搜索方向總是希望它等于或者是靠近于目標(biāo)函數(shù)的負(fù)梯度（即）圖2.1的方向，這樣才能使函數(shù)值下降的最快例2.2試求目標(biāo)函數(shù)在點(diǎn)處的最速下降方向，并求沿這個(gè)方向移動(dòng)一個(gè)單位長后新點(diǎn)的目標(biāo)函數(shù)值解 因?yàn)?，所以最速下降方向是這個(gè)方向上的單位向量是故新點(diǎn)是 ，對應(yīng)目標(biāo)函數(shù)值為2.3 海色矩陣及泰勒展式一、海色（Hesse）矩陣前面說過，梯度是關(guān)于的一階導(dǎo)數(shù)，現(xiàn)在要問關(guān)于的二階導(dǎo)數(shù)是什么？定義 2.5 設(shè)：，如果在點(diǎn)處對于自變量的各分量的二階偏導(dǎo)數(shù)都存在，則稱函數(shù)在點(diǎn)處二階可導(dǎo)，并且稱矩陣是在點(diǎn)處的Hesse矩陣在數(shù)學(xué)分析中已經(jīng)知道，

6、當(dāng)在點(diǎn)處的所有二階偏導(dǎo)數(shù)為連續(xù)時(shí)有因此，在這種情況下Hesse矩陣是對稱的例2.3 求目標(biāo)函數(shù)的梯度和Hesse矩陣解因?yàn)?，所以又因?yàn)樗岳?.4 設(shè)，求線性函數(shù)在任意點(diǎn)X處的梯度和Hesse矩陣解設(shè)，則，（2.2）由式（2.2）進(jìn)而知（階零矩陣）例2.5 設(shè)是對稱矩陣，求二次函數(shù)在任意點(diǎn)處的梯度和Hesse矩陣解設(shè)，則將它對各變量求偏導(dǎo)數(shù)，得在上式中顯然再對它們求偏導(dǎo)數(shù)得以上例子說明，元函數(shù)求導(dǎo)與一元函數(shù)的求導(dǎo)在形式上是一致的，即線性函數(shù)的一階導(dǎo)數(shù)為常向量，其二階導(dǎo)數(shù)為零矩陣；而二次函數(shù)的一階導(dǎo)數(shù)為線性向量函數(shù)，二階導(dǎo)數(shù)為常矩陣最后介紹在今后的計(jì)算中要用到的向量函數(shù)的導(dǎo)數(shù)定義2.6 設(shè)，記，

7、如果在點(diǎn)處對于自變量的各分量的偏導(dǎo)數(shù)都存在，則稱向量函數(shù)在點(diǎn)處是一階可導(dǎo)的，并且稱矩陣是在點(diǎn)處的一階導(dǎo)數(shù)或Jacobi矩陣，簡記為由于元函數(shù)的梯度是向量函數(shù)所以的一階導(dǎo)數(shù)或Jacobi矩陣為即據(jù)此，從上式得知，函數(shù)梯度的Jacobi矩陣即為此函數(shù)的Hesse矩陣下面給出今后要用到的幾個(gè)公式：（1），其中是分量全為常數(shù)的維向量，是階零矩陣（2），其中是維向量，是階單位矩陣（3），其中是階矩陣（4）設(shè)，其中，則二、泰勒展開式多元函數(shù)的泰勒展開在最優(yōu)化方法中十分重要，許多方法及其收斂性的證明是從它出發(fā)的，這里給出泰勒展開定理及其證明定理2.2 設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，則，（2.3）其中，而證設(shè)，于是，

8、對按一元函數(shù)在點(diǎn)展開，得到，其中令，于是（2.4）又因?yàn)?，代入式?.4）中，所以式（2.3）還可以寫成2.4 極小點(diǎn)的判定條件函數(shù)在局部極小點(diǎn)應(yīng)滿足什么條件？反之，滿足什么條件的是局部極小點(diǎn)？這是我們關(guān)心的基本問題下面針對多元函數(shù)的情形給出各類極小點(diǎn)的定義定義2.7 對于任意給定的實(shí)數(shù)，滿足不等式的的集合稱為點(diǎn)的鄰域，記為定義2.8 設(shè)，若存在點(diǎn)和數(shù)，都有，則稱為的局部極小點(diǎn)（非嚴(yán)格）定義2.9 設(shè)，若存在點(diǎn)和數(shù)，但，都有，則稱為的嚴(yán)格局部極小點(diǎn)定義2.10 設(shè)，若存在點(diǎn)，都有，則稱為在D上的全局極小點(diǎn)（非嚴(yán)格）定義2.11 設(shè)，若存在點(diǎn)，但，都有，則稱為在D上的嚴(yán)格全局極小點(diǎn)由以上定義看到

9、，是局部極小點(diǎn)，是指在以為中心的一個(gè)鄰域中在點(diǎn)處取得最小的值；而是全局極小點(diǎn)，是指在定義域D中在點(diǎn)處取得最小的值全局極小點(diǎn)可能在某個(gè)局部極小點(diǎn)處取得，也可能在D的邊界上取得實(shí)際問題通常是求全局極小點(diǎn)，但是直到目前為止，最優(yōu)化中絕大多數(shù)方法都是求局部極小點(diǎn)的，解決這一矛盾的一種方法是先求出所有的局部極小點(diǎn)，再求全局極小點(diǎn)定理2.3 設(shè)具有連續(xù)的一階偏導(dǎo)數(shù)若是的局部極小點(diǎn)并且是D的內(nèi)點(diǎn)，則（2.5）證設(shè)是任意單位向量，因?yàn)槭堑木植繕O小點(diǎn)，所以存在，當(dāng)或時(shí)總有（2.6）引入輔助一元函數(shù)，此時(shí)，由式（2.6）得又因是D的內(nèi)點(diǎn)，所以與它對應(yīng)的是的局部極小點(diǎn)又根據(jù)一元函數(shù)極小點(diǎn)的必要條件，得到，即再由單位

10、向量的任意性得這里條件（2.5）僅僅是必要的，而不是充分的例如在點(diǎn)處的梯度是，但是雙曲面的鞍點(diǎn)，而不是極小點(diǎn)（如圖2.2所示）圖2.2定義2.12 設(shè)是D的內(nèi)點(diǎn)若，則稱為的駐點(diǎn)定理2.4 設(shè)具有連續(xù)二階偏導(dǎo)數(shù)，是D的一個(gè)內(nèi)點(diǎn)若，并且是正定的，則是的嚴(yán)格局部極小點(diǎn)證因?yàn)槭钦ň仃?，則必存在，使得對于所有的都有（參看高等代數(shù)二次型理論）現(xiàn)在將在點(diǎn)處按泰勒公式展開，并注意到，于是可得當(dāng)充分接近（但）時(shí)，上式左端的符號取決于右端第一項(xiàng)，因此一般說來，這個(gè)定理僅具有理論意義因?yàn)閷τ趶?fù)雜的目標(biāo)函數(shù)，Hesse矩陣不易求得，它的正定性就更難判定了定理2.5若多元函數(shù)在其極小點(diǎn)處的Hesse矩陣是正定的，則它

11、在這個(gè)極小點(diǎn)附近的等值面近似地呈現(xiàn)為同心橢球面簇證設(shè)是多元函數(shù)的極小點(diǎn)，并設(shè)是充分靠近極小點(diǎn)的一個(gè)等值面，即充分小把在點(diǎn)展成泰勒公式，即右端第二項(xiàng)因是極小點(diǎn)有而消失如果略去第4項(xiàng)，那么，又因?yàn)?，所以?.7）按假設(shè)正定，由二次型理論知式（2.7）是以為中心的橢球面方程2.5 錐、凸集、凸錐在本節(jié)中，給出維Euclid空間中的錐、凸集和凸錐的定義，以及與其相關(guān)的一些概念和性質(zhì)一、定義與簡單性質(zhì)定義2.13 集合若及任意的數(shù)，均有，則稱C為錐定義2.14 設(shè)是中的個(gè)已知點(diǎn)若對于某點(diǎn)存在常數(shù)且使得，則稱是的凸組合若且，則稱是的嚴(yán)格凸組合定義2.15 集合若和，以及任意的數(shù)，均有則稱C為凸集定義2.1

12、6設(shè)且，則集合稱為中的半空間特別地，規(guī)定空集是凸集容易驗(yàn)證，空間、半空間、超平面、直線、點(diǎn)、球都是凸集定理2.6 任意一組凸集的交仍然是凸集證設(shè)，其中I是的下標(biāo)集，都是凸集任取，則對于任意都是任取且，因是凸集，有于是，即C是凸集若集合C為錐，C又為凸集，則稱C為凸錐若C為凸集，也為閉集，則稱C為閉凸集若C為凸錐，也為閉集，則稱C為閉凸錐由數(shù)學(xué)歸納法不難證明如下的定理2.7和2.8定理2.7 集合C為凸集的充分必要條件是，及任意數(shù)（），有定理2.8 集合C為凸錐的充分必要條件是，及任意數(shù)（），均有定義 2.17有限個(gè)半空間的交稱為多面集，其中為矩陣，為維向量例2.6集合為多面集，其幾何表示如圖2

13、.3畫斜線部分圖2.3在多面集的表達(dá)式中，若，則多面集也是凸錐，稱為多面錐在有關(guān)凸集的理論及應(yīng)用中，極點(diǎn)和極方向的概念有著重要作用定義 2.18設(shè)為非空凸集，若不能表示成中兩個(gè)不同點(diǎn)的凸組合；換言之，若假設(shè)，必推得，則稱是凸集的極點(diǎn)按此定義，圖2.4中多邊形的頂點(diǎn)和是極點(diǎn)，而和不是極點(diǎn)圖2.4中圓周上的點(diǎn)均為極點(diǎn)圖2.4由圖2.4可以看出，在給定的兩個(gè)凸集中，任何一點(diǎn)都能表示成極點(diǎn)的凸組合定義 2.19設(shè)為中的閉凸集，為非零向量，如果對中的每一個(gè)，都有射線，則稱向量為的方向又設(shè)和是的兩個(gè)方向，若對任何正數(shù)，有，則稱和是兩個(gè)不同的方向若的方向不能表示成該集合的兩個(gè)不同方向的正的線性組合，則稱為的

14、極方向圖2.5例2.7如圖2.5所示，對于集合，凡是與向量夾角小于或等于的向量，都是它的方向和是的兩個(gè)極方向的其它方向都能表示成這兩個(gè)極方向的正線性組合例2.8 設(shè)為非空集合，是非零向量證明為的方向的充要條件是且證按照定義2.19，為的方向的充要條件是對每一個(gè)，有（2.8）根據(jù)集合的定義，由式（2.8）可得，（2.9）（2.10）由于，及可取任意非負(fù)數(shù)，因此由式（2.9）和式（2.10）知及對于有界多面集，它的每一個(gè)點(diǎn)可用極點(diǎn)的凸組合來表示，反之，由極點(diǎn)的凸組合表示的點(diǎn)一定屬于這個(gè)多面集對此可簡要說明如下：設(shè)有多面集，如圖2.6(a)所示若，則其中均為非負(fù)數(shù)，且，即為極點(diǎn)，和的凸組合反之，設(shè)，

15、則，即如果多面集是無界的，那么對于該多面集中的任一點(diǎn)（極點(diǎn)除外），只用極點(diǎn)來表示是不行的，還需要用極方向如圖2.6(b)所示，這時(shí)有，其中是中某個(gè)數(shù)，是某一個(gè)非負(fù)數(shù)圖2.6概括起來，有下列定理：定理2.9設(shè)為非空多面集，則有（1）極點(diǎn)集非空，且存在有限個(gè)極點(diǎn)（2）極方向集合為空集的充要條件是有界若無界，則存在有限個(gè)極方向（3）的充要條件是，其中，關(guān)于上述定理的證明參見參考文獻(xiàn)6二、凸集分離定理凸集分離定理是凸分析中最重要的定理之一，它在最優(yōu)化理論和模型當(dāng)中具有重要的應(yīng)用所謂集合的分離是指對于兩個(gè)集合C1和C2存在一個(gè)超平面H，使得C1在H的一邊，而C2在H的另一邊如果超平面方程為，那么對位于H

16、某一邊的點(diǎn)必有，而對位于H另一邊的必有定義2.20設(shè)C1和C2是中的兩個(gè)非空集合，是超平面，若對于每一個(gè)都有，對于每一個(gè)都有（或情況恰好相反），則稱超平面H分離集合C1和C2定理2.10 若C為閉凸集，則存在，以及數(shù)，對，有，并且存在，使得定理2.11 設(shè)C為凸集，則存在，使得，有定理2.12 設(shè)C為閉凸集，則C可表為所有包含C的半空間的交，即，其中上述定理的證明過程參見參考文獻(xiàn)62.6 凸函數(shù)一、各類凸函數(shù)定義及性質(zhì)設(shè)函數(shù)定義在凸集C上，其中定義2.21 若存在常數(shù)，使得，以及，若有，則稱為一致凸函數(shù)；若有，則稱為嚴(yán)格凸函數(shù)；若有，則稱為凸函數(shù)定義2.22 設(shè)為可微函數(shù)若，當(dāng)都有，則稱為偽凸

17、函數(shù)定義2.23 對，且，以及，若，則稱為嚴(yán)格擬凸函數(shù)；定義2.24 對，以及，若，則稱為擬凸函數(shù)；定義2.25 對，且，以及，若，則稱為強(qiáng)擬凸函數(shù)定理2.13 若為一致凸函數(shù)，則為嚴(yán)格凸函數(shù)證：設(shè)為一致凸函數(shù)，則，及，有，即為嚴(yán)格凸函數(shù)定理2.14 若為嚴(yán)格凸函數(shù)，則為凸函數(shù)定理2.15 設(shè)為可微函數(shù)若為凸函數(shù)，則為偽凸函數(shù)定理2.16 設(shè)為偽凸函數(shù)，則為嚴(yán)格擬凸函數(shù)定理2.17 設(shè)為下半連續(xù)的嚴(yán)格擬凸函數(shù)，則為擬凸函數(shù)定理2.18 若為嚴(yán)格凸函數(shù)，則為強(qiáng)擬凸函數(shù)定理2.19 設(shè)為強(qiáng)擬凸函數(shù)，則為嚴(yán)格擬凸函數(shù)下半連續(xù)的定義及定理2.14定理2.19的證明過程參見參考文獻(xiàn)6上述幾種凸函數(shù)有圖2

18、.7所示的關(guān)系圖2.7凸函數(shù)與凸集之間有如下關(guān)系：定理2.20 設(shè)，其中C為非空凸集若是凸函數(shù)，則對于任意實(shí)數(shù)，水平集是凸集證若是空集，則是凸集以下設(shè)非空，任取，則設(shè)且，由是凸函數(shù)知，即，所以是凸集判定一個(gè)函數(shù)是否為凸函數(shù)，一般說來是比較困難，但當(dāng)函數(shù)可微時(shí)，有如下幾個(gè)定理可供使用定理2.21 設(shè)是可微函數(shù)，其中C為凸集則（1）為凸函數(shù)的充要條件是，都有；（2.11）（2）為嚴(yán)格凸函數(shù)的充要條件是，且，都有證（1）先證必要性已知是C上的凸函數(shù)，要證式（2.11）由凸函數(shù)定義知，對滿足的任意數(shù)都有，令，則代入上式中，經(jīng)移項(xiàng)可得（2.12）令，由的可微性，利用一階泰勒展式、方向?qū)?shù)定義及式（2.1

19、2），可得這就證明了式（2.11）再證充分性任取一對數(shù)且考慮點(diǎn)，根據(jù)充分性假設(shè)，應(yīng)有，兩式分別乘以和后相加，得到由凸函數(shù)定義知，是C上的凸函數(shù)（2）充分性可依照（1）的充分性證得，下證必要性因?yàn)閲?yán)格凸函數(shù)本身是凸函數(shù)，所以，且，都有以下證明式中只能取“”號假設(shè)存在，且，使得（2.12）取，由的嚴(yán)格凸性，有（2.13）把式（2.12）代入式（2.13）中，經(jīng)整理得根據(jù)本定理（1）部分結(jié)論得知，此式與是凸函數(shù)相矛盾定理2.22 設(shè)是二次可微函數(shù)，C為非空開凸集，則為C上凸函數(shù)的充要條件是Hesse矩陣在C上任意點(diǎn)均半正定證明略定理2.23 設(shè)是二次可微函數(shù)，C為非空凸集若Hesse矩陣在C上任意點(diǎn)

20、均正定，則在C上為嚴(yán)格凸函數(shù)證明略，需要注意，該定理的逆命題不真例如在上為嚴(yán)格凸函數(shù)，但是它的Hesse矩陣在點(diǎn)處是半正定的二、凸規(guī)劃定義2.26 設(shè)，其中是非空凸集，是凸函數(shù)，則形式為的問題稱為凸規(guī)劃問題更進(jìn)一步，設(shè)若都是上的凸函數(shù)，都是上的線性函數(shù)，則容易驗(yàn)證C是凸集事實(shí)上，因?yàn)槎际峭购瘮?shù)，根據(jù)定理2.20集合也都是凸集此外，超平面，也都是凸集顯然，C是的交集，根據(jù)定理2.6，C是凸集于是，在這種情況下凸規(guī)劃問題又可表示成如下形式：如下定理指明凸規(guī)劃的一個(gè)重要性質(zhì)定理2.24 設(shè)是凸規(guī)劃問題的局部極小點(diǎn)，（1）若是凸函數(shù)，則是凸規(guī)劃問題全局極小點(diǎn)；（2）若是嚴(yán)格凸函數(shù)，則是凸規(guī)劃問題的唯一

21、全局極小點(diǎn)證（1）使用反證法假設(shè)不是全局極小點(diǎn)，則必存在使得對于與的任意凸組合，其中且，根據(jù)的凸性，有由此看到，當(dāng)充分小時(shí)，充分接近，注意到此時(shí)也有，而這與是局部極小點(diǎn)相矛盾因此必是全局極小點(diǎn)（2）假設(shè)不是唯一全局極小點(diǎn)必存在但使得考慮中點(diǎn)由的嚴(yán)格凸性，有此式與為全局極小點(diǎn)相矛盾這就證明了唯一性定義2.27形式為（2.14）的函數(shù)稱為元二次函數(shù)，其中，這里的A是對稱矩陣，即若A為正定，則稱（2.14）為正定二次函數(shù)注意到，由定理2.23知，正定二次函數(shù)是嚴(yán)格凸函數(shù)，在最優(yōu)化算法構(gòu)造中它起著特殊的作用定義2.28形式為（2.15）的問題稱為二次規(guī)劃問題，其中是矩陣，是矩陣若A為半正定或正定，則稱

22、（2.15）為二次凸規(guī)劃問題本書不作專門討論解2.7 約束問題的最優(yōu)性條件所謂最優(yōu)性條件就是最優(yōu)化問題的目標(biāo)函數(shù)與約束函數(shù)在最優(yōu)點(diǎn)處滿足的充要條件這種條件對于最優(yōu)化算法的終止判定和最優(yōu)化理論推證都是至關(guān)重要的最優(yōu)性必要條件是指在最優(yōu)點(diǎn)處滿足哪些條件；充分條件是指滿足哪些條件的點(diǎn)是最優(yōu)點(diǎn)本節(jié)僅講述最基本的結(jié)論一、約束最優(yōu)解對約束優(yōu)化問題的求解，其目的是在由約束條件所規(guī)定的可行域內(nèi)，尋求一個(gè)目標(biāo)函數(shù)值最小的點(diǎn)及其函數(shù)值這樣的解稱為約束最優(yōu)解約束最優(yōu)點(diǎn)除了可能落在可行域內(nèi)的情況外，更常常是在約束邊界上或等式約束曲面上，因此它的定義及它的一階必要條件與無約束優(yōu)化問題不同（一）約束優(yōu)化問題的類型約束優(yōu)化

23、問題根據(jù)約束條件類型的不同分為三種，其數(shù)學(xué)模型如下：（1）不等式約束優(yōu)化問題（IP型）（2.16）（2）等式約束優(yōu)化問題（EP型）（3）一般約束優(yōu)化問題（GP型）（二）約束優(yōu)化問題的局部解與全局解按一般約束優(yōu)化問題，其可行域?yàn)槿魧δ晨尚悬c(diǎn)存在，當(dāng)與它鄰域的點(diǎn)之距離時(shí)，總有則稱為該約束優(yōu)化問題的一個(gè)局部最優(yōu)解下面以一個(gè)簡單例子說明設(shè)有該問題的幾何圖形如圖2.8所示從圖上的目標(biāo)函數(shù)等值線和不等式約束與等式約束的函數(shù)曲線可寫出它的兩個(gè)局部最優(yōu)解這是因?yàn)樵邳c(diǎn)鄰域的任一滿足約束的點(diǎn)，都有；同理，亦然圖2.8對某些約束優(yōu)化問題，局部解可能有多個(gè)在所有的局部最優(yōu)解中，目標(biāo)函數(shù)值最小的那個(gè)解稱為全局最優(yōu)解在上

24、例中，由于，所以全局最優(yōu)解為由此可知，約束優(yōu)化問題全局解一定是局部解，而局部解不一定是全局解這與無約束優(yōu)化問題是相同的二、約束優(yōu)化問題局部解的一階必要條件對于約束，現(xiàn)在進(jìn)一步闡明起作用約束與不起作用約束的概念一般的約束優(yōu)化問題，其約束包含不等式約束和等式約束在可行點(diǎn)處，如果有，則該約束稱可行點(diǎn)的起作用約束；而如果有，則該約束稱可行點(diǎn)的不起作用約束對于等式約束，顯然在任意可行點(diǎn)處的等式約束都是起作用約束在某個(gè)可行點(diǎn)處，起作用約束在的鄰域內(nèi)起到限制可行域范圍的作用，而不起作用約束在處的鄰域內(nèi)就不產(chǎn)生影響因此，應(yīng)把注意力集中在起作用約束上（一）IP型約束問題的一階必要條件圖2.9所示為具有三個(gè)不等式

25、約束的二維最優(yōu)化問題圖2.9圖2.9（a）是最優(yōu)點(diǎn)在可行域內(nèi)部的一種情況在此種情形下，點(diǎn)的全部約束函數(shù)值均大于零，所以這組約束條件對其最優(yōu)點(diǎn)都不起作用換句話說，如果除掉全部約束，其最優(yōu)點(diǎn)也仍是同一個(gè)點(diǎn)因此這種約束優(yōu)化問題與無約束優(yōu)化問題是等價(jià)的圖2.9（b）所示的約束最優(yōu)點(diǎn)在的邊界曲線與目標(biāo)函數(shù)等值線的切點(diǎn)處此時(shí)，所以是起作用約束，而其余的兩個(gè)是不起作用約束既然約束最優(yōu)點(diǎn)是目標(biāo)函數(shù)等值線與邊界的切點(diǎn)，則在點(diǎn)處目標(biāo)函數(shù)的梯度與約束函數(shù)梯度矢量必共線，而且方向一致若取非負(fù)乘子，則在處存在如下關(guān)系另一種情況如圖2.9（c）所示當(dāng)前迭代點(diǎn)在兩約束交點(diǎn)上，該點(diǎn)目標(biāo)函數(shù)的梯度矢量夾于兩約束函數(shù)的梯度矢量之

26、間顯然，在點(diǎn)鄰近的可行域內(nèi)部不存在目標(biāo)函數(shù)值比更小的可行點(diǎn)因此，點(diǎn)就是約束最優(yōu)點(diǎn)，記作由圖可知，此時(shí)點(diǎn)目標(biāo)函數(shù)的梯度可表達(dá)為約束函數(shù)梯度和的線性組合若用代替即有成立，且式中的乘子和必為非負(fù)總結(jié)以上各種情況，最優(yōu)解的一階必要條件為對于（2.16）IP型約束問題的一階必要條件討論如下：設(shè)最優(yōu)點(diǎn)位于個(gè)約束邊界的匯交處，則這個(gè)約束條件組成一個(gè)起作用的約束集按上面的分析，對于點(diǎn)必有下式成立（2.17）但是在實(shí)際求解過程中，并不能預(yù)先知道最優(yōu)點(diǎn)位于哪一個(gè)或哪幾個(gè)約束邊界的匯交處為此，把個(gè)約束全部考慮進(jìn)去，并取不起作用約束的相應(yīng)乘子為零，則最優(yōu)解的一階必要條件應(yīng)把式（2.17）修改為（2.18）式（2.18

27、）為IP型問題約束最優(yōu)解的一階必要條件，它與式（2.17）等價(jià)因?yàn)樵谙拢瑢τ谄鹱饔眉s束，必有使式（2.18）中的第四式成立；對于不起作用約束，雖然而必有，可見式（2.18）與式（2.17）等價(jià)（二）EP型約束問題的一階必要條件圖2.10所示為具有一個(gè)等式約束條件的二維化問題，其數(shù)學(xué)模型為在該問題中，等式約束曲線是它的可行域，而且目標(biāo)函數(shù)等值線與約束曲線的切點(diǎn)是該約束問題的最優(yōu)解圖2.10在點(diǎn)處，目標(biāo)函數(shù)的梯度與約束函數(shù)的梯度共線因此，在最優(yōu)點(diǎn)處一定存在一個(gè)乘子，使得成立對于一般的維等式約束優(yōu)化問題，其數(shù)學(xué)模型為則為其解的一階必要條件為（三）GP型約束問題解的一階必要條件由上述不等式約束優(yōu)化與等式約束優(yōu)化問題的一階必要條件，可以推出一般約束優(yōu)化問題的條件設(shè)維一般約束優(yōu)化問題的數(shù)學(xué)模型為（2.19）則為其解的一階必要條件應(yīng)為（2.20）函數(shù)稱為關(guān)于問題（2.19）的廣義拉格朗日函數(shù)，式中，為拉格朗日乘子由于引入拉格朗日函數(shù)，條件（2.20）中的第一式可寫為（四）KuhnTcker條件（簡稱KT條件）在優(yōu)化實(shí)用計(jì)算中，常常需要判斷某