1 / 14
文档名称:

第五章-01 约束最优条件课件.ppt

格式:ppt   大小:2,483KB   页数:14页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第五章-01 约束最优条件课件.ppt

上传人:yuzonghong1 2022/11/25 文件大小:2.42 MB

下载得到文件列表

第五章-01 约束最优条件课件.ppt

相关文档

文档介绍

文档介绍:该【第五章-01 约束最优条件课件 】是由【yuzonghong1】上传分享,文档一共【14】页,该文档可以免费在线阅读,需要了解更多关于【第五章-01 约束最优条件课件 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。*
Chapter5
约束问题的最优性条件
信息与计算科学系
*
数学模型
minf(x)
(x)≥0
……
sm(x)≥0
h1(x)=0
……
hl(x)=0
与无约束问题中有一阶必要条件▽f(x)=0一样,在约束问题中我们也要找出这种问题的最优解必须满足的条件,从而决定迭代过程何时终止!
*

起作用约束(有效约束)
对容许点来说,若有不等式约束si(x)≥0变成等式,即si()=0,则该不等式约束称为关于容许点的一个起作用约束;若si()>0则称之为这个容许点的不起作用约束。
x
x
x
则对点(1,0)T来说1,4为有效约束,2,3为不起作用约束
A
B
x1
x2
·P
例:某问题的约束函数分别为:
s1(x)=1-x12-x22≥0
s2(x)=x1-x2≥0
s3(x)=x1≥0
s4(x)=x2≥0
*
容许下降方向
方向d既是点x’处的容许方向,又是点x’处的下降方向
(1)如果某点x’不是极小点,则继续寻优时的搜索方向就应该从该点的一个可行下降方向上去找(因为这样就既保证函数值的下降,又能确保找到的好点是一个可行的)
(2)如果某点x*是一个极小点,则在该点就不会有可行下降方向。因否则若有的话比如d,则x*沿着d稍微走一点点就会得到一个可行点,且该点的函数值必x*的函数值小。这当然与x*为极小点矛盾!
*

引理
设不等式约束问题的可行域为D={x|si(x)≥0,i=1:m}
x’为任一容许点,
记I={i|si(x’)=0,i=1:m}
当iI,si(x)在x’处有一阶偏导数,且▽si(x’)Td>0
当iI,si(x)在x’处连续,
则d是x’处的一个容许方向
Proof
对iI:由▽[-si(x’)]Tp<0知:
p是函数-si(x)在x’点处的下降方向。
从而存在一个小正数i,对t(0,i),总有
-si(x’+tp)<-si(x’)=0,即si(x’+tp)>0
对iI,si(x’)>0,
由si(x)在x’处连续,故存在一个小正数
i,使t(0,i),均有si(x’+tp)>0
取=min{1,…,m},
对t(0,),均有si(x’+tp)>0,i=1:m。
*
由这个引理可知道
若x*是一个极小点,
则在x*处不会有方向p满足
也就是说,这个不等式组必无解。
*
Kuhn-Tucker(库恩-塔克)定理
设x*为不等式约束问题的一个极小点
函数f(x),s1(x)…,sm(x)在x*处都有一阶偏导数
I={i|si(x*)=0,i=1:m},
当iI,▽si(x*)线性无关
则存在实数1,…,m,满足:
▽f(x*)-[1▽s1(x*)+2▽s2(x*)+…+m▽sm(x*)]=0
isi(x*)=0,i=1:m
i≥0,i=1:m
K-T条件
*
为证明原结论还需说明0必不为0(即>0)
则由0▽f(x*)-∑[i▽si(x*)]=0,iI
知▽si(x*),iI,线性相关,
与已知矛盾!
这样在上式两端同时除以0
▽f(x*)-∑[(i/0)▽si(x*)]=0
即得结论。
满足K-T条件的点称为K-T点。
事实上,若0为0,
*
minf(x)=(x1-2)2+x22
(x)=x1-x22≥0
s2(x)=-x1+x2≥0
对点x(2)=(1,1)T,
在该点处s1(x),s2(x)都是起作用约束
在该点处f,s1,s2的梯度分别是
故x(2)是K-T点
*
备注
如同无约束问题中的一阶必要条件▽f(x)=0一样,
K-T条件仅是一个必要条件,而非充分。但对于绝大
多数的求解约束问题的数值计算方法来说,只要求出
满足K-T条件的点就达到目的了。