不等式约束的极值问题及其经济学应用ppt课件.ppt

第第 5 章章不等式约束的极值问题及不等式约束的极值问题及其经济学应用其经济学应用为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.1 不等式约束极值问题数不等式约束极值问题数 学模型的一般形式学模型的一般形式 不等式约束极值问题和等式约束极值问题的不等式约束极值问题和等式约束极值问题的主要区别在于约束条件确定的决策变量取值范围主要区别在于约束条件确定的决策变量取值范围不同，即可行域不同，从而导致目标函数均衡解不同，即可行域不同，从而导致目标函数均衡解的位置不同，等式约束极值问题的均衡解在可行的位置不同，等式约束极值问题的均衡解在可行域的内点处取得，而不等式约束极值问题的均衡域的内点处取得，而不等式约束极值问题的均衡解可能位于可行域的端点上，那么，在这种情形解可能位于可行域的端点上，那么，在这种情形下求解最优化问题需要利用下求解最优化问题需要利用库恩库恩塔克条件塔克条件。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.1 不等式约束极值问题数不等式约束极值问题数 学模型的一般形式学模型的一般形式 令令 x=(x1,x2,xn)，f(x)和和 g(x)是连续的是连续的实值函数，则不等式约束的极值问题的数学模型实值函数，则不等式约束的极值问题的数学模型的一般形式为：的一般形式为：max y=f(x1,x2,xn)s.t.gi(x1,x2,xn)0，i=1,2,m 满足不等式组的满足不等式组的 x 构成的集合构成的集合 D 称为称为可行域可行域，D 中的点称为中的点称为可行点可行点。如果均衡解在可行域的内部。如果均衡解在可行域的内部则称为则称为内部解内部解，如果均衡解在可行域的边界上则称，如果均衡解在可行域的边界上则称为为角点解角点解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 所谓的简单的不等式约束极值问题是指自变量所谓的简单的不等式约束极值问题是指自变量个数不超过两个的极值问题。个数不超过两个的极值问题。例子例子 1：利用图解法求解下列极小化模型均衡解利用图解法求解下列极小化模型均衡解 min C=(x1 5)2+(x2 10)2 5x1+4x2 40 s.t.0 x1 5 0 x2 10为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 首先，确定可行域（见下图）。首先，确定可行域（见下图）。非线性规划的目标非线性规划的目标 就是从可行域内选择一就是从可行域内选择一 点点(x1*,x2*)，使其目标，使其目标 函数值最小。对于本题函数值最小。对于本题 来讲，实际上就是要以来讲，实际上就是要以 (5,10)为圆心的同心圆为圆心的同心圆 的半径最小。的半径最小。x1x2O105 8为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 即：这个同心圆与可行域相切。即：这个同心圆与可行域相切。在这个切点，圆的切线斜率与直线斜率相等。在这个切点，圆的切线斜率与直线斜率相等。所以，我们首先求圆的切线的斜率。目标函数所以，我们首先求圆的切线的斜率。目标函数可以重写为：可以重写为：(x1 5)2+(x2 10)2 C=0 对其求全微分可得：对其求全微分可得：2(x1 5)dx1+2(x2 10)dx2=0 整理得：整理得：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 于是有于是有 ，整理得：，整理得：4x1 5x2=30 与与 5x1+4x2=40 建立方程组：建立方程组：4x1 5x2=30 5x1+4x2=40 解方程组，得均衡解：解方程组，得均衡解：。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 例子例子 2：利用图解法求解下列极大化模型均衡解利用图解法求解下列极大化模型均衡解 max f(x,y)=x+y 2x2+y2 54 0 x 0，y 0 首先，确定可行域（见下页图）。首先，确定可行域（见下页图）。非线性规划的目标就是从可行域内选择一点非线性规划的目标就是从可行域内选择一点(x*,y*)，使其目标函数值最大。，使其目标函数值最大。s.t.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 对于本题来讲，实际对于本题来讲，实际 就是要使得直线与坐标轴就是要使得直线与坐标轴 的截距最大。的截距最大。即：直线与可行域相切。即：直线与可行域相切。在这个切点，椭圆在这个切点，椭圆 切线的斜率与直线的斜切线的斜率与直线的斜 率相等。率相等。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 所以，我们首先求椭圆的切线的斜率。对椭圆所以，我们首先求椭圆的切线的斜率。对椭圆求全微分，得：求全微分，得：4xdx+2ydy=0。整理得：整理得：，于是有：，于是有：与与 2x2+y2 54=0 建立方程组得：建立方程组得：解方程组，得均衡解：解方程组，得均衡解：(x*,y*)=(3,6)。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 例子例子 3：利用图解法求解下列极大化模型均衡解利用图解法求解下列极大化模型均衡解 max f(x,y)=x2+y2 2x2+y2 54 0 x 0，y 0 首先，确定可行域（见下页图）。首先，确定可行域（见下页图）。非线性规划的目标就是从可行域内选择一点非线性规划的目标就是从可行域内选择一点(x*,y*)，使其目标函数值最大。，使其目标函数值最大。s.t.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 对于本题来讲，实际对于本题来讲，实际 就是要使得以就是要使得以(0,0)为圆为圆 心的同心圆半径最大。心的同心圆半径最大。即：圆与可行域相切。即：圆与可行域相切。在这个切点，椭圆在这个切点，椭圆 切线的斜率与同心圆切切线的斜率与同心圆切 线的斜率相等。线的斜率相等。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.2 简单不等式约束极值问简单不等式约束极值问 题的图解法题的图解法 所以，我们首先求椭圆的切线的斜率。对椭圆所以，我们首先求椭圆的切线的斜率。对椭圆求全微分，得：求全微分，得：4xdx+2ydy=0。整理得：整理得：。然后，对圆求全微分，得：。然后，对圆求全微分，得：于是有于是有 x*=0，代入椭圆方程得，代入椭圆方程得 y*=。所以，均衡解为：所以，均衡解为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件一、简单不等式约束（仅存在非负约束）一、简单不等式约束（仅存在非负约束）极值问题的库恩极值问题的库恩塔克条件塔克条件 为得到一般化的不等式约束的库恩为得到一般化的不等式约束的库恩塔克条塔克条件，我们首先来分析简单的不等式约束的库恩件，我们首先来分析简单的不等式约束的库恩塔克条件，即仅有非负约束而无其他约束。塔克条件，即仅有非负约束而无其他约束。我们先来看单变量的情形：我们先来看单变量的情形：f(x)是连续可微的是连续可微的 max y=f(x)s.t.x 0(5-1)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 由于约束条件由于约束条件 x 0，因此说模型，因此说模型(5-1)式的最式的最优解可能会存在三种情况：优解可能会存在三种情况：第一种情况第一种情况：y 的极大值对应的均衡解的极大值对应的均衡解 x*出现在可出现在可 行域的内部。行域的内部。在这种情况下，一阶在这种情况下，一阶 必要条件为：必要条件为：AOyxx*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 第二种情况第二种情况：y 的极大值对应的均衡解的极大值对应的均衡解 x*出现在可出现在可 行域的边界上，但仍能保证一阶必要行域的边界上，但仍能保证一阶必要 条件条件 。在这种情况下，一阶在这种情况下，一阶 必要条件为：必要条件为：且：且：x*=0BOyxx*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 第三种情况第三种情况：y 的极大值对应的均衡解的极大值对应的均衡解 x*出现在可出现在可 行域的边界上，但不能保证一阶必要行域的边界上，但不能保证一阶必要 条件条件 。在这种情况下，一阶在这种情况下，一阶 必要条件为：必要条件为：且：且：x*=0COyxx*D为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 从上面的讨论来看，模型从上面的讨论来看，模型(5-1)问题的极大值点问题的极大值点存在的必要条件是如下三个条件之一：存在的必要条件是如下三个条件之一：f(x*)=0，且，且 x*0 A 点点 f(x*)=0，且，且 x*=0 B 点点 f(x*)0 两种情况开始判断，然后找两种情况开始判断，然后找到同时满足库恩到同时满足库恩塔克条件的解。塔克条件的解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 2.n 变量变量 m 约束极值问题的库恩约束极值问题的库恩塔克条件塔克条件 n 个变量个变量 m 个约束条件的极值问题可写为：个约束条件的极值问题可写为：max y=f(x)s.t.gj(x)0，j=1,2,m 其中：其中：x=(x1,x2,xn)f(x)和和 g(x)是连续可微函数。是连续可微函数。(5-13)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 构造构造 Lagrange 函数：函数：L(x,1,2,m)=f(x)+1g1(x)+1g2(x)+mgm(x)m =f(x)jgj(x)j=1 库恩库恩塔克塔克 条件为：条件为：x*x*x*x*x*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 如果如果(5-13)式还存在决策变量的非负约束，则式还存在决策变量的非负约束，则均衡解的库恩均衡解的库恩塔克条件为：塔克条件为：x*x*x*x*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 举个例子：举个例子：求下列最优化问题的可能极值点求下列最优化问题的可能极值点 max f(x,y)=x(10 x)+y(10 y)s.t.5x 4y 40 x 5 y 10 x 0,y 0为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 如果是极小值问题呢，库恩如果是极小值问题呢，库恩塔克条件是？塔克条件是？一个简单的处理方法是一个简单的处理方法是将它转化为极大值问将它转化为极大值问 题题，而且，而且将不等式约束均转化为将不等式约束均转化为“”。举个例子：举个例子：min C=(x 4)2+(y 4)2 s.t.2x+3y 6 3x 2y 12 x 0,y 0为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 解：首先，极小值问题转化为极大值问题解：首先，极小值问题转化为极大值问题 max C=(x 4)2 (y 4)2 s.t.2x 3y 6 3x+2y 12 x 0,y 0 构建拉格构建拉格 L=(x 4)2 (y 4)2+1(6+2x 朗日函数：朗日函数：+3y)+2(12 3x 2y)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 于是，该问题的库恩于是，该问题的库恩塔克条件为：塔克条件为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件三、混合约束极值问题的库恩三、混合约束极值问题的库恩塔克条件塔克条件 考虑考虑 k 个等式约束和个等式约束和 m 个不等式约束的个不等式约束的 n 元元实值函数实值函数 f(x1,x2,xn)的极大值问题：的极大值问题：max y=f(x1,x2,xn)s.t.hl(x1,x2,xn)=al，l=1,2,k gj(x1,x2,xn)bj，j=1,2,m为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 对于不等式约束：对于不等式约束：gj(x1,x2,xn)bj，j=1,2,m 我们假设其中有我们假设其中有 m0 个约束条件在均衡解个约束条件在均衡解 x*=(x1*,x2*,xn*)处是紧的（即使得不等式约束的等处是紧的（即使得不等式约束的等 号成立），姑且认为就是前号成立），姑且认为就是前 m0 个约束条件在均衡解个约束条件在均衡解 处是紧的，而后处是紧的，而后 m m0 个约束条件不是紧的。个约束条件不是紧的。我们再假定在均衡点我们再假定在均衡点 x*=(x1*,x2*,xn*)处满处满足约束规范，即：足约束规范，即：所有等式约束构成的向量值函数所有等式约束构成的向量值函数在在 x*处的雅可比矩阵的秩为处的雅可比矩阵的秩为 m0+k。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件亦即：雅可比矩阵亦即：雅可比矩阵 的秩为的秩为 m0+k。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 构造构造 Lagrange 函数：函数：库恩库恩塔克条件为：塔克条件为：xxxx,为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 如果给该极大值问题再加上非负约束，则库如果给该极大值问题再加上非负约束，则库恩恩塔克条件为：塔克条件为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.3 库恩库恩塔克条件塔克条件 举个例子举个例子：求解下面最优化问题可能的极值点：求解下面最优化问题可能的极值点 max f(x,y)=2x+y s.t.(x+1)(y+1)=9/2 x 0,y 0为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 思考一个问题：思考一个问题：我们前面讲的库恩我们前面讲的库恩塔克条件是塔克条件是 求解不等式约束的极值问题均衡求解不等式约束的极值问题均衡 解的必要条件吗？解的必要条件吗？先举一个先举一个例子例子 1：考虑下述不等式约束极值问题：考虑下述不等式约束极值问题 max y=x1 s.t.x2 (1 x1)3 0 x1 0,x2 0为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 首先，我们用前面讲的库恩首先，我们用前面讲的库恩塔克条件来求解。塔克条件来求解。构造构造 Lagrange 函数：函数：L=x1+(1 x1)3 x2 库恩库恩塔克条件为：塔克条件为：无解无解为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 这个不这个不等式约束极等式约束极值问题真就值问题真就无解吗？无解吗？下面我下面我们用最开始们用最开始学的图解法学的图解法来试试。来试试。（先找可行域）（先找可行域）Ox1x211并未按照这个并未按照这个趋势走，而是趋势走，而是突然转弯。突然转弯。均衡解（均衡解（1,0）歧点歧点为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 由图解法可知，该不等式约束极值问题存在最由图解法可知，该不等式约束极值问题存在最优解（优解（1，0），但根据前述库恩），但根据前述库恩塔克条件却无法塔克条件却无法解出，表明库恩解出，表明库恩塔克条件失效，亦表明前述的库塔克条件失效，亦表明前述的库恩恩塔克条件不是不等式约束极值问题的必要条件。塔克条件不是不等式约束极值问题的必要条件。为什么会出现这种情况呢？为什么会出现这种情况呢？我们观察一下，我们观察一下，在最优解（在最优解（1，0）之前，可行域的边界是沿着某个趋）之前，可行域的边界是沿着某个趋势行走，但当达到最优解点（势行走，但当达到最优解点（1，0）时却不再按照这）时却不再按照这个趋势继续行走，而是突然转向，我们把这样的最优个趋势继续行走，而是突然转向，我们把这样的最优解点称为解点称为歧点歧点（Cusp，也叫分岔点）。歧点前后可行，也叫分岔点）。歧点前后可行域边界表现出了某种不规则性，而正是由于这种不规域边界表现出了某种不规则性，而正是由于这种不规则性使得库恩则性使得库恩塔克条件在边界的最优解处失效。塔克条件在边界的最优解处失效。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 歧点的数学表达：当曲线突然反向，使得在该点一歧点的数学表达：当曲线突然反向，使得在该点一 边的斜率等于该点另一边的斜率边的斜率等于该点另一边的斜率 时，所形成的尖点（时，所形成的尖点（Sharp Point）。）。歧点是最经常引用的使库恩歧点是最经常引用的使库恩塔克条件失效的塔克条件失效的原因，但事实上，原因，但事实上，歧点的出现既不是库恩歧点的出现既不是库恩塔克条塔克条件在最优解处失效的必要条件，也不是充分条件件在最优解处失效的必要条件，也不是充分条件。比如，我们比如，我们举一个举一个例子例子 2 对于对于例子例子 1 我我 们再加上一个新的约束条件：们再加上一个新的约束条件：2x1+x2 2。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 我们先我们先用图解法来用图解法来求解。求解。（先找可行域）（先找可行域）可行域没变可行域没变 均衡解（均衡解（1,0）Ox1x2112均衡解（均衡解（1,0）歧点歧点为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 我们再用库恩我们再用库恩塔克条件来解。塔克条件来解。Lagrange 函数函数 可写为：可写为：L=x1+1(1 x1)3 x2+2(2 2x1 x2)库恩库恩塔克条件为：塔克条件为：(1,0)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 由由例子例子 2 可知，即使存在歧点，但库恩可知，即使存在歧点，但库恩塔克塔克条件仍然成立，即条件仍然成立，即歧点并非库恩歧点并非库恩塔克条件失效的塔克条件失效的必要条件必要条件。我们再举一个我们再举一个例子例子 3：考虑如下最优化问题：考虑如下最优化问题 max y=x2 x12 s.t.(10 x12 x2)3 0 x1 2 x1 0,x2 0为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 我们先用库恩我们先用库恩塔克条件来试试。塔克条件来试试。Lagrange 函函 数为：数为：L=x2 x12+1(10 x12 x2)3+2(2+x1)库恩库恩塔克条件为：塔克条件为：无解无解为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 下面我下面我们用图解法们用图解法来试试。来试试。（先找可行域）（先找可行域）Ox1x221 2 310(2,6)任何地方都不存在歧点任何地方都不存在歧点使得使得 x2=x12 向上向上移动的距离最大。移动的距离最大。均衡解点均衡解点为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 由由例子例子 3 可知，即便是在没有歧点存在的情况可知，即便是在没有歧点存在的情况下，库恩下，库恩塔克条件也是失效的（图解法证明该问塔克条件也是失效的（图解法证明该问题是有最优解的），因此说，题是有最优解的），因此说，歧点也不是库恩歧点也不是库恩塔塔克条件失效的充分条件克条件失效的充分条件。通过上面的分析可知，库恩通过上面的分析可知，库恩塔克条件并非不塔克条件并非不等式约束极值问题的必要条件，那么在什么情况下等式约束极值问题的必要条件，那么在什么情况下库恩库恩塔克条件才是不等式约束极值问题的必要条塔克条件才是不等式约束极值问题的必要条件呢？件呢？只有满足特定条件时只有满足特定条件时（这个条件就叫（这个条件就叫做做约束规范约束规范，Constraint Qualification），库恩），库恩塔塔克条件才是不等式约束极值问题的必要条件。克条件才是不等式约束极值问题的必要条件。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）由前面的分析可知，这个特定条件（约束规范）由前面的分析可知，这个特定条件（约束规范）与可行域的形状无关（例子与可行域的形状无关（例子 1 和例子和例子 2 具有相同可行具有相同可行域、例子域、例子 3 的可行域还是凸集），而是与约束函数的的可行域还是凸集），而是与约束函数的形式有关（例子形式有关（例子 2 加上一个新的约束条件后，库恩加上一个新的约束条件后，库恩塔克条件便未失效）。塔克条件便未失效）。什么是约束规范呢？什么是约束规范呢？是指对非线性规划中的是指对非线性规划中的约束函数施加的某些限制，目的是为了排除可行域边约束函数施加的某些限制，目的是为了排除可行域边界上的某些不规则性（包括但不仅限于歧点），这些界上的某些不规则性（包括但不仅限于歧点），这些不规则性可能会违背能够产生最优解的库恩不规则性可能会违背能够产生最优解的库恩塔克条塔克条件。换句话说，如果约束条件满足某一约束规范，则件。换句话说，如果约束条件满足某一约束规范，则边界的不规则性就不会存在，库恩边界的不规则性就不会存在，库恩塔克条件有效。塔克条件有效。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）那么，究竟是在什么情况下才是满足约束规范呢那么，究竟是在什么情况下才是满足约束规范呢？考虑如下一般性的不等式约束极值问题考虑如下一般性的不等式约束极值问题 max y=f(x1,x2,xn)s.t.gi(x1,x2,xn)0，i=1,2,m 我们先给出一个我们先给出一个定义定义：令：令 x0=(x10,x20,xn0)是可行域中的一个点，在点是可行域中的一个点，在点 x0 处，如果满足处，如果满足 gi(x10,x20,xn0)=0，则称约束条件，则称约束条件 gi(x1,x2,xn)0 在点在点 x0 处是处是紧的紧的。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）以以例子例子 1 为例。为例。约束条件：约束条件：x2 (1 x1)3 0在在 A 点是紧的。点是紧的。其他两个约束条件：其他两个约束条件：x1 0 和和x2 0 在在 A 点不是紧的。点不是紧的。Ox1x2112AB约束条件约束条件 x2 (1 x1)3 0和和 x2 0 在在 B 点是紧的点是紧的C三约束条件在三约束条件在 C 点都不是紧的点都不是紧的约束条件约束条件 x2 (1 x1)3 0和和 x1 0 在在 D 点是紧的点是紧的D为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）假设在可行域假设在可行域边界上边界上的点的点 x*=(x1*,x2*,xn*)满足所有约束，即：满足所有约束，即：对任意的对任意的 i（i=1,2,m）都有）都有 gi(x*)0 而且在点而且在点 x*处有处有 k 个（个（k m）不等式约束条件）不等式约束条件是紧的，且这是紧的，且这 k 个约束函数的梯度向量是线性无关个约束函数的梯度向量是线性无关的，则称在点的，则称在点 x*处满足处满足约束规范约束规范（也称满足（也称满足线性线性独立规格独立规格）。）。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）何谓何谓梯度向量梯度向量？n 元函数元函数 f(x)=f(x1,x2,xn)对于对于 xi 的一阶的一阶 偏导数构成的偏导数构成的 n 维向量称为维向量称为梯度向量梯度向量，即：，即：xxxx为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）下面我们来验证一下下面我们来验证一下例子例子 1。g1(x1,x2)=x2 (1 x1)3 首先，写出三个约束函数：首先，写出三个约束函数：g2(x1,x2)=x1 g3(x1,x2)=x2 在均衡点在均衡点(1,0)处，有处，有 2 个约束条件是紧的，且：个约束条件是紧的，且：x*x*x*x*x*x*线性相关，不线性相关，不满足约束规范满足约束规范为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 约束规范（约束规格）约束规范（约束规格）所以，由以上分析可知，若要使用库恩所以，由以上分析可知，若要使用库恩塔克塔克条件来求解不等式约束极值问题，应该在利用库恩条件来求解不等式约束极值问题，应该在利用库恩塔克条件求解得到均衡解后，对均衡点检验约束塔克条件求解得到均衡解后，对均衡点检验约束函数是否满足约束规范。函数是否满足约束规范。特别需要指出的是，如果可行域仅是由线性约特别需要指出的是，如果可行域仅是由线性约束形成的凸集，那么约束规范总是满足的，而且库束形成的凸集，那么约束规范总是满足的，而且库恩恩塔克条件在最优解处总成立。塔克条件在最优解处总成立。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 再思考一个问题：再思考一个问题：库恩库恩塔克条件是求解不等式塔克条件是求解不等式 约束极值问题的充分条件吗？约束极值问题的充分条件吗？再举一个再举一个例子例子 4：考虑下述不等式约束极值问题：考虑下述不等式约束极值问题 min y=x2 s.t.x12+x2 0 x12+x22 1 0为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 首先，将最优值问题转化为极大值问题的标准型。首先，将最优值问题转化为极大值问题的标准型。max z=x2 s.t.x12+x2 0 x12+x22 1 0 然后，构造然后，构造 Lagrange 函数：函数：L=x2+1(x12 x2)+2(1 x12 x22)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 库恩库恩塔克条件为：塔克条件为：解得均衡点为解得均衡点为(0,0)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 下面我们来验证约束函数在均衡点下面我们来验证约束函数在均衡点(0,0)处是否处是否满足约束规范。满足约束规范。该问题的约束函数为：该问题的约束函数为：g1(x1,x2)=x12+x2 g2(x1,x2)=x12+x22 1 在均衡点在均衡点(0,0)处，只有第一个约束条件是紧的，处，只有第一个约束条件是紧的，而且它的梯度向量为：而且它的梯度向量为：线性无关，满线性无关，满足约束规范足约束规范为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 下面，我们看看图解法的结果。下面，我们看看图解法的结果。库恩库恩塔克得塔克得到的均衡点到的均衡点实际的最优值点实际的最优值点x1x2O满足库恩满足库恩塔克塔克条件的点不是目条件的点不是目标函数均衡解。标函数均衡解。库恩库恩塔克塔克条件不是充条件不是充分条件。分条件。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 库恩库恩塔克条件与塔克条件与 Lagrange 条件的比较条件的比较 相似之处相似之处：在没有非负约束的限制下，二者的在没有非负约束的限制下，二者的 Lagrange 函数对决策变量的一阶偏导数都是函数对决策变量的一阶偏导数都是 0；当不等式约束问题中的约束条件满足紧的时当不等式约束问题中的约束条件满足紧的时 候，则二者的候，则二者的 L/j 均等于均等于 0（相同），则（相同），则 由此看出，等式约束问题的必要条件是不等由此看出，等式约束问题的必要条件是不等 式约束问题必要条件的特殊情况。式约束问题必要条件的特殊情况。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.4 对库恩对库恩塔克条件的认识塔克条件的认识 不同之处不同之处：在等式约束中，在等式约束中，Lagrange 乘子可以为正，也乘子可以为正，也 可以为负；但在不等式约束中，紧约束对应可以为负；但在不等式约束中，紧约束对应 的库恩的库恩塔克条件中的塔克条件中的 Lagrange 乘子为正，乘子为正，而松约束的而松约束的 Lagrange 乘子为乘子为 0；由于不等式约束问题对由于不等式约束问题对 有非负限制，所以有非负限制，所以 L 对对 的一阶偏导的一阶偏导 0，且该一阶偏导数与，且该一阶偏导数与 构成互补松弛性，而在等式约束问题中，构成互补松弛性，而在等式约束问题中，L 对对 的一阶偏导的一阶偏导=0，故不存在互补松弛性。，故不存在互补松弛性。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.5 库恩库恩塔克条件的充分性塔克条件的充分性一、库恩一、库恩塔克条件的二阶充分条件塔克条件的二阶充分条件 考虑如下不等式约束的极大值问题：考虑如下不等式约束的极大值问题：max y=f(x)s.t.gj(x)0，j=1,2,m 其中：其中：x=(x1,x2,xn)。构造构造 Lagrange 函数：函数：x*,*x*x*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.5 库恩库恩塔克条件的充分性塔克条件的充分性 如果库恩如果库恩塔克条件在塔克条件在(x*,*)得到满足，则有：得到满足，则有：假设前假设前 m0 个约束条件个约束条件 g1,g2,gm0 在在 x*处等处等 号成立（即紧的），而后号成立（即紧的），而后 m m0 个约束条件个约束条件 gm0+1,gm0+2,gm 在在 x*处取严格不等号。处取严格不等号。x*x*x*,*x*,*x*,*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.5 库恩库恩塔克条件的充分性塔克条件的充分性 令令 gM0=(g1,g2,gm0)，则，则 gM0 在在 x*处的梯度处的梯度 向量可写为：向量可写为：x*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.5 库恩库恩塔克条件的充分性塔克条件的充分性 此外，此外，Lagrange 函数在函数在(x*,*)处的海塞矩阵可处的海塞矩阵可写为：写为：x*,*为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.5 库恩库恩塔克条件的充分性塔克条件的充分性 构造如下海赛加边矩阵：构造如下海赛加边矩阵：类似于等式约束，如果后类似于等式约束，如果后 n m0 个海塞加边主个海塞加边主子式子式 的符号均与的符号均与(1)k（m0 k 0，与与(1)2 同号。同号。所以，所以，(3,6)是目标函数的一个极大值点。是目标函数的一个极大值点。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能5.5 库恩库恩塔克条件的充分性塔克条件的充分性二、库恩二、库恩塔克充分性定理：凹规划塔克充分性定理：凹规划 在某些情况下，库恩在某些情况下，库恩塔克条件可以被用作极塔克条件可以被用作极大化问题的充分条件。大化问题的充分条件。考虑如下极大化问题：考虑如下极大化问题：max y=f(x)s.