版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、o 重点重点学习库恩库恩-塔克条件塔克条件(Kuhn Tucker, K-T条件),学会学会计算库恩库恩-塔克塔克点点(K-T点)。其他次要。 第2章 最优化的基础理论和基本方法2 有约束最优化2.2 一般约束情况一般约束情况问题:min f(x), xRn (2-1) st ci(x1, x2, ., xn) = 0, i E ci(x1, x2, ., xn) 0, i I其中E和I分别表示等式和不等式约束的指标集, E= 1, 2, ., l I= l+1, l+2, ., l+m E I = (空集)考虑问题的局部解。考虑最优性条件考虑问题的局部解。考虑最优性条件。看两个例子:不等式约
2、束不等式约束。o 例1 min f(x) = x1 + x2 st c1(x) = x12 + x2 2 - 2 0 f(x*) c1(x*)x* f(x)f(x) = x1 + x2 = -2 c1(x)c1(x) 0D:O例例1 min f(x) = x1 + x2 st c1(x) = x12 + x2 2 - 2 0可见满足: 非负条件非负条件 * 0 叫做松弛互补条件松弛互补条件 对应不等式约束。对应不等式约束。1. 由图解法, x*为最优解,当然也是局部解。局部解。2. 局部解局部解x*在在D的边界上,约束C1起作用起作用: c1(x*) = 0。 f(x*) + * c1(x*)
3、 =0* 0* c1(x*) = 0 f(x*)=0f(x) = (x1 -1)2 + x22 c1(x*)Dx*O例例2 min f(x) = (x1 -1)2 + x22 st c1(x) = x12 + x2 2 - 2 01. D内的点x* = (1,0)T为最优解,当然也是局部解。局部解。2. 约束C1不起作用不起作用: c1(x*)0。 3. x*是无约束问题局部解。所以:f(x*) =0。 f(x*) + * c1(x*) =0 * = 0 * c1(x*) = 0 满足非负条件非负条件 满足松弛互补条件松弛互补条件 对应不等式约束。对应不等式约束。起作用约束和不起作用约束(对不
4、等式约束)在可行点x处起作用约束起作用约束:使得ci (x) = 0, i I的不等式约束ci(x)。不起作用约束不起作用约束:使得ci(x) 0, i I的不等式约束ci(x)。(这是由局部解的局部性决定的,只考虑x的邻域。)引入符号I(x):表示在可行点x处的所有起作用的不等式约束的下标,即I(x)=i | iI,ci(x)=0。综合等式约束、不等式约束情况一般约束优化的局部解的必要条件一般约束优化的局部解的必要条件库恩库恩-塔克定理塔克定理 对于一般约束问题对于一般约束问题(2-1),设,设x=x*为问题的局部解。为问题的局部解。又设又设f(x)、 ci(x)在在x*处有连续偏导数,处有
5、连续偏导数,n维向量维向量组组 ci(x*), i EI(x*) 线性无关。则存在常数向量线性无关。则存在常数向量 * =( 1*, 2*, , l+m*)T,使如下条件成立:,使如下条件成立:0*)(*)(*)*,(1mliiixxcxfxL,.,2 , 10*)(lEixci,.,2, 10*)(mlllIixciIii 0*Iixcii 0*)(*乘数。拉imliiixcxfxL, )()(),(1令令说明o 上述5式称为库恩库恩-塔克条件塔克条件(Kuhn-Tucker) ,由二人于1951给出。o 其中的第4式称为非负条件非负条件,只对不等式约束对应只对不等式约束对应的拉格朗日乘子的
6、拉格朗日乘子 成立成立。 (等式等式约束对应的约束对应的 可正可负可正可负,正像在前面等式约束的例题中的那样) 。o 第5式称为互补松弛条件互补松弛条件,针对不等式约束的(实际上对等式约束也成立,但把等式情况包括进来是多余的)。o 第1式中的和式对应等式约束和不等式约束两部分.o 满足库恩-塔克条件的点x*简称为K-T点。点。例 求k-T点(p252),252(01)(09)()(min21222211221薛毅薛毅点。点。的的求约束优化问题求约束优化问题pTKxxxcxxxcstxxxf) 1()9(),(212221221xxxxxxxL点。唯一的为该问题TK)3, 0(T种情况讨论,分为
7、是否求解过程可以按40,该点是问题可能的局部解。该点是问题的最优解(下页图)(根据其他方法可知)K-T点:(0,-3)To=0,矛盾方程。,矛盾方程。o=0,必须,必须=-1,不满足非负条件。,不满足非负条件。o0,0,由松弛互补条件可解得,由松弛互补条件可解得见书见书p253,这时让这时让2L =0的两个式子相减,可见总是的两个式子相减,可见总是0 ,不,不满足非负条件。满足非负条件。o0,=0,n 有一个(1+ )x1 = 0,由此只有x1 = 0(否则不满足非负条件)。n 可知x2= +3或 -3。前者不满足c2约束。故x2=-3. 所以,x=(0,-3))T 为该优化问题的 K-T点。
8、该点是最优解。f=0f=-5对于凸优化问题o 定理定理 如果问题(2-1)为一个凸优化问题(即 可行域D是凸集,目标函数f是D上的凸函数),又设目标函数f(x)和约束函数ci(x)都存在一阶连续偏导数,则问题的K-T点是问题的最优解。例子:上例。所以,该点是最优解。最优化的基本理论和基本方法o 5个重要定理最优化的基本理论。n 无约束 3个,有约束 2个。n 历史上的最优化3个重要成果。n 凸优化:驻点凸优化:驻点/K-T点是最优解是最优解。o 是理论指导和基本方法。n 准确方法,但不够实用,对规模大的或复杂的问题。 (以后将讲实用方法,即优化算法,为近似方法。)n 有时不能确定是否为局部解(充分条件不满足时)。费马定理费马定理1629拉格朗日定理拉格朗日定理1788库恩塔克定理库恩塔克定理1951大约相隔大约相隔150年。年。作业o求
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 初中七年级英语下册Unit 1 Section A词汇语法与句型教学设计
- 高二英语听力教学设计:仿真特训中推理判断与信息重组策略的落实
- 小学四年级英语Cool clothes教案
- 八年级地理教学设计:中国气候类型判读与季风显著性中考突破
- 高二化学选择性必修1第三章第1、2节化学反应速率与影响因素教学设计
- 高考语文二轮复习修辞手法赏析教学设计
- 高中化学选择性必修3 甲醛与酮的性质及应用教学设计
- 小学六年级心理健康《学会感恩 与爱同行》教学设计
- 初中八年级数学《认识一次函数》第一课时教学设计
- 小学三年级综合实践活动《时间都去哪了》教学设计
- 殡葬服务质量考核细则
- 泌尿外科急诊经皮肾穿刺造瘘手术教学查房
- 2026年中国酒吧行业市场现状、未来前景预测及行业发展趋势
- 2026年医疗器械监督管理条例培训试卷附答案
- 心脏瓣膜病护理查房
- 多资产配置全景研究系列控波御险:多资产组合风险管理方法论
- 《脓毒症和脓毒性休克管理国际指南2026》解读课件
- 新版西师版五年级上册数学全册教案(完整版)教学设计含教学反思
- 2025年四川省成都市新都区中考数学一诊试卷
- 人工智能驱动下的人才竞争力评价与专业演变研究
- 2026-2030中国电信反欺诈行业前景调查及未来趋势洞察研究报告
评论
0/150
提交评论