5拟凹规划与比较静态分析 .docx

1、第5章 拟凹规划与比较静态分析5.1 KuhnTucker问题5.2 最优化问题的变形5.3 比较静态分析5.4 单调比较静态分析5.5 对偶原理l 本章解决参数约束最优化问题 (5.1)余下的两个问题：1 求解方法：如何求出问题(5.1)的解？2 比较静态分析：参数发生变化时，解集和值函数如何随变化？l 拟凹规划问题n 约束函数：(拟)凸n 目标函数：(伪)凹5.1 KuhnTucker问题5.1.1 基本概念5.1.2 Kuhn-Tucker定理5.1.3 最优解的充分条件5.1.1 基本概念l 问题 (5.2) n 约束集非空n 经济学中还经常包括u 等式约束u 非负约束 (等价于)。l

2、 基本概念n 约束是紧的(binding) ：n 约束是松的(binding) ：n 处紧的约束集n 点处约束限制(constraint qualification)成立中的向量线性无关5.1.2 KuhnTucker定理l Kuhn-Tucker定理n 设问题(5.2)满足i. 连续可微；ii. 非空iii. 是问题的解iv. 在点处约束限制成立。则可得Kuhn-Tucker条件：1 Lagrange条件：，。2 互补松弛条件(complementary slackness conditions):l 单一约束情形下的Kuhn-Tucker定理n 在约束是紧的但非最优点，沿着的垂线向点进行微

3、小的变动将使函数值增加。n 在点处沿着约束线的任意可行的变动都不会改变目标函数值。l 为什么紧的约束乘子必须是非负的？n 如果乘子为负，向约束集内部的移动使约束变松，从而会增加函数值。图5.2 为什么是非负的l 如果不满足约束限制，Kuhn-Tucker定理会失效n 图中的是问题的解，但无法将表示成和的线性组合。5.1.3 最优解的充分条件l Kuhn-Tucker条件是作为解的必要但非充分条件。n 图5.4中的满足Kuhn-Tucker条件，但它不是问题(5.2)的解；而点和则都是。l 为检验二阶条件或充分条件，需要计算(加边)海赛矩阵并且检验负半定性，这是一件痛苦的事情!l 对多数经济问题

4、，定理5.2能有效解决这一问题：l 定理5.2 充分条件假设问题(5.2)满足Kuhn-Tucker定理的条件，并且：(i) 伪凹；(ii) 都是拟凸的则满足Kuhn-Tucker条件的所有都是问题的解。l 经济理论中的多数最优化模型能满足定理的条件n 伪凹性u 不稳定的拟凹性伪凹性u 凹性伪凹性u 严格拟凹性伪凹性l 问题(5.2)的惟一解。l 定理5.3 假设是问题(5.2)的最优解，如果n 严格拟凹n 约束函数拟凸，则是问题(5.2)的惟一解。5.2 最优化问题的变形5.2.1 非负约束5.2.2 等式约束5.2.3 最优化问题的简化5.2.1 非负约束：l 问题： (5.3)l 定理5

5、.4 假设问题(5.3)满足：(i)连续可微；(ii)非空；(iii)是问题的解；(iv)在点处约束限制满足(包括所有的非负约束)。记Lagrange函数为则最优性条件为 l 例5.1 问题 (5.5)(i) 目标函数是两个对数之和：凹(ii) 约束函数是线性的:凸。问题(5.5)是凸的，因而可以应用定理5.4。l 等式约束+非负约束问题： (5.6)l 定理5.5 假设问题(5.6)满足：(i)连续可微(ii)非空(iii)是问题的解(iv)在点处约束限制满足(包括所有的非负约束)。则最优性条件为，=0， (5.7)l 例5.2 消费者问题5.2.2 等式约束l 问题 (5.8) l 定理5

6、.6 Lagrange乘子定理 假设问题(5.8)满足(i) 连续可微；(ii)非空；(iii)是问题的解；(iv)在点处约束限制成立， 这一条件称为Lagrange条件。定理5.7 最优解的充分条件 问题(5.8)中，设(1)伪凹;(2)拟凹;如果满足Lagrange条件，并且，则是问题的解。5.2.3 最优化问题的简化l 定理5.7 假设问题 (5.2)满足：(i) 严格拟凹；(ii) 严格拟凸；(iii) 在解处是紧约束；(iv) 在解处是松约束。则：是问题(5.2)的解它是修正后的问题 (5.9)的解。5.3 比较静态分析5.3.1 隐函数定理5.3.2 包络定理l 比较静态分析n 分

7、析经济模型的解随参数的变化而变化的情况。n 经济模型中多数可检验的预测和政策含义源于比较静态分析。n 可以是定性的，也可以是定量的。l 比较静态分析的常用工具n 隐函数定理n 包络定理5.3.1 隐函数定理l 开集上的方程组 (5.10)n 设在处的解为，称方程组在处局部有解n 方程组的隐式解(implicit solution) 对某些包含的开的参数集和对某些包含的变量集，存在惟一决定的函数，使得，l 定理5.8 (隐函数定理) 假设方程组(5.10)满足：(i)，在处连续可微；(ii) 是方程组在处的解；(iii)偏导数向量矩阵是非奇异的，即秩则：1方程组在处局部有解；2隐函数连续可微并且

