《运筹学非线性规划126-7演示教学》由会员分享，可在线阅读，更多相关《运筹学非线性规划126-7演示教学（20页珍藏版）》请在金锄头文库上搜索。
1、第十二章非线性规划,12.6 KKT条件 12.7 二次规划,2020/9/2,12.6 约束优化的KKT条件,回顾最优条件 单变量非约束 多变量非约束 有约束的，但只有非负约束 充分条件可能是： 是凹函数 最优性的必要条件：,12.6 约束优化的KKT条件,一般约束问题 充分条件可能是： 是凹函数并且 是凸函数 （见12.2） 最优性的必要条件：KKT条件,12.6 约束优化的KKT条件,KKT条件,12.6 约束优化的KKT条件,定理： 假设 是满足某些正则性条件的可微函数。只有当存在 个数 ，使所有KKT条件都满足，这时 可能是非线性规划问题的一个最优解。 推论 假设 是一个凹函数， 是
2、凸函数（即该问题为凸规划问题），并且这些函数都满足正则性条件。那么当且仅当定理的所有条件都满足时， 是一个最优解。,12.6 约束优化的KKT条件,例 双变量非线性规划问题 可知：,12.6 约束优化的KKT条件,KKT条件：,12.6 约束优化的KKT条件,KKT条件： 该问题最优解：,12.7 二次规划,二次规划与线性规划问题的不同之处仅仅在于目标函数也包括 和 项。用矩阵符号表示二次规划问题： 用向量元素表示： 半正定矩阵：如果对任何非零向量 ，都有 成立，且有非零向量 ，使 ，则称矩阵A为半正定矩阵。,12.7 二次规划,例如 此时：,12.7 二次规划,对于二次规划的KKT条件（以上
3、题为例） KKT条件： 将不等式变为等式。,12.7 二次规划,注意此时条件2与条件4可表示为： 对于每个配对 其中的两个变量称为互补变量。这些条件得到一个新的组合约束 称为互补约束。,12.7 二次规划,整个条件集合的简便形式 用矩阵符号表示：,12.7 二次规划,改进的单纯形法 引入人工变量 ，相当于应用单纯形法求解以下的线性规划问题 满足从KKT条件得到的线性规划约束，但也包括这些人工变量。,同原单纯形法相比，修改发生于： 限制-输入规则：当你选择一个输入基变量时，考虑排除互补变量已经是一个基变量的任一非基变量；选择应该是根据单纯形表的一般标准从其他非基变量中做出的。,12.7 二次规划,依旧用本节刚开始的例子说明这种方法 在引入所需人工变量后，用改进的单纯形法显性说明的线性规划问题是 附加的互补约束用限制-输入规则，算法自动的执行该约束。,12.7 二次规划,12.7 二次规划,因此，该二次规划问题的最优解为x1=12，x2=9。,12.7 二次规划,一些软件的选择 Excel LINGO LINDO MPL/CPLEX,THE END THANK YOU!,
