工程优化方法及应用 第二章

基本概念和理论(lǐlùn)基础主要内容：§1代数基础：范数、正定性§2多元函数分析基础：Hesse矩阵、方向导数(dǎoshù)、中值公式§3多元函数的极值§4等高线§5凸分析基础：凸集、凸函数、凸规划§6

最优化算法的结构共七十七页向量(xiàngliàng)范数定义——l2范数——l1范数——lp范数——l∞范数§1代数(dàishù)基础——列向量共七十七页范数常见(chánɡjiàn)不等式l1-范数l2-范数l∞范数相互等价共七十七页——l2范数也称谱范数(ATA最大特征值开平方)特别(tèbié)地，方阵有如下范数——l1范数(列和的最大者)——l∞范数(行和的最大者)矩阵(jǔzhèn)范数共七十七页定义：设Q为n×n阶对称矩阵(jǔzhèn),若，均有，则称

Q正定。若

，均有

，则称Q半正定。若，均有，则称Q负定。若,均有，则称Q半负定。矩阵(jǔzhèn)正定性共七十七页正定(zhènɡdìnɡ)判定定理矩阵

Q半正定

Q的所有特征根大于等于零;

Q的各阶主子式都大于等于零；存在矩阵G，使得Q=GGT。矩阵

Q正定

Q的所有特征根大于零;

Q的各阶顺序主子式都大于零；Q的各阶主子式都大于零；存在非奇异矩阵G，使得Q=GGT

共七十七页负定判定(pàndìng)定理矩阵

Q半负定

Q的所有特征根小于等于零;

Q的所有奇数阶主子式都小于等于零，且偶数阶主子式都大于等于零；存在矩阵G，使得-Q=GGT。矩阵

Q负定

Q的所有特征根小于零;

Q的所有奇数阶顺序主子式都小于零，且偶数阶顺序主子式都大于零；Q的所有奇数阶主子式都小于零且偶数阶主子式都大于零；存在非奇异矩阵G，使得-Q=GGT

共七十七页解：对称矩阵Q的三个顺序主子(zhǔzi)式依次为例1

判定矩阵是否(shìfǒu)正定:矩阵Q是正定的。共七十七页§2

多元函数(hánshù)分析基础n元函数(hánshù)：

n元线性函数：

n元二次函数：

n元向量值线性函数：多元函数共七十七页序列(xùliè)收敛定义若满足，则称为Cauchy序列。i.e.注：收敛是Cauchy序列.Cauchy序列的任一子列都收敛。定义

设为一向量序列，如果则称序列依范数收敛到,记为

共七十七页给定区域(qūyù)

D上的n

元实值函数梯度(tīdù)、Hesse矩阵——列向量的梯度共七十七页的梯度的Hesse矩阵共七十七页常用的梯度(tīdù)和Hesse阵公式：其中(qízhōng)Q为实对称矩阵共七十七页方向(fāngxiàng)导数定义(方向导数(dǎoshù))设在点x

处可微,d为固定单位向量，则称f(x)

在x

处沿方向d

的方向导数为共七十七页最速上升方向(fāngxiàng)最速下降(xiàjiàng)方向共七十七页解：由于(yóuyú)则函数在处的最速下降方向例1试求目标函数在点处的最速下降(xiàjiàng)方向，并求沿这个方向移动一个单位长度后新点的目标函数值。此方向上的单位向量新点是共七十七页中值公式(gōngshì)设

二阶可导，则在x*的邻域内有：一阶Taylor展开式二阶Taylor展开式共七十七页第二章基本概念和理论(lǐlùn)基础本章主要内容：§1代数基础：范数、正定性§2多元函数分析基础：Hesse矩阵、方向导数(dǎoshù)、中值公式§3多元函数的极值§4等高线§5凸分析基础：凸集、凸函数、凸规划§6

最优化算法的结构共七十七页§3

多元函数(hánshù)的极值

