运筹学非线性规划126-7

第十二 章非线性规划 12.6 KKT条件 12.7 二次规划*12.6 约束优化的 KKT条件 回顾最优条件 单 变量非约束 多 变量非约束 有 约束的，但只有非负约束 充分条件可能是： 是凹函数 最优性的必要条件：12.6 约束优化的 KKT条件 一般约束问题 充分条件可能是： 是 凹函数并且 是凸函数 （见 12.2） 最优性的必要条件： 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 改进单纯形法对二次规划例子的应用迭代 基变量 方程 Z x1 x2 u1 y1 y2 v1 z1 z2 右端项0 Z (0) -1 0 -4 -3 1 1 0 0 0 -45z1 (1) 0 4 -4 1 -1 0 0 1 0 15z2 (2) 0 -4 8 2 0 -1 0 0 1 30v1 (3) 0 1 2 0 0 0 1 0 0 301 Z (0) -1 -2 0 -2 1 1/2 0 0 1/2 -30z1 (1) 0 2 0 2 -1 1/2 0 1 1/2 30x2 (2) 0 -1/2 1 1/4 0 -1/8 0 0 1/8 3+3/4v1 (3) 0 2 0 -1/2 0 1/4 1 0 -1/4 22+1/212.7 二次规划表 12.5 改进单纯形法对二次规划例子的应用迭代 基变量 方程 Z x1 x2 u1 y1 y2 v1 z1 z2 右端项2 Z (0) -1 0 0 -5/2 1 3/4 1 0 1/4 -7-1/2z1 (1) 0 0 0 5/2 -1 -3/4 -1 1 3/4 7+1/2x2 (2) 0 0 1 1/8 0 -1/16 1/4 0 1/16 9+3/8x1 (3) 0 1 0 -1/4 0 1/8 1/2 0 -1/8 11+1/43 Z (0) -1 0 0 0 0 0 0 1 1 0u1 (1) 0 0 0 1 -2/5 -3/10 -2/5 2/5 3/10 3x2 (2) 0 0 1 0 1/20 -1/40 3/10 -1/20 1/40 9x1 (3) 0 1 0 0 -1/10 1/20