非线性规划约束规范作业_第1页
非线性规划约束规范作业_第2页
非线性规划约束规范作业_第3页
非线性规划约束规范作业_第4页
非线性规划约束规范作业_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

在 KKT 条件下 讨论非线性规划的约束规范 文章目录 一 引理论述 二 KKT 条件 三 约束规范及其相互关系 运筹学作业 纪旭 2012201742 1 一 引理论述 本文主要考虑如下形式的约束优化问题 min f x s t gi 0 1 2 m 其中 表示可行域 S S gi x n g i 0 1 2 m 在可行解 处满足 0 的约束条件称为 处的有效约束 active constraint S 在 处 x gi xx 的切锥可以表示为 S 在 处的线性化锥 x y t k 0 y k y 满足x t ky k k x 可以表示为 x y n g i x y 0 gi x 是有效约束 用图表示如下 切锥由 直接定义 而线性规划锥则依赖于描述集合 的函数 因此 两者 x x gi 并未完全一致 虽然不一定成立 但是总是成立的 x x x x 对于原问题 引入 Lagrange 乘子 得到 L0 f x m i 1 igi x 称为 Lagrange 函数 0 L0 二 Karush Kuhn Tucker 条件 由以上引理 可以得到描述原问题的最优性必要条件的定理 设 为原问题的局部最优解 并且目标函数 f 均在 处可微 xRn R 1 2 m x 若 co 则存在 Lagrange 乘子 满足 x x R m xL0 1 g i 0 i 1 2 m 0gi 0 gi 0 运筹学作业 纪旭 2012201742 2 上式一般称为 Karush Kuhn Tucker 条件或者 KKT 条件 该条件是 为原问题的局部最 优解的必要条件 但不是充分条件 举反例加以说明 考虑问题 min f 2 s t 1 12 2 0 2 12 22 1 0 由于 取 则 KKT 条件成立 但是 不是该问 f 0 1 g 1 0 1 1 0 x 题的局部最优解 KKT 条件说明 在局部最优解 处目标函数的梯度乘以 1 后得到的向量包含在由 x f 有效约束函数的梯度所张成的凸多面锥中 如下图所示 g i x 从 KKT 表达式我们看出 在假设条件 下 KKT 条件是原问题最优性条 x co x 件 一般称这样的假设条件为约束规范 约束规范 constraint qualification 它是 KKT 条件成为最优 性必要条件不可或缺的条件 但同时有特殊情况 当原问题为凸规划时 在约束规范下 KKT 条件也是全局最优性 的充分条件 三 约束规范及相互关系 接下来来讨论保证 KKT 条件最优性必要条件的其他约束规范 然后讨论它们之间的关 系 首先给出没有约束规范情况下的最优性必要条件 Fritz John 条件 设点 为原问题的局部最优解 目标函数 f 与约束函数 xRn R gi 均在 处可微 则存在 满足 1 2 m x 1 2 m 运筹学作业 纪旭 2012201742 3 0 f m i 1 g i 0 i 1 2 m gi 0 gi 0 i 1 2 m 0 1 2 0 0 0 以上式子称为 Fritz John 条件 KKT 条件可以看做它的特殊情形 即的情形 0 0 原问题只包含不等式约束 对于这个问题 具有代表性的约束规范有 1 线性独立约束规范线性独立约束规范 linear independence constraint qualification 向量组 有 g i 效约束 线性无关 2 Slater 约束规范约束规范 Slater s constraint qualification 有效约束 均为凸函数 并且 g i 存在满足i 1 2 m x0 x0 0 3 Cottle 约束规范约束规范 Cottle s constraint qualification 存在向量 满足 y Rn 为有效约束 y 0 4 Abadie 约束规范约束规范 Abadie s constraint qualification x x 5 GuignardGuignard 约束规范约束规范 Guignard s constraint qualification co x x 其中 Guignard 约束规范正是上文 KKT 条件叙述中所假定的约束规范 通过阅读相关文献 得到它们之间的关系如下的关系 1 若线性独立约束规范或 Slater 约束规范成立 则 Cottle 约束规范也成立 2 若 Cottle 约束规范成立 则 Abadie 约束规范也成立 若 Abadie 约束规范成立 则 Guignard 约束规范也成立 证明不加以赘述 综合上两条结论 画出关系图 在这些约束规范中 Guignard 约束规范是最弱的条件 因此从理论上来讲 Guignard 约束规

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论