对于一个极小化问题，我们的目的是求出全局极小点，而全局极小点不好求，因此我们一般的做法是先求出所有局部极小值点，再从中找出全局极小点。为了求出函数的局部极小值点，我们需要考察函数f在局部极小点处满足(mǎnzú)什么条件？反过来，满足(mǎnzú)什么条件的点是局部极小点？首先回顾二元函数的极值条件（高等数学），然后推广到多元函数。共七十七页二元函数极值(jízhí)的判别条件定理(dìnglǐ)

(必要条件)

设(1)为D的一个内点;可微;(2)在处,

（驻点）则在的极值点;(3)为且注：可微的极值点一定是驻点，反之不一定成立。例

在处梯度为，但只是双曲抛物面的鞍点，而不是极小点。f共七十七页

(2)当时，不是(bùshi)的极值点，称为函数的鞍点；(3)当时，不能确定，需另行讨论。定理(充分条件)

设(1)为D的一个内点;二次连续可微;(2)在的驻点，即(3)为且令则(1)当时，具有极值取严格极大值取严格极小值Hesse阵负定Hesse阵正定(zhènɡdìnɡ)共七十七页多元(duōyuán)函数的极值判别条件定理(必要条件)

设(1)x*为D的一个内点;可微;(2)在则的极值点;(3)为且证明(zhèngmíng):

借助一元函数极值的必要条件，见下页。共七十七页

设是的局部极小点，为任意(rènyì)单位向量。由定义知：当,即时，总有：令则而是D的内点，从而与之对应的t=0是的局部(júbù)极小点。

由一元函数极小点必要性条件知,而由前述性质知则,由单位向量任意性，即知。证明:（若，取，则

矛盾。）共七十七页定理(充分条件)

设(1)x*为D的一个内点;(2)二次连续可微;在(3)则的严格局部极小点（严格局部极大点）。为(4)正定（负定）；证明：借助多元函数(hánshù)的泰勒公式：（x充分接近时）。共七十七页课后作业(zuòyè)P382.12.32.9--2.14共七十七页第二章基本概念和理论(lǐlùn)基础本章主要内容：§1代数基础：范数、正定性§2多元(duōyuán)函数分析基础：Hesse矩阵、方向导数、中值公式§3多元函数的极值§4等高线§5凸分析基础：凸集、凸函数、凸规划§6

最优化算法的结构共七十七页Z=f(x,y)

的图形(túxíng)是一条曲面。f(x,y)=c

的图形称为等高线或等值线。令c=c1,c2,…等一系列的值，得到一族等高线。从等高线族的图形上大致可以看出函数值的变化情况。（利用二维观察三维）§4

等高线二元函数(hánshù)的等值线共七十七页共七十七页性质：极值(jízhí)点附近，二元函数的等高线近似于一族同心椭圆.理由(lǐyóu):注：极值点附近，二次函数的等高线就是一族准确的同心椭圆.极值点正好就是椭圆族的共同中心。因此，求二次函数的极值点问题，从几何上讲，也就是求等值线族的共同中心。共七十七页解：展开(zhǎnkāi)例把二次函数

化为矩阵向量形式并检验Q是否正定，如正定，试用(shìyòng)公式

求这个函数的极小点。与题中函数比较各项系数为：共七十七页由前例(qiánlì)知正定,极小(jíxiǎo)点为共七十七页性质(xìngzhì)：若函数在某点的梯度不为零，则该梯度必与过该点的等值线垂直.（梯度方向也称法向量）理由(lǐyóu):注：梯度所指的方向总是等值线的法方向，并且在极大值点处梯度方向指向近似椭圆的中心，而在极小值点处梯度方向背离近似椭圆的中心。共七十七页定义(dìngyì)（等值面）在三维以上的空间中，使目标函数z=f(x)取同一常数值的面{x|f(x)=r,r是常数}称为目标函数z=f(x)的等值面。定理

若多元函数在其极小点处的

