不等式约束问题.ppt
《不等式约束问题.ppt》由会员分享,可在线阅读,更多相关《不等式约束问题.ppt(66页珍藏版)》请在三一办公上搜索。
1、不等式约束问题,线性不等式约束优化问题,一般性不等式约束优化问题,不等式约束在给定点的分类及其作用,设 满足所有约束,即,如果 是 处不起作用的约束,则对任,意的 都存在 满足,所以,构造可行方向时不用考虑不起作用约束,在 处不起作用约束:,在 处起作用约束:,对起作用约束指标集的约定,对任何满足不等式约束的可行解,只要不特别说明,总是假定其前 个约束是起作用约束,其它约束是不起作用约束,即,线性不等式约束问题,线性不等式约束可行方向的充要条件,理由:,所以,因为,对于线性不等式约束,是可行解 处的可行方向的充要条件是,下降方向的充分条件,对任意的,如果,就是 在 处的下降方向,理由:,由于,
2、一定存在 满足,不是下降方向必要条件的原因,是下降方向,是上升方向,的性质不定,是下降方向充要条件的一个充分条件,是 的某个邻域内的凸函数,理由:,凸函数的一阶必要条件,其中 是保证上述凸性的邻域,令,不是下降方向,代入上式可得,构造线性不等式约束的可行下降方向,基本假定,基本途径,的可行解,起作用约束的系数向量线性无关,即矩阵 的列向量线性无关,分析线性方程组 的解的情况,其中 是方程组的变量,是满足线性不等式约束,线性方程组 的解的各种可能的情况,因为 的列向量线性无关,有逆,可以定义,情况1、,情况3、,方程组无解,情况2、,但存在 满足,并且,理由:,情况1的例子,可行集,将负梯度投影
3、到所有起作用约束的零空间,如上图的,的零空间(满足 的全体向量)的投影矩阵,其中 是单位矩阵,性质1、,性质2、,性质3、,即,情况1()的可行下降方向,理由:利用性质1、2可得,由下降方向的充分条件可知是下降方向,利用性质3可得,由可行方向的充要条件可知是可行方向,情况2的例子:,可行集,将负梯度投影到所有正 的起作用约束的零空间,如,情况2()的可行下降方向,其中 是 的第 个列向量,即,理由:,第,个分量等于1,(可行),(下降),情况3的例子:,可行集,不存在满足 的可行方向,情况3()的结论,不存在满足 的可行方向,理由:,是可行方向,(充要条件),注意:,不存在满足 的可行方向,在
4、 处不存在可行下降方向,只有 是 的某个邻域内的凸函数,两者等价,不能说 是局部最优解!,线性不等式约束问题最优解的必要条件,对于线性不等式约束的优化问题,如果 是局部最优解,是以 处起作用约束,(Kuhn-Tucker条件),的系数向量为列向量构成的矩阵,并且假定其列,向量线性无关,那么一定存在 满足,注意:的列向量线性无关是上述结论成立的条件!,满足上述条件的 称为K-T解,1)确定初始可行解,2)构造 处起作用约束对应的 矩阵,计算,3)如果,停止,是K-T解,线性不等式约束问题的投影梯度法,否则按照情况1或情况 2对应的方法确定可行,下降方向,4)在 处沿方向 进行一维搜索确定,用 替
5、换,然后回到 2)继续迭代,可行步长应该满足,由于,所以最大可行步长为,线性不等式约束一维搜索的最大可行步长,等价于,注意到对起作用约束有,所以,如果,则有,不保证下降!,一般性不等式约束问题,一般性不等式约束优化问题,假定 满足以下条件:,列线性无关,(起作用约束),(不起作用约束),如果,则有,以上条件和对线性不等式约束所假定的条件一致,非线性不等式约束可行方向的充分条件,理由:,不是必要条件的原因:,可行集,不可行,可行集,可行,线性约束,非线性约束,非线性不等式约束和线性不等式约束的本质区别,如果 满足适合线性不等式约束的可行下降,方向的条件,即,一定存在,使,满足,因此 是非线性不等
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 不等式 约束 问题
链接地址:https://www.31ppt.com/p-5048301.html