约束条件下多变量函数的寻优方法.ppt

《约束条件下多变量函数的寻优方法.ppt》由会员分享，可在线阅读，更多相关《约束条件下多变量函数的寻优方法.ppt（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 运筹学 第第第第1010章章章章 约束条件下多变量函数的寻优方法约束条件下多变量函数的寻优方法约束条件下多变量函数的寻优方法约束条件下多变量函数的寻优方法10.1 10.1 约束极值问题的最优性条件约束极值问题的最优性条件约束极值问题的最优性条件约束极值问题的最优性条件一、一、一、一、基本概念基本概念基本概念基本概念 1.1.起作用约束起作用约束起作用约束起作用约束 等式约束对所有可行点来说都是起作用约束等式约束对所有可行点来说都是起作用约束等式约束对所有可行点来说都是起作用约束等式约束对所有可行点来说都是起作用约束.2.2.正则点正则点正则点正则点 对于非线性规划问题对于非线性规划问题对于

2、非线性规划问题对于非线性规划问题(1),(1),若在可行点若在可行点若在可行点若在可行点X X1 1处处处处,各各各各起作用约束的起作用约束的起作用约束的起作用约束的 梯度线性无关梯度线性无关梯度线性无关梯度线性无关,则则则则X X1 1是约束条件的一个是约束条件的一个是约束条件的一个是约束条件的一个正则点正则点正则点正则点.设有非线性规划问题设有非线性规划问题设有非线性规划问题设有非线性规划问题 运筹学 一、一、一、一、基本概念基本概念基本概念基本概念 1.1.起作用约束起作用约束起作用约束起作用约束 等式约束对所有可行点来说都是起作用约束等式约束对所有可行点来说都是起作用约束等式约束对所有

3、可行点来说都是起作用约束等式约束对所有可行点来说都是起作用约束.2.2.正则点正则点正则点正则点 对于非线性规划问题对于非线性规划问题对于非线性规划问题对于非线性规划问题(1),(1),若在可行点若在可行点若在可行点若在可行点X X1 1处处处处,各各各各起作用约束的起作用约束的起作用约束的起作用约束的 梯度线性无关梯度线性无关梯度线性无关梯度线性无关,则则则则X X1 1是约束条件的一个是约束条件的一个是约束条件的一个是约束条件的一个正则点正则点正则点正则点.设有非线性规划问题设有非线性规划问题设有非线性规划问题设有非线性规划问题3.3.可行方向可行方向可行方向可行方向 设设设设R R是非线

4、性规划问题是非线性规划问题是非线性规划问题是非线性规划问题(1)(1)的可行域的可行域的可行域的可行域,X,X1 1是可行点是可行点是可行点是可行点,d,d为某个给定为某个给定为某个给定为某个给定 方向方向方向方向,若存在若存在若存在若存在 1 10,0,使得对于任意的使得对于任意的使得对于任意的使得对于任意的 (0(0 0,0,使得对于任意的使得对于任意的使得对于任意的使得对于任意的 (0(0 0(jd0(j J).J).运筹学 3.3.可行方向可行方向可行方向可行方向 设设设设R R是非线性规划问题是非线性规划问题是非线性规划问题是非线性规划问题(1)(1)的可行域的可行域的可行域的可行域

5、,X,X1 1是可行点是可行点是可行点是可行点,d,d为某个给定为某个给定为某个给定为某个给定 方向方向方向方向,若存在若存在若存在若存在 1 10,0,使得对于任意的使得对于任意的使得对于任意的使得对于任意的 (0(0 0(jd0(j J).J).4.4.下降方向下降方向下降方向下降方向 设设设设X X1 1是可行点是可行点是可行点是可行点,对于该点任一方向对于该点任一方向对于该点任一方向对于该点任一方向d,d,若存在若存在若存在若存在 1 10,0,使得任意使得任意使得任意使得任意 (0 (0 1 1),),都有都有都有都有f(f(X X1 1+d)f(d)f(X X1 1),),则称方向

6、则称方向则称方向则称方向d d为为为为X X1 1点的一个点的一个点的一个点的一个下降方下降方下降方下降方向向向向.注注注注 d d为点为点为点为点X X1 1的的的的下降方向下降方向下降方向下降方向f(Xf(X1 1)T Td0.d0.5.5.可行下降方向可行下降方向可行下降方向可行下降方向 运筹学 二、二、二、二、库恩库恩库恩库恩塔克塔克塔克塔克(Kuhn-Tucker)(Kuhn-Tucker)条件条件条件条件 是确定某点为最优点的是确定某点为最优点的是确定某点为最优点的是确定某点为最优点的一阶必要条件一阶必要条件一阶必要条件一阶必要条件.只要是只要是只要是只要是最优点且为正则点最优点且

7、为正则点最优点且为正则点最优点且为正则点就必满足该条件就必满足该条件就必满足该条件就必满足该条件.对于对于对于对于凸规划凸规划凸规划凸规划,库恩库恩库恩库恩塔克条件是最优点存在的塔克条件是最优点存在的塔克条件是最优点存在的塔克条件是最优点存在的充要条件充要条件充要条件充要条件.1.1.一阶必要条件定理一阶必要条件定理一阶必要条件定理一阶必要条件定理 对非线性规划问题对非线性规划问题对非线性规划问题对非线性规划问题(1)(1)而言而言而言而言,若若若若X X*是局部或全局极值点且为正则是局部或全局极值点且为正则是局部或全局极值点且为正则是局部或全局极值点且为正则点点点点,则一定存在向量则一定存在

8、向量则一定存在向量则一定存在向量设有非线性规划问题设有非线性规划问题设有非线性规划问题设有非线性规划问题及及及及,使得下述条使得下述条使得下述条使得下述条件件件件成立成立成立成立.注注注注 称为称为称为称为广义拉格朗日函数广义拉格朗日函数广义拉格朗日函数广义拉格朗日函数.运筹学 二、二、二、二、库恩库恩库恩库恩塔克塔克塔克塔克(Kuhn-Tucker)(Kuhn-Tucker)条件条件条件条件 是确定某点为最优点的是确定某点为最优点的是确定某点为最优点的是确定某点为最优点的一阶必要条件一阶必要条件一阶必要条件一阶必要条件.只要是只要是只要是只要是最优点且为正则点最优点且为正则点最优点且为正则点

9、最优点且为正则点就必满足该条件就必满足该条件就必满足该条件就必满足该条件.对于对于对于对于凸规划凸规划凸规划凸规划,库恩库恩库恩库恩塔克条件是最优点存在的塔克条件是最优点存在的塔克条件是最优点存在的塔克条件是最优点存在的充要条件充要条件充要条件充要条件.1.1.一阶必要条件定理一阶必要条件定理一阶必要条件定理一阶必要条件定理 对非线性规划问题对非线性规划问题对非线性规划问题对非线性规划问题(1)(1)而言而言而言而言,若若若若X X*是局部或全局极值点且为正则是局部或全局极值点且为正则是局部或全局极值点且为正则是局部或全局极值点且为正则点点点点,则一定存在向量则一定存在向量则一定存在向量则一定存在向量及及及及,使得下述条使得下述条使得下述条使得下述条件件件件成立成立成立成立.注注注注 称为称为称为称为广义拉格朗日函数广义拉格朗日函数广义拉格朗日函数广义拉格朗日函数.例例例例:求下列非线性规划问题的求下列非线性规划问题的求下列非线性规划问题的求下列非线性规划问题的K-TK-T点点点点.