工程优化第2章-4

课件下载邮箱邮箱名：

xdgongchengyouhua@126.com(xd+工程优化的小写全拼)密码：xidian123多元函数的梯度及其Hesse矩阵等高线二次函数多元函数的极值及其判别条件凸集、凸函数、凸规划几个重要的不等式第2章基础知识

由一元函数的几何图形知：f(x)是凸函数，任意给定曲线上两点A，B，则弦AB在与弧AB之上，用数学式子表示：

凸函数弦AB的方程：令则上式可写为：所以：

定义（凸函数）:

设集合DRn为凸集，函数f:DR,若

α(0,1)，均有则称f(x)为凸集D上的凸函数。若进一步有上面不等式以严格不等式成立，则称f(x)为凸集D上的严格凸函数。当-f(x)为凸函数(严格凸函数)时，则称f(x)为凹函数

(严格凹函数)。严格凸函数凸函数严格凹函数凸函数----推广到多元函数例：设1)若A半正定，则在上是凸函数；2)若A正定，则在上是严格凸函数。证明:

凸函数----推广到多元函数性质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)}是否是凸函数？凸函数的性质性质1：

f(x)

为凸集S上的凸函数S上任意有限点的凸组合的函数值不大于各点函数值的凸组合。

证明参见文中定理2.10的证明。P39作业定理(一阶条件):

设D

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

在D上可微，则

(1)f在D上为凸函数

恒有

(1)(2)

f在D上为严格凸函数

恒有

(2)

证明:见书中定理2.11(P27)凸函数的判定定理定理5（二阶条件）:

设D

Rn为含有内点的非空凸集，函数f:DR在D上二次可微，则

a)f在D上为凸函数xD，2f(x)

半正定；

b)若xD，2f(x)

正定，则f在D上为严格凸函数。证明:见书中定理2.12（P28）由一阶条件和多元函数的泰勒展开式可证。回忆：一个矩阵半正定充要条件是所有主子式非负；一个矩阵正定充要条件是所有顺序主子式为正。凸函数的判定定理例：设二次函数(1)：若为半定矩阵，在中为凸函数；(2)：若为正定矩阵，在中为严格凸函数。例：判断f(x)=5x12-6x1x2+5x22在凸集D上是否是凸函数？凸函数的判定定理的顺序主子式都是正的，所以正定，因此f(x)在凸集D上是严格凸函数。由于故证明为凸函数。也是凸函数。根据性质2，为凸函数。

看下述各式是否成立：证明：首先用定义证明是凸函数，即对任意和例:

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

取什么值，总有为凹函数。

因此

从而用同样的方法可以证明用一阶条件证明只需证任意选取两点或或或不管a1、a2、b1、b2取什么值，上式均成立，从而得证。是凹函数，

要证

例:

试证明为凹函数。其Hesse矩阵处处负定，故为(严格)凹函数。

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

试证明为凹函数。定义（凸规划）:

考虑如下非线性规划当都是凸函数时,称规划为凸规划凸规划性质1:

设(1)为凸规划，则

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

ii)(1)的最优解集是凸集；

iii)(1)的任何局部极小点都是全局极小点。

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

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

数，则(1)的全局极小点是唯一的。

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

非线性规划的局部最优解不一定是全局最优解,其可行解和最优解集也不一定是凸集,甚至不是连通集.如果是凸规划,就有很多好的性质。凸规划的性质性质3：设(1)为凸规划，则为(1)的最优解

的充要条件为：，有利用凸函数的一阶判别条件（证明参见文中定理2.15）凸规划的性质多胞形：有限个点的凸包闭半空间是凸的多面体、极点、极方向闭半空间：称为正闭半空间;称为负闭半空间;H+和H-统称为闭半空间。多面体：有限个闭半空间的交多面体的极点（顶点）：多面体、极点、极方向

对任意xS，不存在S

中的另外两个点x1和x2，及极方向：方向d

不能表示为两个不同方向的组合使方向：xS,dRn,d

0及总有时，称d1和d2同方向。当定理（极点特征）设A

满秩，x

是S极点的充分必要条件是:存在分解A=[B,N]，其中B为m阶非奇异矩阵，使xT=[xBT,xNT],这里xB=B-1b≥0,xN=0.S中必存在有限多个极点。(≤Cnm)定理（极方向特征）设A=[p1,p2,…,pn]满秩，d

是S

极方向的充分必要条件是:存在分解A=[B,N]，其中B为m阶非奇异矩阵，对于N中的列向量pj

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

,

dN=(0,...,1,…,0)TS中必存在有限多个极方向。(≤(n-m)Cnm)多面体S={xRnAx=b,x≥0}的极点和极方向定理（表示定理）考虑上述多面体S，设A满秩，

为所有极点，

为所有极方向。那么，对于xS，且多面体S={xRnAx=b,x≥0}的极点和极方向使

一个凸集有非空的相对内部；一个凸集是连通的并且在任意点具有可行方向；一个多面体的凸集可以由一个有限的极点和极方向的集合来刻画；凸集上凸函数的全局极小值的存在可以非常方便的按照收缩方向来描述；为什么凸在最优化中如此特殊

一个凸函数的局部极小点都是全局极小点；一个非凸函数可以被“凸化的”同时保持了全局极小值的最优性；一个凸函数是连续的并且具有良好的可微性；闭凸锥关于极是自对偶的；凸且下半连续的函数关于共轭是自对偶的。为什么凸在最优化中如此特殊向量运算：x,yRn

x,y

的内积：<x,y>=xTy=xiyi=x1y1+x2y2+…+xnyn

x,y

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

的长度：‖x‖=[xTx](1/2)

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

定理（Cauchy-Schwarz不等式）重要的不等式定理1设A为n阶对称正定矩阵，则，恒有等号成立当且仅当x与线性相关;

等式成立当且仅当x

与y线性相关。其中表示向量的内积。定理3：设A为n阶对称正定矩阵，m与M分别为A的最小与最大特征值，则，恒有定理2：设A为n阶对称正定矩阵，m与M分别为A的最小与最大特征值，则，恒有

重要的不等式1/M与

1/m分别为A-1的最小与最大特征值范数

（A正定）椭球范数范数

范数

范数

范数----向量范数定义1：方阵A的范数是指与A相关联并记做的一个非负数，它具有下列性质：对于都有，而时；对于任意，都有；；；若还进一步满足：则称之为与向量范数相协调（相容）的方阵范数.

范数----矩阵范数定义2:设与是上的两个范数，若存在，使得，则称范数与是等价的。容易证明：其中是的最大特征值，而是的最小特征值。范数----范数等价中所有向量范数均等价。Cauchy-Schwarz不等式

当且仅当与线性相关时，等式成立。关于范数的几个重要不等式定理（Cauchy-Schwarz不等式）

等式成立当且仅当x

与y线性相关。当且仅当与线性相关时，等式成立。关于范数的几个重要不等式定理4：设A是正定矩阵，则当且仅当与线性相关时，等式成立。Cauchy-Schwarz不等式

设A是n阶正定矩阵，则等号成立当且仅当与线性相关。关于范数的几个重要不等式定理1设A为n阶对称正定矩阵，则，恒有等号成立当且仅当x与线性相关;定理5：Young不等式：假定p与q都是大于1的实数，且满足，则，有

当且仅当时，等式成立。关于范数的几个重要不等式Hölder不等式其中p与q都是大于1的实数，且满足.Minkowski不等式

关于范数的几个重要不等式

定义3（序列收敛）：设是中的一个向量序列，，如果，存在正整数K，使得当时，有，则称序列收敛到