Hesse阵正定，则它在这个极小点附近的等值面近似地呈现为同心超椭球面族。多元(duōyuán)函数的等值面共七十七页等值面的性质(xìngzhì)小结不同值的等值面之间不相交，因为目标函数是单值函数；除了极值点所在的等值面外，不会在区域内部中断，因为目标函数是连续的；一般地，在极值点附近(fùjìn)，等值面（线）近似地呈现为同心椭球面族（椭圆族），因为泰勒公式；二次函数的等值面是同心椭球面族，极值点是这个椭圆球面的共同中心。

二元函数，梯度所指的方向总是等值线的法方向，并且在极大值点处梯度方向指向近似椭圆的中心，而在极小值点处梯度方向背离近似椭圆的中心。共七十七页例

用图解法求解(qiújiě)

解：先画出目标函数(hánshù)等值线，再画出约束曲线。对应的最优值为由图易见约束直线与等值线的切点是最优点，利用解析几何的方法得该切点为本处约束曲线是一条直线，这条直线就是可行域；而最优点就是可行域上使等值线具有最小值的点.共七十七页第二章基本概念和理论(lǐlùn)基础本章主要内容：§1代数基础：范数、正定性§2多元函数分析基础：Hesse矩阵(jǔzhèn)、方向导数、中值公式§3多元函数的极值§4等高线§5凸分析基础：凸集、凸函数、凸规划§6

最优化算法概述共七十七页一元函数有结论(jiélùn)：若f(x)在区间[a,b]上是凸的，则x*是f(x)的极小值点等价于x*是f(x)的最小值。且由微分学知：若，则f(x)是凸的。§5凸分析(fēnxī)基础问题（极小值点和最小值点之间的关系）：设f(x)定义在D内，若x*为f(x)的最小值点，则x*为f(x)的极小值点。反过来不一定成立。为研究多元函数的极值与最值的关系，下面介绍多元函数凸性。共七十七页规定：空集和单元素集是凸集。根据(gēnjù)定义：三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸集。等价(děngjià)定义（凸集）：设§5.1凸集定义（凸集）：若集合中任意两点的连线都属于，则称为凸集。因为两点

连线上任一点可以表示为

凸集的几何特征凸集的代数特征称集合为凸集。恒有共七十七页凸集：在点集中(jízhōng)任取两点，则其连线仍在其中。即没有(méiyǒu)凹入的部分；没有(méiyǒu)空洞。⑴⑵⑶⑷⑸⑹ABCD共七十七页证明:即所以即H是凸集。

例2:

集合是凸集,称为超平面，c为n维向量。

例3：邻域是凸集。

例1:

集合是凸集.共七十七页定义：设那么(nàme)称是

的凸组合。

性质(xìngzhì)2：S是凸集

S中任意有限个点的凸组合属于S。证明：见书中定理2.9(P23)。充分性显然。必要性：归纳法。性质1：设是凸集，则也是凸集。注：不一定是凸集。性质1：设是凸集，则也是凸集。共七十七页定义（凸包）：包含(bāohán)集合D的所有凸集的交集,称为D的凸包.记作Co(D)或者H(D).注：由性质1可知，Co(D)是包含D的最小凸集。0定义（凸锥）：设，如果对任意的及所有的，都有，则称是一个锥。一个同时是凸集的锥，称为凸锥。定义（多胞形）：有限个点的凸包共七十七页凸集分离(fēnlí)定理HS2S1定义（集合分离）：设是非空集合，如果存在向量及，使得则称超平面分离和。共七十七页定理（投影定理）：设是非空凸集，，则（1）存在唯一的使得它与y

的距离最小，即（2）是点y

到S的距离最小的充要条件为证明：参考袁亚湘P39。令根据下确界的定义，存在序列使得。下面证它是柯西列即可。ySx共七十七页定理（点与凸集的分离定理）：设是非空凸集，，则如果存在唯一的及，使得即存在超平面分离y

和S。ylS证明(zhèngmíng)：参考袁亚湘P41共七十七页定理（Farkas

）设

则下列关系式有且仅有一组有解：证明(zhèngmíng)：参考袁亚湘P42几何(jǐhé)解释:(1)有解，(2)无解a2a1amca1a2amc(1)无解，(2)有解(1)式有解当且仅当凸锥{x|Ax≤0}与半空间{x|cTx>0}的交非空.(2)式有解当且仅当c在由A的行向量a1,a2,…,am所生成的凸锥内.共七十七页定义（凸函数）:

设集合D

Rn为凸集，函数f:D

R,若x,y

D,

(0,1)，均有

f(

x+(1-

)y

)≤f(x)+(1-

)f(y)

，则称f(x)为凸集D上的凸函数。凸函数：任意(rènyì)两个点的凸组合的函数值小于等于这两个点的函数值的凸组合。严格凸函数：进一步，若有上面不等式以严格不等式成立，则称f(x)为凸集上的严格凸函数。凹函数：当-f(x)为凸函数(严格凸)时，则称f(x)为凹函数(严格凹)。§5.2凸函数共七十七页f(X)Xf(X1)f(X2)

X1X2凸函数(hánshù)几何意义：任意两点的函数(hánshù)值的连线上的点都在曲线的上方，即弦位于曲线的上方．αx1+(1-α)x2f(αx1+(1-α)x2)αf(x1)

+(1-α)f(x2)共七十七页性质(xìngzhì)2：设f1,f2

是凸集D上的凸函数，设a,b>0,

则af1+bf2

是凸函数；

f(x)=max{f1(x),f2(x)}

是凸函数。思考：

af1-bf2

是否是凸函数？

g(x)=min{f1(x),f2(x)}是否是凸函数？凸函数的性质(xìngzhì)性质1：f(x)

为凸集S上的凸函数

S上任意有限点的凸组合的函数值小于等于各点函数值的凸组合。

证明参见文中P26定理2.10的证明。充分性显然，必要性用数学归纳法。共七十七页定理(dìnglǐ)(一阶条件):

设D

Rn为非空凸集，函数f:D

R

在D上可微，则

(1)f在D上为凸函数任意x，y

D，恒有

f(y)

≥f(x)+

fT(x)(y-x)

(1)(2)f在D上为严格凸函数任意x≠y

D，恒有

f(y)>f(x)+

fT(x)(y-x).(2)

证明:

见书中定理2.11(P27)，见下一页。凸函数的一阶判定(pàndìng)定理严格凸函数凸函数共七十七页证明(zhèngmíng)：（必要性）设f(x)

为凸函数，根据定义所以两边取极限得即若f(x)严格(yángé)凸函数，则有故有共七十七页证明(zhèngmíng)：（充分性）设令由假设(jiǎshè)得一式乘以a，二式乘以1-a，相加得若f(x)严格凸函数，上述大于等于号均变成大于号，即成立。共七十七页几何(jǐhé)解释一个可微函数是凸函数当且仅当曲线(qūxiàn)位于切线的上方凸函数

f(y)

≥f(x)+

fT(x)(y-x)共七十七页定理5（二阶条件）:

设D

Rn为含内点的非空凸集，函数f:D

R在D上二次可微，则

a)f在D上为凸函数

x

D，2f(x)

半正定；

b)

x

D，2f(x)

正定

f在D上为严格凸函数（特别(tèbié)注意逆命题不成立）。凸函数的二阶判定(pàndìng)定理证明：（充分性)（必要性）令得，

2f(x)

半正定。共七十七页例：设二次函数，根据二阶条件得

(1)若为半正定(zhènɡdìnɡ)矩阵，在中为凸函数；(2)若为正定矩阵，在中为严格凸函数。例：判断(pànduàn)

f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函数？的顺序主子式都是正的，所以正定，因此f(x)在凸集D上是严格凸函数。共七十七页由于(yóuyú)故证明(zhèngmíng)为凸函数。也是凸函数。根据性质2，为凸函数。看下述各式是否成立：证明：用定义证明是凸函数，即对任意和例:

试证明为凹函数。或即显然，不管和

取什么值，总有为凹函数。因此从而用同样的方法可以证明共七十七页用一阶条件(tiáojiàn)证明只需证任意(rènyì)选取两点或或或不管y1、y2、x1、x2取什么值，上式均成立，从而得证。是凹函数，要证例:

试证明为凹函数。共七十七页-f(x)的海赛矩阵(jǔzhèn)处处正定，故为(严格(yángé))凹函数。

下面用二阶条件证明:由于例:

试证明为凹函数。共七十七页5.3凸规划(guīhuà)例（凸规划）:

考虑如下非线性规划当都是凸函数时，则规划(1)为凸规划。定义（凸规划）:设为凸集，为上的凸函数，则称规划问题为凸规划问题．证明:即证明为凸集，因为-gi

为凸函数，所以-gi(

x+(1-

)y)≤-gi(x)-(1-

)gi(y)进而

gi(

x+(1-

)y)≥gi(x)+(1-

)gi(y)≥0共七十七页性质1:

设(1)为凸规划，则

A.规划(1)的可行集R是凸集；

B.规划(1)的最优解集是凸集；

C.规划(1)的任何局部极小点都是全局(quánjú)极小点。

证明：见书中P30定理2.13.性质2:

设(1)为凸规划，若f(x)在非空可行集R上是严格凸函

数，则(1)的全局极小(jíxiǎo)点是唯一的。

证明：见书中P31定理2.14.注:

非线性规划的局部最优解不一定是整体最优解,其可行解和最优解集也不一定是凸集,甚至不是连通集.如果是凸规划,就有很多好的性质。凸规划的性质共七十七页定理

凸规划的任一局部最优解都是它的整体最优解。证明：设x*是凸规划的一个(yīɡè)局部最优解，则存在δ>0,使如果(rúguǒ)x*不是整体最优解，则又因为f是凸函数，所以取α>0充分小：共七十七页例如下非线性规划是否为凸规划：正定(zhènɡdìnɡ)，凸函数共七十七页所以(suǒyǐ)，该问题为凸规划。半正定(zhènɡdìnɡ)，凸函数半正定，凸函数共七十七页

如图所示，该问题(wèntí)最优解（最小点）在x*点取得。共七十七页练习验证(yànzhèng)下列（MP）是凸规划共七十七页课后作业(zuòyè)

P382.192.20(1,3)2.282.29共七十七页第二章基本概念和理论(lǐlùn)基础本章主要内容：§1代数基础：范数、正定性、序列收敛§2多元函数分析基础：Hesse矩阵、方向导数、中值公式(gōngshì)§3多元函数的极值§4等高线§5凸分析基础：凸集、凸函数、凸规划§6

最优化算法的结构共七十七页n元函数求解无约束优化问题§6最优化算法(suànfǎ)的结构定理(必要条件)

设

(1)为D的一个内点;(2)

在可微;(3)为

的极值点;

则。定理(充分条件)

设

(1)为D的一个内点;(2)

在二次连续可微;(3);(4)正定;则为的严格局部极小点。对一般n元函数，由条件

得到一非线性方程组，解它相当困难。对于不可(bùkě)微函数，当然谈不上使用这样的方法。迭代算法根据一阶必要条件，令函数梯度等于零，求得驻点；然后用充分条件进行判别，求出所要的最优解。共七十七页大致想法：为了求函数f(x)

的最优解，首先给定一个初始估计然后按某种规则(即算法)找出比更好的解再按此种规则找出比更好的解如此即可得到一个解的序列若这个解序列收敛(shōuliǎn)于该问题的最优解x*，则算法有效。无约束优化问题(P1)——约束优化问题问题(P2)——迭代法的基本(jīběn)思想共七十七页步长因子(yīnzǐ)搜索方向(fāngxiàng)：可行方向、下降方向迭代法的基本思想：希望找到迭代序列{xk}，其迭代格式为定义：（可行方向）设D为可行域，在点处，对于非零向量d

，若存在实数，使得，则称d

为f(x)在点的可行方向。xkxk+1dkak共七十七页注：根据(gēnjù)泰勒公式即当时，总存在使得当时，恒有，我们称满足的方向为在处的一个下降方向。定义：（下降方向）在点处，对于非零向量d

，若存在实数，使得