logo资料库

最优化 kkt条件.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.32M 资料格式：pdf 举报 版权申诉
第1页 / 共42页
第2页 / 共42页
第3页 / 共42页
第4页 / 共42页
第5页 / 共42页
第6页 / 共42页
第7页 / 共42页
第8页 / 共42页
资料共42页，剩余部分请下载后查看
    S
    A Brief Lecture Notes on Optimization for Microeconomic Analysis1 冯 曲 复旦大学经济学院 中国经济研究中心 第一稿 2003 年 1 月 一切匠心都归功于 Dixit, Chiang, Takayama 等杰出的前辈；所有的错误、遗漏为编者所有。 他是个顽皮的孩子，不肯就安分的待在身旁；我们要做的是，不能让他的玩耍脱离我 们的视线。 1 欢迎指出错误及评论。qufeng@fudan.edu.cn 1
    目 录 A.最优规划问题…………………………………………………..………..3 B.梯度向量…………………………………………………………………3 B.1.无约束极值问题…………………………………………………..3 B.1.1 向量的内积…………………………………………………4 B.2.约束极值问题……………………………………………………..6 B.2.1 雅克比矩阵…………………………………………………8 B.2.2 隐函数定理…………………………………………………8 B.2.3 超平面………………………………………………………9 C.等式约束极值的拉格朗日求解法……………………………………..10 D.非线性规划问题的求解：库恩－塔克条件…………………………..11 E.二阶条件………………………………………………………………..14 E.1 无约束极值问题…………………………………………………14 E.1.1 泰勒展开…………………………………………………..14 E.1.2 二次型…………………………………………………….16 E.2 等式约束极值问题……………………………………………….17 E.3 不等式约束问题………………………………………………….21 F.凹规划……………………………………………………………………22 F.1.1 凸集…………………………………………………………22 F.1.2 凸函数………………………………………………………22 F.1.3.凹函数………………………………………………………23 F.2.凹规划……………………………………………………………..24 F.3.拟凹函数、拟凸函数……………………………………………..25 G.最优化问题的解…………………………………………………………28 G.1.基本概念…………………………………………………………..28 G.1.1 紧集…………………………………………………………28 G.1.2.函数的连续…………………………………………………28 G.1.3 韦氏定理……………………………………………………28 G.2.解的存在性和唯一性……………………………………………..29 G.2.1.存在性定理…………………………………………………29 G.2.2 唯一性定理…………………………………………………30 G.3 分离……………………………………………………………….31 H.比较静态分析……………………………………………………………33 H.1.基本思想 …………………………………………………………33 H.2.一般方法……………………………………...……………………34 I. 包络定理…………………………………………….…………………….36 I.1.最大值函数…………………………………………………………36 I.2.包络定理……………………………………………………………37 I.3.拉格朗日乘子的含义………………………………………………39 I.4.包络定理的应用……………………………………………………40 2
    A.最优规划问题： xf )( max x ts .. xg =)( c 这样一个规划问题可以用来表达一个在一定资源约束情况下的经济决策问 题，其中 )(xf 称为目标函数， x为选择变量， )(xg 为约束函数。如果用集合 S ＝{x|g(x)=c}表示约束，则此规划问题可以看作是在集合 S（可以看作是欧氏空 间的一个子集，称为可行集）上选择一个点 x（或向量），使得目标函数 f(x)的 值最大。如下图，在二维情形下，S 表示可行集，f(x)=k 表示目标函数的等值线， 则上述规划问题就变成了在 S 中找一点，使得目标函数的等值线达到一个最高 的位置。 从这样的角度看规划问题，我们可以将研究的重点放在目标函数的性质和 可行集的性质两个部分。 x2 S grad f f(x)=k x1 图 A.1 B.梯度向量 梯度 grad f 的概念一般和目标函数的等值线（面）的变化有关。我们分两 种情况来从梯度的角度看最优化问题。 B.1.无约束极值问题： 一维情况下： f ' x )( ⋅ = dx xdf )( 此时，目标函数值的变化，是两部分的乘积，第一部分是导数，第二部分是 x 的微分，或者说是 x 的变化，可以取正也可以取负。 若 f )(' >x 0 ，则可以取 0>dx ，使得 >xdf )( 0 ，即通过点 x 的移动，可以 使目标函数值增加；若 f )(' xdf )( 0 ，目标函数 3
    值还可以继续增加。因此，当 f(x)取得极值，即目标函数值不再增加时，上述 情形不可能发生，即有 f )(' =x 0 。 含义：一维无约束极值问题中，目标函数的梯度就是导数，表示目标函数 值变化（增加）的方向。 多维情形下： xdf =)( f x ⋅ dx 此时， xf 即为 )(xf 在点 x 处的梯度向量，为横向量（ f L ，其中每一个分 ,1 nf ) , 量为偏导数； dx 为纵向量，表示 x 的变化。上式表示目标函数 )(xf 的变化可以 用梯度向量和 dx 的内积来衡量： xdf )( = f x ⋅ dx = ( f , 1 , f n L dx 1 M dx n   )         = dxf 1 1 + + f n dx n L B.1.1 几何意义：向量的内积 x,y 是两个向量，其内积定义为： yx =⋅ ( x 1 , , x n L y 1 M y n   )         = yx 11 + + yx n n L 同时，也可以表示成： yx =⋅ yx αcos ，或 =αcos yx ⋅ yx ，其中α表示向 量 x,y 之间的夹角， yx , 分别表示向量 x,y 的模（原点到点 x、y 的距离）。 如果 0 ≤ α< ，则 0>⋅ yx ； α= ，则 0=⋅ yx ，即向量 x,y 正交（垂直）； π 2 π 2 πα ≤ π 2 < ，则 0<⋅ yx 现在分析梯度向量 xf 和 dx 的几何意义： dx 代表欧氏空间中一点 x 微小变化的向量，方向可以是前后左右上下，取决 于每一个分量变化的大小。具体的，如下图，以二维为例， dx = ( dx 1 dx , 2 ) 的分 量分别表示从点 x 出发横轴和纵轴变化的方向，向量 dx 则表示从点 x 变化的整 体方向，具体的，满足平行四边形法则。 4
    x2 dx dx2 x dx1 x1 图 B.1 与无约束问题相比，存在约束时，现在可以选择的点（可行集）不再是整 个欧氏空间，而是由具体的约束条件构成的欧式空间的一个子集。因此，此时 从点 x 移动的方向不再是任意的，而只能在这个可行集内移动。可以想象一下： 在一个没有围墙的校园内，可以向任何方向行走；如果有了围墙，则在围墙的 附近就不能朝任意方向了，最多只能沿着围墙走。如在消费者选择的问题（两 个商品的情形），其约束满足： x ,0 2 xp 2 x 1 = + I , 2 xp 11 x2 ≥ ≥ 0 fx x dx x1 图 B.2 预算线如同围墙一般，在其附近就只能沿其方向移动。 从代数上看，我们也可以得到上述直观的理解，对上式两边全微分，并且 , 是参数，保持不变，得： Ipp , 1 2 dxp 1 1 + dxp 2 2 = 0 与无约束相比， dx 1,dx 2 的大小不是任意的，而是相互联系的，即确定了 1dx ， 则 2dx 也就相应确定了（一般的，相互联系的机制有约束条件决定）。在这个例 子中， 2dx 和 1dx 的比例就等于预算线的斜率，作为平行四边形对角线的 dx 的方 向也就确定了，就是沿预算线移动。 梯度向量 xf 的几何意义是：等值面 xf =)( k 在点 x 处指向值增加（变化） 的法方向，也就是在点 x 处 f(x)值增加最快的方向，其变化率为 xf 的模。如上 5
    图，无差异曲线（二维情形下，等值面就是无差异曲线）上点 x 处作切线（多 维情形下就是切平面）， xf 就是和切线垂直的、无差异曲线增加的向量。 由上述的讨论，对于 xdf =)( f x ⋅ dx ，如果梯度向量 xf 和 dx 的方向是一致的 （夹角小于 π 2 ），则 >xdf )( 0 ，即从点 x 移动，可以使 )(xf 的值增加；如果梯 度向量 xf 和 dx 的方向不一致（夹角大于 π 2 ），则 xdf )( 0 。故而当目标函数在点 x 取得极值处，一定有梯度向量 f x =x )( 0 ，这 就是无约束极值问题的一阶条件。 B.2.约束极值问题 当存在约束（不管是等式约束还是不等式约束）时，点 x 处的变化方向是 有限制的，即向量 dx 不是任意的。比如在上面所举的消费者选择的例子中，在 预算线上，向量 dx 的方向为沿预算线移动。此时，按我们上面对梯度向量 xf 和 向量 dx 的几何意义的讨论，当点 x1（x3）处梯度向量 xf 和向量 dx 不正交时，所 以向右（左）移动，可以使目标函数值增大；在点 x2 处，梯度向量 xf 和向量 dx 正交， =xdf )( 0 ，目标函数取得极值。由前面的讨论，向量 dx 的方向即为预算 线的方向，而梯度向量 xf 为无差异曲线的法方向，也就是与无差异曲线切线垂 直的方向，由几何知识，我们知道，在点 x2（最优解）处，无差异曲线的切线 的斜率一定于预算线的斜率相同，如图示，无差异曲线在点 x2 处一定于预算线 相切。这个结论与我们在消费者选择定性讨论的结果是一致的。 6
    x2 x1 x2 x3 x1 图 B.3 一般的，约束由等式 xG =)( c 表示，点 x 的变化向量 dx 是受限制的，具体 的，将约束等式全微分， 0 dxG 1 = + 1 + ndxG n L 由于 c 是常数，等式的右边等于零。写成向量的形式为： G ( 1 , L , G n ) ⋅ dx 1 M dx n           = 0 ，或 Gx ⋅ dx 0= ，其中 G x L= G ( 1 , , G n ) 因此，在点 x 处，向量 dx 的方向由上式确定，即向量 dx 与向量 xG 垂直。 由在最优解 x 处，满足 f x ⋅ dx 0= ，即梯度向量 xf 与向量 dx 垂直。由几何知识， 我们知道，在最优解 x 处，梯度向量 xf 一定与向量 xG 平行，即存在常数λ使得： G f λ= x x ，或 f x G x λ= 这就是我们熟悉的等式约束极值问题的一阶条件。 正如前面对梯度向量 xf 的讨论，此处我们也可以将向量 xG 看作时约束函数 )(xG 在点 x 处的梯度向量，即等值面 xG =)( c 在点 x 处的法向量。由 Gx ⋅ dx 0= ， 向量 dx 与梯度向量 xG 是垂直的，或者说向量 dx 可以看作是等值面 xG =)( c 的切 平面中的一个向量。又由在点 x 处， f x ⋅ dx 0= ，即梯度向量 xf 和向量 dx 垂直， 也就是说向量 dx 也在等值面 xf =)( k 的切平面中。因此，在最优解点 x 处，两 个等值面 xf =)( k 、 xG =)( c 的切平面重合，推得法向量 xf 、 xG 平行，即有 7
    f λ= G x x 。 梯度向量 gradf 在一维的情形下就是导数 )(' x f ，而在 n 维情形下就是偏导 数向量 xf 。 B.2.1 雅克比矩阵 在上面的例子中，如果约束不是单个等式，而是由 m 个等式组成的，即 )(xG 和 c 都是向量，具体的： 1 xG ( 1 , L , x n ) = c 1 M xG ( 1 m , , x n ) = c m L 则此时， G x ≡ G ( 1 ∂ x ( ∂ 1 , L , L , , G x n m ) ) ≡ 1 G ∂ x ∂ 1 m M G ∂ x ∂ 1         , , L 1 G ∂ x ∂ n , L , m G ∂ x ∂ n ，我们称之为 )(xG 的雅克比         矩阵。在隐函数定理的讨论中，会涉及到雅克比矩阵的概念。 B.2.2 隐函数定理 i)在隐函数 ) =yxf ,( 0 中（ yx, 都是一维向量），如果在点 ( x 0 y , 0 ) 的一个领域内 有 0≠yf ，则 y 可以表示成 x 的函数，即 y φ= )(x ，并且 dy dx −= f f x y 。 ii)当 x 是 n 维向量时，如果在点 ( x 0 y , 0 ) 的一个领域内有 0≠yf ，则 y 可以表示 成 n 维向量 x 的函数，即 y φ= )(x ，且 y ∂ x ∂ i −= f f i y , i ,1 L= , n 。 这可以通过对隐函数 =yxf ,( ) 0 求全微分， dxf 1 1 + f nL + dx n + f y dy = 0 求得。 iii)当 y 是一个 m 维向量时，根据方程组的知识， y 的值要能够被确定， yxf ,( ) 也一定是一个 m 维的向量，即： f 1 ( x 1 , L , x ; y 1 , n L , y m ) = 0 M f m ( x 1 , L , x ; y 1 , n L , y m ) = 0 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料