《运筹学非线性规划》PPT课件.ppt

第十二章非线性规划12.6 KKT条件12.7 二次规划2022/10/2712.6 约束优化的KKT条件回顾最优条件单变量非约束多变量非约束有约束的，但只有非负约束充分条件可能是：是凹函数最优性的必要条件：12.6 约束优化的KKT条件一般约束问题充分条件可能是：是凹函数并且 是凸函数（见）最优性的必要条件：KKT条件12.6 约束优化的KKT条件最优性的充要条件表表12.4 最优性的充要条件最优性的充要条件问题最优性的必要条件充要条件可能是单变量非约束 是凹函数多变量非约束 是凹函数有约束的，但只有非负约束 是凹函数一般约束KKT条件 是凹函数并且 是凸函数（见12.2）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.5 改进单纯形法对二次规划例子的应用改进单纯形法对二次规划例子的应用迭代基变量方程Zx1x2u1y1y2v1z1z2右端项0Z(0)-10-4-311000-45z1(1)04-41-1001015z2(2)0-4820-100130v1(3)012000100301Z(0)-1-20-211/2001/2-30z1(1)0202-11/2011/230 x2(2)0-1/211/40-1/8001/83+3/4v1(3)020-1/201/410-1/422+1/212.7 二次规划表表12.5 改进单纯形法对二次规划例子的应用改进单纯形法对二次规划例子的应用迭代基变量方程Zx1x2u1y1y2v1z1z2右端项2Z(0)-100-5/213/4101/4-7-1/2z1(1)0005/2-1-3/4-113/47+1/2x2(2)0011/80-1/161/401/169+3/8x1(3)010-1/401/81/20-1/811+1/43Z(0)-1000000110u1(1)0001-2/5-3/10-2/52/53/103x2(2)00101/20-1/403/10-1/201/409x1(3)0100-1/101/202/51/10-1/2012因此，该二次规划问题的最优解为x1=12，x2=9。12.7 二次规划一些软件的选择lExcellLINGOlLINDOlMPL/CPLEXTHE ENDTHANK YOU!