8、 在1个变量和1个参数的情形下，隐函数公式为 l 考虑一维的情形，并设是方程的惟一可微的解。于是，由给定。对求导，利用链式法则，有:则在，处，可得隐函数的公式。l 例5. 3 隐函数定理在最优化问题中的应用考虑由开的参数集定义的等式约束最优化问题，Lagrange定理隐性刻画了问题的解。任意解必须求解以下个方程设是方程组的解，是函数。定理的第一部分表明：若对左边每个方程关于和求导，则解是可微的；定理的第二部分为导数和提供了计算公式。l 隐函数定理的注意点n 定理保证方程组在处有惟一的局部解，但不保证是给定的全局解。n 有多个解时，需要更细心一些u 在图5.5中，每个解对参数的变化做出不同的反应

9、。图5. 5 最优解可能不是全局惟一解n 只有偏导数矩阵非奇异时，才能应用定理图5.6 奇异时，解可能不是局部惟一的5.3.2 包络定理l 定理5.10 平滑包络定理 假设是问题：的局部极大点，如果：(i) 是连续的、凹的；(ii) 在点处二次连续可微; (iii) 在点处紧约束是线性无关的；则值函数可微，满足其中为Lagrange函数，而是与相联系的(惟一的)Lagrange乘子。l 例5.4 消费者问题的Lagrange函数利用定理5.9，有可见，在最优消费组合处，收入的微小增加如何在不同的商品之间划分是无关紧要的，无论增加的收入怎么消费，效用的变化都是相同的。此时，Lagrange乘子可

10、以视为收入的边际效用。l 更一般的结果定理5.11 包络定理假设问题满足：(i) 连续；(ii) 紧；(iii) 在中连续则在最优解为单值时，值函数可微，并且l 定理5.10的优势n 不要求关于可微，只要求对参数可微。n 可用于可行集是离散的情形：图5.7u 在每个处的最优选择是在该处最高的曲线。u 值函数是目标函数的上包络。u 在最优解惟一时，值函数可微，其导数等于目标函数在该点的导数。n 这一洞察可以推广到更一般的选择集上，其中值函数始终是目标函数的上包络。图5.7 值函数是目标函数的上包络例5. 5 (最优位置) 假设某一产品需求的分布定义为：其中：是卖主的位置，是衡量需求的位置。设价格

11、为1，边际成本为0，问题为：最优解为，值函数为。假设卖主的位置只位于一个端点上，即。此时，最优解需定位于尽可能接近于需求并且值函数为如图5.8，除了在处(此时多值)之外，值函数是可微的，满足。图5.8 值函数可微(除了在处)5.4 单调比较静态分析5.4.1 隐函数定理的局限性5.4.2 单个选择变量的单调比较静态分析5.4.3 使用技巧：参数化和聚合5.4.1 隐函数定理的局限性l 问题：解集何时在中单调不减或严格递增？l 隐函数定理的局限性n 未必可微，甚至未必是函数n 即使是可微函数，也未必能识别其符号。_例5.6 (隐函数定理的条件) 问题 (5.11)其中，函数且严格凹(从而)。对每

12、个，问题(5.10)都有一阶条件确定的唯一解。由于严格凹，因此隐函数定理的条件满足，于是同时，l 隐函数定理的严格要求n 光滑,且最优化问题对每个参数有唯一解n 严格凹时，才能标识在整个参数区间的微分符号。l 错误认识：光滑或凹性对判断对的效应很重要5.4.2 单个选择变量的单调比较静态分析l 考察单变量、单参数和一个固定约束集的情形：n 设，其中，问题为，其中 (5.14)n 设存在；但解不必唯一，可能是集合。l 定义5.2 (强集序) n ，若，则称在强集序(strong set order)中，。例5.6 (强集序)：如图5.9，在上方图形中，但在下方图形中，这一关系不成立。图5.9 强

13、序集l 单调不减n 若是函数，则是标准的函数单调不减n 若是紧值对应，则函数和单调不减l 定义5.2 (超模) 是上的超模(supermodular)，在上单调不减n 这一定义指：是上的超模更大，选择更大的(即)所得到的增量收益更大l 超模的定义不要求可微，但若可微，则n 引理5.1 设为，是上的超模，l 定理5.11 (Topkis单调性定理) 是上的超模单调不减例5.7 设垄断厂商面临如下问题：垄断厂商的产量；时的市场价格成本函数，参数影响垄断厂商的成本n 设垄断厂商的最优产量n 若，则目标函数是超模。于是，只要减少生产的边际成本，则是非递减的。n 注意，在得到这一结论时，无需假设需求函数

