不等式约束问题.ppt

不等式约束问题,线性不等式约束优化问题,一般性不等式约束优化问题,不等式约束在给定点的分类及其作用,设 满足所有约束，即,如果 是 处不起作用的约束，则对任,意的 都存在 满足,所以，构造可行方向时不用考虑不起作用约束,在 处不起作用约束：,在 处起作用约束：,对起作用约束指标集的约定,对任何满足不等式约束的可行解，只要不特别说明，总是假定其前 个约束是起作用约束，其它约束是不起作用约束，即,线性不等式约束问题,线性不等式约束可行方向的充要条件,理由：,所以,因为,对于线性不等式约束，是可行解 处的可行方向的充要条件是,下降方向的充分条件,对任意的，如果，就是 在 处的下降方向,理由：,由于，一定存在 满足,不是下降方向必要条件的原因,是下降方向,是上升方向,的性质不定,是下降方向充要条件的一个充分条件,是 的某个邻域内的凸函数,理由：,凸函数的一阶必要条件,其中 是保证上述凸性的邻域，令,不是下降方向,代入上式可得,构造线性不等式约束的可行下降方向,基本假定,基本途径,的可行解，起作用约束的系数向量线性无关,即矩阵 的列向量线性无关,分析线性方程组 的解的情况,其中 是方程组的变量,是满足线性不等式约束,线性方程组 的解的各种可能的情况,因为 的列向量线性无关，有逆，可以定义,情况1、,情况3、,方程组无解,情况2、,但存在 满足,并且,理由：,情况1的例子,可行集,将负梯度投影到所有起作用约束的零空间，如上图的,的零空间（满足 的全体向量）的投影矩阵,其中 是单位矩阵,性质1、,性质2、,性质3、,即,情况1（）的可行下降方向,理由：利用性质1、2可得,由下降方向的充分条件可知是下降方向,利用性质3可得,由可行方向的充要条件可知是可行方向,情况2的例子：,可行集,将负梯度投影到所有正 的起作用约束的零空间，如,情况2（）的可行下降方向,其中 是 的第 个列向量，即,理由：,第,个分量等于1,（可行）,（下降）,情况3的例子：,可行集,不存在满足 的可行方向,情况3（）的结论,不存在满足 的可行方向,理由：,是可行方向,（充要条件）,注意：,不存在满足 的可行方向,在 处不存在可行下降方向,只有 是 的某个邻域内的凸函数，两者等价,不能说 是局部最优解！,线性不等式约束问题最优解的必要条件,对于线性不等式约束的优化问题,如果 是局部最优解，是以 处起作用约束,（Kuhn-Tucker条件）,的系数向量为列向量构成的矩阵，并且假定其列,向量线性无关，那么一定存在 满足,注意：的列向量线性无关是上述结论成立的条件！,满足上述条件的 称为K-T解,1）确定初始可行解,2）构造 处起作用约束对应的 矩阵，计算,3）如果，停止，是K-T解,线性不等式约束问题的投影梯度法,否则按照情况1或情况 2对应的方法确定可行,下降方向,4）在 处沿方向 进行一维搜索确定,用 替换，然后回到 2）继续迭代,可行步长应该满足,由于，所以最大可行步长为,线性不等式约束一维搜索的最大可行步长,等价于,注意到对起作用约束有，所以,如果，则有,不保证下降！,一般性不等式约束问题,一般性不等式约束优化问题,假定 满足以下条件：,列线性无关,（起作用约束）,（不起作用约束）,如果，则有,以上条件和对线性不等式约束所假定的条件一致,非线性不等式约束可行方向的充分条件,理由：,不是必要条件的原因：,可行集,不可行,可行集,可行,线性约束,非线性约束,非线性不等式约束和线性不等式约束的本质区别,如果 满足适合线性不等式约束的可行下降,方向的条件，即,一定存在，使,满足,因此 是非线性不等式约束的可行下降方向,线性和非线性不等式约束可行下降方向之间的关系,理由：,已知条件,因为,所以,其中,由于，只要 的分量都大于0，,另一方面，因为 以及,每个分量就大于0，即,只要 的每个分量充分小，就会有,非线性不等式约束问题可行下降方向的存在性定理,其中,如果（等价于方程组无解）或者,有小于0的分量，一定存在 满足,，令,根据线性和非线性不等式约束可行下降方向之间的关系，此时在 处一定存在可行下降方向,考虑起作用约束构成的线性方程组,不等式约束优化问题最优解的必要条件,如果 是上述问题的局部最优解，线性方程,列线性无关,等价表述,结论,问题,条件,组 一定存在分量非负的解,如果 是上述问题的局部最优解，向量,一定满足线性方程组,，并且其每个分量都不小于0,（Kuhn-Tucker条件）,一般性等式和不等式约束问题,假设条件：已知 满足,1）,2）线性无关,优化模型,如果 是最优解，还必须满足什么条件？,要回答的问题：,存在 的 个分量，记为，满足,线性无关,线性无关,线性无关,有逆矩阵,隐函数定理,邻域 以及在该邻域可导的函数 满足,如果 有逆矩阵，那么存在 的,例如，线性函数,当 有逆矩阵时,那么 和 就是下面原问题的局部最优解,记,如果 是下面不等式约束问题的局部最优解,由于,如果 是以上问题的最优解，所有起作用约束的梯度 线性无关，那么一定存在 满足,问题：1）如何用原问题的 表示以 上含有未知函数梯度的等式？2）假设条件能否保证上述梯度的线性无关性？,的K-T条件,问题 1）的解决途径之一,问题 1）的解决途径之二,例如，线性函数,问题 1）的解决途径之三,将前面求出的梯度代入,记为,问题 1）的结论,问题2）的解决途径,线性无关,是否有非零解,上面等式方程的左边可写成,利用,令,已知 线性无关,线性无关,的K-T条件,如果 是上述问题的最优解，且满足：,则一定存在 和 成立,1）,2）线性无关,Kuhn-Tucker定理,如果 是下述问题的最优解,并且在 处等式约束和所有起作用的不等式约束的梯度线性无关，则一定存在 和 满足,标准线性约束的简约梯度法,标准线性约束优化问题（可表示任意线性约束）,已知可行解 满足以下条件：,1）存在2）的每个分量都大于零（非退化情况）,于是 是下述问题可行解（）,并且，（对应的约束是不起作用约束）,求简约梯度,已知：,对于线性不等式约束的优化问题,定理4.5.3（教材134页）：如果，是上述问题 的K-T解，否则 是 处的可行下降方向,令,令,是K-T解,K-T解的理由：,可行方向,下降方向,可行下降方向的理由：,1）确定初始可行解,2）选择 的前 个最大的正分量为 向量，确定 及可行解,3）计算简约梯度 和可行下降方向 如果，停止，已是K-T解,标准线性约束优化问题的简约梯度法,4）在 处沿方向 进行一维搜索确定，然 后用 替换，用 和 更 换，再回到 2）继续迭代,其他有关问题,凸规划问题的K-T解的性质,凸规划问题 需要：凸函数，凸集,等式和不等式约束描述的凸规划问题,需要：凸函数，都是凹函数，都是线性函数,容易验证，此时可行集是凸集,利用可导凸（凹）函数的性质可以得到,设 是满足K-T条件的可行解，是任意可行解,则有,又因为，可知,满足,因为 是满足K-T条件的可行解，所以存在,和可正可负的,利用,再利用,可得,又可得,可以得到,最后，由于,由于 是任意可行解，所以 是全局最优解,全局最优解的充要条件,结论：,对于凸规划问题，Kuhn-Tucker条件是,一般性优化问题的罚函数法（外点法）,对于一般性优化问题,构造加上惩罚项的目标函数,外点法就是求解下述无约束问题逼近原问题的解,其中,不等式约束优化问题的障碍函数法（内点法）,对于一般性不等式约束优化问题,构造加上障碍函数项的目标函数，如,可以从可行解开始求解下述无约束优化问题逼近,原问题的解,拉格朗日（Lagrange）对偶问题,对于附加约束子集的一般性优化问题,定义拉格朗日对偶问题为,其中,例、原问题,所以拉格朗日对偶问题为,则,仍然考虑原问题,所以拉格朗日对偶问题为,如果不定义附加子集，即，则,弱对偶定理,如果 是原问题的可行解，是对偶问题可行,解，那么一定成立,理由：,因为，,所以,又因为，所以,推论,是原问题的可行解,并且,是对偶问题可行解,如果,是对偶问题的最优解,是原问题的最优解,那么,