运筹学非线性规划.ppt

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