14、或者成本函数的凹性。l 如何表明单调不增？n 只要目标函数在中是超模即可。5.4.3 使用技巧：参数化和聚合l 参数化(parameterization)n 比较和的解n 引入参数，并建立二值(dummy)函数：u 若是超模，即非递减，则u 故的解比的解大l 聚合(aggregation)n 在多个选择变量之下，我们可能只想获得关于一个变量的结论。n 此时可通过“聚合”我们较不关心的选择变量来使用Topkis定理n 问题：u 若只对的行为感兴趣，可将问题表述为：，其中u 若在中是超模，则Topkis定理声称，在问题中，是单调不减的。例5.8 (竞争性厂商) n 设竞争性厂商用种投入生产一种产出

15、其中为产品价格，为投入品价格，是生产函数。若我们只对如何影响产出感兴趣，则问题可表述为，其中其中为成本函数。由于在中有递增的差，因此，不管生产函数的形状如何，厂商的供给曲线都是非递减的。5.5 对偶原理5.5.1 Lagrange对偶函数5.5.2 Lagrange对偶问题5.5.3 对偶性和Slater约束条件5.5.4 影子价格：对偶性的经济学解释5.5.1 Lagrange对偶函数l 定义5.2 (Lagrange对偶函数)设与问题 (5.2)相关的Lagrange函数为。Lagrange对偶函数(Lagrange dual function)，或对偶函数(dual function)L

16、agrange函数在上的最大值，即：n 若向上无界，则取。l 定理5.13 对偶函数产生问题(5.2)的最优值的上界，即，有 (5.1)l 只有当且时，对偶函数才给出最优值的上界。将满足和的向量对称为对偶可行(dual feasible)。5.5.2 Lagrange对偶问题l 问题 (5.18)是与问题(5.2)相联系的Lagrange对偶问题(Lagrange dual problem)。n 初始问题(5.2)称为原问题(primal problem)。n 若是问题(5.18)的最优值，则称之为对偶最优(dual optimal)或对偶最优乘子 (optimal Lagrange mult

17、ipliers)。n 由于Lagrange对偶问题(5.18)的目标函数是凸函数，同时约束条件是凸集，因此无论原问题(5.2)是不是凸的，对偶问题 都是凸规划问题。例5.9 线性规划问题(linear programming problems) 的一般形式 ，其中。对偶函数为除非，否则线性函数的上确界为。于是，对偶函数为如果且，则对偶变量是对偶可行的。此时，对偶问题可以表示为5.5.3 对偶性和Slater条件l 弱对偶性(weak duality)n 设Lagrange对偶问题(5.18)的最优值为。n 可通过对偶问题获得原问题的最优值的上确界。n 即使原问题不是凸的，仍有： (5.19)这

18、一性质称为弱对偶性。n 当和为无限时，(5.19)仍然成立。u ：对偶问题不可行u ：原问题不可行。l 强对偶性(strong duality)n 当等式成立时n 意味着通过对偶问题获得的上确界是紧的。l 强对偶性一般不成立n 如果原问题(5.2)是凸的，对偶性通常(但不总是)成立。n 约束条件(constraint qualification)：以凸性为基础，强对偶性成立的问题的条件l Slater条件(Slaters condition)n 原问题(5.2)的约束集D中存在非空内点，使得 (5.20)成立。n 为严格可行的(strictly feasible)l Slater定理(Slat

19、ers theorem)n 原问题凸的，且Slater条件成立强对偶性成立l 原问题的一些不等式约束函数为仿射的，可改写Slater条件。n 设是仿射的，若以下的较弱条件成立，则强对偶性成立：n 原问题(5.2)的约束集D中存在(相对)内点，满足： (5.21)l Slater条件(5.20)及其改写形式(5.21)不仅表明凸规划问题的强对偶性，而且表明当时，对偶最优值可以达到，即存在满足的对偶可行。5.5.4 影子价格：对偶性的经济学解释l 设表示运营条件，表示利润。约束代表某些限制，寻求在这些限制之下最大化利润的运营条件可表示为问题： l 设想厂商可以违反限制的情形n 违反的数量，n 违反

20、限制的每单位价格n 厂商为第种限制或约束而支付的数量为。l 厂商的支付也可以发生在约束不紧时：n 时，厂商可用同样的价格卖出第种约束的任意未使用的部分，表示厂商可得到的收入。n 假设，这意味着厂商必须为违反限制而支出，而当约束不紧时可以得到收入。l 厂商的净利润：nn 厂商以最大化利润的方式运营，这带来利润。因此，对偶函数表示厂商的最优利润。n 最优对偶值则是厂商在最不利的价格集合下厂商的最优利润。l 弱对偶性的理解n 在违反的约束可以被买卖的(第二种)情形中，厂商的最优利润要大于或等于不能违反约束的(第一种情形中的)最优利润，即便是在最不利的价格下也是如此。l 强对偶性的理解n 强对偶性成立，且可以得到对偶最优值。n 可将对偶最优向量理解为价格集，在这一价格集中，允许违反买卖约束的厂商不占优势。n 鉴此，对偶最优向量称为原问题(5.2)的影子价格(shadow price)。62