不等式约束问题.ppt

《不等式约束问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、不等式约束问题线性不等式约束优化问题一般性不等式约束优化问题不等式约束在给定点的分类及其作用设满足所有约束，即如果是处不起作用的约束，则对任意的都存在满足所以，构造可行方向时不用考虑不起作用约束在处不起作用约束：在处起作用约束：对起作用约束指标集的约定对任何满足不等式约束的可行解，只要不特别说明，总是假定其前个约束是起作用约束，其它约束是不起作用约束，即线性不等式约束问题线性不等式约束可行方向的充要条件理由：所以因为对于线性不等式约束，是可行解处的可行方向的充要条件是下降方向的充分条件对任意的，如果，就是在处的下降方向理由：由于，一定存在满足不是下降方向必要条件的原因是下降方向是上升方

2、向的性质不定是下降方向充要条件的一个充分条件是的某个邻域内的凸函数理由：凸函数的一阶必要条件其中是保证上述凸性的邻域，令不是下降方向代入上式可得构造线性不等式约束的可行下降方向基本假定基本途径的可行解，起作用约束的系数向量线性无关即矩阵的列向量线性无关分析线性方程组的解的情况其中是方程组的变量是满足线性不等式约束线性方程组的解的各种可能的情况因为的列向量线性无关，有逆，可以定义情况1、情况3、方程组无解情况2、但存在满足并且理由：情况1的例子可行集将负梯度投影到所有起作用约束的零空间，如上图的的零空间（满足的全体向量）的投影矩阵其中是单位矩阵性质1、性质2、性质3、即情况1（）的可行下

3、降方向理由：利用性质1、2可得由下降方向的充分条件可知是下降方向利用性质3可得由可行方向的充要条件可知是可行方向情况2的例子：可行集将负梯度投影到所有正的起作用约束的零空间，如情况2（）的可行下降方向其中是的第个列向量，即理由：第个分量等于1（可行）（下降）情况3的例子：可行集不存在满足的可行方向情况3（）的结论不存在满足的可行方向理由：是可行方向（充要条件）注意：不存在满足的可行方向在处不存在可行下降方向只有是的某个邻域内的凸函数，两者等价不能说是局部最优解！线性不等式约束问题最优解的必要条件对于线性不等式约束的优化问题如果是局部最优解，是以处起作用约束（Kuhn-Tucker条件）

4、的系数向量为列向量构成的矩阵，并且假定其列向量线性无关，那么一定存在满足注意：的列向量线性无关是上述结论成立的条件！满足上述条件的称为K-T解1）确定初始可行解2）构造处起作用约束对应的矩阵，计算3）如果，停止，是K-T解线性不等式约束问题的投影梯度法否则按照情况1或情况2对应的方法确定可行下降方向4）在处沿方向进行一维搜索确定用替换，然后回到2）继续迭代可行步长应该满足由于，所以最大可行步长为线性不等式约束一维搜索的最大可行步长等价于注意到对起作用约束有，所以如果，则有不保证下降！一般性不等式约束问题一般性不等式约束优化问题假定满足以下条件：列线性无关（起作用约束）（不起作用约束）如

5、果，则有以上条件和对线性不等式约束所假定的条件一致非线性不等式约束可行方向的充分条件理由：不是必要条件的原因：可行集不可行可行集可行线性约束非线性约束非线性不等式约束和线性不等式约束的本质区别如果满足适合线性不等式约束的可行下降方向的条件，即一定存在，使满足因此是非线性不等式约束的可行下降方向线性和非线性不等式约束可行下降方向之间的关系理由：已知条件因为所以其中由于，只要的分量都大于0，另一方面，因为以及每个分量就大于0，即只要的每个分量充分小，就会有非线性不等式约束问题可行下降方向的存在性定理其中如果（等价于方程组无解）或者有小于0的分量，一定存在满足，令根据线性和非线性不等式约束可

6、行下降方向之间的关系，此时在处一定存在可行下降方向考虑起作用约束构成的线性方程组不等式约束优化问题最优解的必要条件如果是上述问题的局部最优解，线性方程列线性无关等价表述结论问题条件组一定存在分量非负的解如果是上述问题的局部最优解，向量一定满足线性方程组，并且其每个分量都不小于0（Kuhn-Tucker条件）一般性等式和不等式约束问题假设条件：已知满足1）2）线性无关优化模型如果是最优解，还必须满足什么条件？要回答的问题：存在的个分量，记为，满足线性无关线性无关线性无关有逆矩阵隐函数定理邻域以及在该邻域可导的函数满足如果有逆矩阵，那么存在的例如，线性函数当有逆矩阵时那么和就是下面原问题的

7、局部最优解记如果是下面不等式约束问题的局部最优解由于如果是以上问题的最优解，所有起作用约束的梯度线性无关，那么一定存在满足问题：1）如何用原问题的表示以上含有未知函数梯度的等式？2）假设条件能否保证上述梯度的线性无关性？的K-T条件问题1）的解决途径之一问题1）的解决途径之二例如，线性函数问题1）的解决途径之三将前面求出的梯度代入记为问题1）的结论问题2）的解决途径线性无关是否有非零解上面等式方程的左边可写成利用令已知线性无关线性无关的K-T条