3 凹函数与拟凹函数.pdf

1 第第 3 章章 凹函数凹函数 3 1 光滑函数与齐次函数光滑函数与齐次函数 3 2 光滑函数的凹性光滑函数的凹性 3 3 保持凹性的运算保持凹性的运算 3 4 拟凹函数拟凹函数 2 3 1 光滑函数与齐次函数光滑函数与齐次函数 3 1 1 梯度的几何性质梯度的几何性质 3 1 2 Hessi 矩阵的定性矩阵的定性 3 1 3 Taylor 展开展开 3 1 4 齐次函数齐次函数 3 光滑函数 smooth function 是可以近似表达为线性 函数的非线性函数 它们的图形没有间断和折点 光滑函数的线性近似实际上属于微积分的范畴 4 3 1 1 梯度的几何性质梯度的几何性质 梯度 1 N xx fff xxx 向量 1 N ddxdx x 表示从x出发的变化方向 具体取决于每一个分量变化的大小 图3 1 向量dx的几何含义 5 全微分 1 1 N xxn dffdxfdxfd xxxxx 3 1 即 f 在点x处的全微分恰好是梯度 f x和向量 dx的 内积 曲线 fc x的水平集 level set LX fc xx 常见例子 无差异曲线 效用函数的水平集 等产量曲线 生产函数的水平集 6 梯度 0 f x的几何含义 0 f x是与切平面垂直的向量 即法向量 0 f x在点 0 x处指向 f 变化的法方向 图3 2 梯度向量的几何含义 7 例 3 1 水平集的斜率 设 2 f 在点 0 x处可微 存在 超平面 0 0HXf xx dx在点 0 x处与水平集相切 H 由下式定义 12 00 12 0 xx fdxfdx xx 其斜率为 1 2 0 2 0 1 x x f dx dxf x x 即 f 在点 0 x处的偏导数之比 若 f 为效用函数 则水平集为无差异曲线 而两种商 品之间的边际替代率衡量无差异曲线的斜率 若 f 为生产函数 则水平集为等产量曲线 而两种投 入之间的边际技术替代率衡量等产量曲线的斜率 8 3 1 2 Hessi 矩阵的定性矩阵的定性 矩阵的定性 A为N阶方阵 A正半定0 TN z Azz A正定0 TN z Azz A负半定 A正半定 A负定 A正定 A不定 NT zz Az 既有正值也有负值 9 主子式和顺序主子式 ij N N a A的K阶主子阵 从A中划去NK 行和相同的NK 列 由此形成的KK 阶子矩 阵 对应的行列式称为A的K阶主子式 ij N N a A的K阶顺序主子阵 从A中划去后 后NK 行和NK 列 由此形成的KK 阶子 矩阵 对应的行列式称为A的K阶主子式 10 例 3 2 三阶方阵 111213 212223 313233 aaa Aaaa aaa 有 1 个三阶主子式 3 个二阶主子式 3 个一阶主子式 有 3 个顺序主子式 11 定理 3 1 对称矩阵S的定性 S正定 S的N个顺序主子式都为正数 S负定 S的N个顺序主子式依次改变符号 奇数顺序的为负 而偶数顺序的为正 S正半定 S的21 N 个主子式都非负 S负半定 S的21 N 个主子式依次改变符号 奇数顺序的为负 而偶数顺序的为正 12 例 3 3 Cobb Douglas 函数 12 12 aa fx x x的梯度向量为 1212 11 1 12212 aaaa fa xxa x x x Hessi 矩阵为 1212 1212 211 2111212 12 112 12 122212 1 1 aaaa aaaa a axxa a xx f a a xxa ax x x 12 1 3 2 3aa 则f在点 8 8 的梯度为 1 2 8 8 3 3 f Hessi矩阵为 2 11 1 8 8 1136 f 它的三个主子式 1 11 2 1 12 2 2 12 2 0 0 0 x xx x x xx x x xx x ff ff ff 因此 在点 8 8 处 海赛矩阵是负半定的 13 3 1 3 Taylor 展开展开 中的Taylor定理 f 是开区间S 上的 1n C 单值函数 0 xS 0 xSx 在 0 x和x之间存在x 使得 21 1 00000 1 2 1 nn nn xxxx f xxf xf xfxfxfx nn 中的二次近似表示 f 是开区间S 上的 3 C实值函数 0 xS 0 xS xx 满足 22 0000 1 2 f xxf xfx xfx xo x 14 N 中的二次近似表示 f 是点 0 x的凸邻域 N S 上的 3 C单值函数 S x 0 xx 满足 000202 1 2 T ffffo xxxx xxx xx 其中 余项 2 ox为可以忽略不计的向量x的模的 平方的无穷小量 进一步地 在点 0 x和 0 xx之间存在点x 使得 0002 1 2 T ffff xxxx xxx x 15 例3 3 Cobb Douglas函数 例3 1中的Cobb Douglas函数 1 32 3 12 fxx x在点 8 8 处的二次Taylor展开近似表示为 00020 11 12 22 22 121122 1 2 11 1 211 8 113 3236 121 8 2 3372 T ffff xx x x xx xxxx xx xxxx xxx x 16 3 1 4 齐次函数齐次函数 齐次函数 f 是K次齐次 S x 0t K f tt f xx 经济分析中的齐次函数 生产者理论 规模报酬不变意味着生产函数是1 次齐次的 价格函数 如利润函数中 它对应于相对价格不 变时的规模 经济学中最常见的情形是0次或1次齐次 0次齐次函数沿着任何射线都是常数 1次齐次函数沿着所有射线都是线性的 有时 也称为线性齐次的 linearly homogeneous 17 例 3 4 Cobb Douglas 函数 Cobb Douglas函数 1 1 N N fxx x 是 1 N n n a 次齐次的 因为对0t 12 1212 1 12 12 N NN N n n aaa N aaaaaa N a f ttxtxtx tx xx tf x x 18 例3 5 经济学中的一些齐次函数 规 模 弹 性 不 变 constant elastic scale CES 函 数 1 1 122 NN fa xa xa x x 是 1 次齐次的 需求函数 n xmp衡量给定价格p和收入m时商品 n x的需求量 例 1 1 它是 0次齐次的 间接效用函数 max Xm vmu xp px 在p和m中是 0 次齐次的 竞争性厂商的利润函数 max T Y y pp y是 1 次齐次 的 竞争性厂商的成本函数 cyw在投入价格w中是 1 次齐次的 19 齐次函数的性质 f 是K次齐次可微函数 f 的偏导数1K 次齐次 f 是1次齐次可微 nn txx ftf xx f 是K次齐次可微 1 n N nx n Kfx ff xxx x 20 3 2 光滑函数的凹性光滑函数的凹性 3 2 1 凹性的定义凹性的定义 3 2 2 一阶条件一阶条件 3 2 3 二次条件二次条件 3 2 4 例子例子 3 2 5 上水平集上水平集 3 2 6 下图下图 21 3 2 1 定义定义 f 凹 12 D x x 0 1 1212 1 1 fff xxxx 3 9 f 严格凹 xx 0 1 上式严格成立 f 凸 f 凹 f 严格凸 f 严格凹 22 例 3 5 利润函数 竞争性厂商的利润函数 max T y Y pp y在p中是凸的 设 1 Y最 大化价格 1 p时的利润 2 Y最大化价格 2 p时的利润 对 0 1 设加权平均价格 12 1 ppp 设y最大化p时的利润 则 1212 1 1 TTTT pp yppyp yp y 由于 1 y 2 y分别最大化 1 p 2 p时的利润 因此 1111 2212 1 1 1 TT TT p yp yp p yp yp 12 12 12 1 1 1 T T TT pp y ppy p yp y pp 利润函数 p在p中是凸的 23 函数是仿射的 从而线性的 该函数既凸又凹 凸集D上的f是凹的 S x和v g tft xv在 ttS t xv 上是凹的 通过将函数限定在一条直线上 这一性质可检 查函数是否为凹 凸函数在定义域的内部是连续的 但可能在边界上 不连续 24 3 2 2 一阶条件一阶条件 f 是开凸集 N D 上的 1 C单值函数 f 凹 0 D x x 000 fff xxxxx 3 10 凹函数 f 的图像位于经过其上任一点 00 xf x的切线 0000 0 lxf xfxxx 的 下方 000 lff xxxx 00 fxx 图3 4 凹函数的一阶条件 25 式 3 10 表明 凹函数的一次泰勒近似是 f 的全局高估量 global overestimator 反之 如果函数的一阶泰 勒近似总是函数的全局高估量 则函数是凹的 借助凹函数的局部信息 即它在一点的值和导数 可以导出全局信息 即它的全局高估量 例子 式 3 10 表明 0 f x0 D x 0 ff xx 也即 0 x是f的全局最大点 26 严格凹性 f 严格凹 0 D x x 0 xx 000 fff xxxxx f 凹 0 D x x 000 fff xxxxx 27 一阶凹性条件的证明 1n 的情形 f 凹 12 x xD 0 1 t 121 xt xxS f 凹 12112 1 f xt xxt f xtf x 3 11 1211 21 f xt xxf x f xf x t 0t 可得式 3 11 12 x xD f 满足式 3 11 12 xx 0 1 令 12 1 yxx 应用式 3 11 1122 f xf yfy xyf xf yfy xy 12 1 f xf xf y f凹 28 一般的情形一般的情形 12 N S x x 考虑 21 1 g tf tt xx 有 2121 1 g tf tt xxxx f凹 g凹 1 0 0 ggg 21121 fff xxxxx 3 12 21 1 ttD xx 21 1 ttD xx 21212121 1 1 1 f ttf ttf tttt xxxxxxxx g tg tg t tt g凹 29 3 2 3 二阶条件二阶条件 2 fC f 凹 2 f 负半定 在 上 0fx 在点x有负曲率 30 例 3 6 二次函数 N f 1 2 TT fSr xxxq x 其中S为NN 阶实对称矩阵 N q r x 2 fS x f 凹 S负半定 f 凸 S正半定 f 严格凹 S负定 f 严格凸 S正定 31 3 2 4 例子例子 上的一些例子 指数函数 ax e在 上凸 幂函数 01a a x在 上凹 1a 或0a 时是凸的 绝对值的幂 1p px在 上凸 对数 log x在 上凹 非负熵 logxx在 上 严格 凸 证明方法 1 验证式 3 11 2 检验二次导数 32 N 上的例子 范数 N 上的每个范数都是凸函数 最大值函数 1 max N fxx x在 N 上凸 二次与线性之比 函数 x y xy 上的 2 f x yxy 是 凸的 图3 2 图3 2函数 2 f x yxy 33 指数之和的对数 函数 1 log N xx fee x 在 N 上凸 2N 时的情形如图3 3 图3 3 函数 log xy f x yee 几何平均函数 1 1 N N n n fx x在 N 上凹 34 验证方法 1 直接验证式 3 11 2 验证Hessi矩阵是正半定的 3 函数约束在任意直线上 并验证所产生的一元函数 的凹性 35 范数 范数 N f 0 1 则 121212 1 1 1 fffff xxxxxx 不等式基于范数满足三角不等式 等式源于范数的齐次性 最大值函数 0 1 maxn n fx x满足 1212 12 12 1 max 1 max 1 max 1 nn n nn nn fxx xx ff xx xx 36 二次与线性之比 函数 对0y 2 2 332 22 T yyyxy f x y xxyyxyx 0 指数之和的对数 函数 2 1 diag TT T f x1 zzzz 1 z 其中 1 N xx ee z 为验证 2 f x是正半定的 必须表 明 v 2 0 T f vx v 即 2 22 111 1 0 NNN T nnnnn T nnn fzv zv z vx v 1 z 37 设 nnnnn avzbz 应用Cauchy Schwartz不等式 2 TTT a ab ba b 可得上式 几何平均函数 海赛矩阵由以下两式给定 1 1 22 11 2222 1 NN NN ni nn kkklki xx ff nkl xn xx xN x x xx 表示为 1 2 1 222 1 11 diag N N n T n N x fN Nxx xqq 其中1 nn qx 须表明 2 f x负半定 即对 v 1 2 2 2 1 22 11 0 N N n NN T nnn nn nn x vv fN Nxx vx v 38 设 a1 nnn bvx 应用Cauchy Schwartz不等式 2 TTT a a b ba b 可得上式 3 1 5 上水平集上水平集 凸集D上的 N fD 的 上水平集 superlevel set UD f xx f 凹 它的 上水平集U 是凸的 相反的情形不成立 如 x f xe 的上水平集是凸的 但它在 上 不是凹的 而是严格凸的 39 f 凸 它的 下水平集 SD f xx凸 40 例3 9 N x 的几何和算术平均分别为 1 11 1 N NN nn nn GxAx N xx 在 G 的定义中 取 1 00 N 算术 几何平均不等式表明 GA xx 设 0 1 考察 N GA xxx 即几何平均不小于算术平均的 倍的向量的集合 这一集合是凸 的 因为它是凹函数 GA xx的0 上水平集 事实上 该集合是非负齐次的 因而是凸锥 41 3 1 6 下图下图 n fD 的图形 graph 为 fD xxx 它是 1n 的子集 n fD 的下图 hypograph 为 hypo ffD xxx 42 f 凹 它的下图是凸集 f 凸 上图 epigraph epi ffD xxx 凸 凹函数的许多结果可以利用下图进行几何解释 如凹性的一阶条件 000 fff xxxxx 其中 n fD 是凹的 0 D x x hypof x 000 fff xxxxx 0 00 0 1 1 ff f xx xx x 43 这意味由向量 1f x确定的超平面在点 00 fxx处支撑hypof 如图3 8 hypof 00 fxx 1f x 图3 8 向量 1f x确定的 在点 00 fxx处的hypof的支撑超平面 44 例3 8 生产函数 厂商用N种投入生产一种产出的技术 投入要求集 N V yyY xx 生产函数 production function sup fyV y y xx 生产函数与生产可能性集 Yy yy 在技术上可行 给定 f n x 定义 gfxx Y 是 g 的下图 f凹 Y凸 生产函数凹 技术呈现规模报酬非递增 生产函数严格凹 技术呈现规模报酬递减 45 3 3 保持凹性的运算保持凹性的运算 3 3 1 非负加权之和非负加权之和 3 3 2 仿射映射的复合函数仿射映射的复合函数 3 3 3 复合函数复合函数 46 3 3 1 非负加权之和非负加权之和 f 凹 f x凹 1 f 和 2 f 凹 12 ff 凹 m f 凹 1 m wmM 1 1 M M w fw f 凹 类似地 凸函数的非负加权之和是凸的 严格凹 凸 函数的正加权之和是严格凹的 凸的 47 3 3 2 仿射映射的复合函数仿射映射的复合函数 设 N fD 矩阵 MN A M b 定义 M gS 为 gf A xxb 其中 SAD xxb f 凹 g 凹 f 凸 g 凸 48 3 3 3 复合函数复合函数 设 h n g 其复合函数 hgfD 定义为 fh g xx 其中 dom dom dom fg gh xx 复合函数的凹 凸 性 h 凹和非递减 g 凹 f 凹 h 凹和非递增 g 凸 f 凹 h 凸和非递减 g 凸 f 凸 h 凸和非递增 g 凹 f 凸 49 例3 9 一些简单的复合结果 g 凹 g e x 凹 g 凹和正的 log gx凹 g 凸和正的 1 gx凹 g 凹和非负 1p pg x凹 g 凹 logg x在 0g xx上是凹的 50 3 4 拟凹函数拟凹函数 3 4 1 定义定义 f 拟凹 quasiconcave 12 D x x 0 1 1212 1 min fff xxxx f 严格拟凹 quasiconcave 12 D x x 0 1 1212 1 min fff xxxx f 拟凸 quasiconvex f 拟凹 f 严格拟凸 f 严格拟凹 f 拟线性 quasilinear f 既拟凹又拟凸 51 几何意义 设 12 D x x 12 ff xx 拟凹性要 求 从 低点 2 x沿直线移动到 高点 1 x时 f 的函数值不低于 2 f x 1 x 1 f x 2 x 2 f x f x x 图3 9 拟凹函数 52 定理3 6 设 N fD 定义在凸集D上 f 拟凹 上水平集 UD f xx 凸 f 拟凸 下水平集 SD f xx 凸 f 拟线性 水平集 LD f xx 凸 直接结论 凹 拟凹 拟凹函数不具有凹函数的某些性质 在定义域中的某些内点处可能不连续 其非负线性组合未必是拟凹函数 53 例3 11 凸偏好 凸偏好 convex preference 指在平均的和极端的消费组合之 间 消费者更偏爱平均的消费组合 反映凸偏好关系的效用函数 u 拟凹 54 例3 12 凸技术 投入要求集 V y是生产函数 f 的上水平集 N V yfyxx V y凸 f 拟凹 生产函数凹 生产可能性集凸 凸技术假定 V y凸或 fx拟凹 该假定不排除 规模报酬递增的存在 55 拟凸函数的经济学例子 例3 13 间接效用函数 消费者间接效用函数 max Xm vmu xp px 例1 3 在价格向量p中是拟凸的 56 上的拟凹函数 图中 上水平集U 是区间 a b 因而是凸的 上水平集U 是区间 c a b c 图3 10 上的拟凹函数 57 拟凹函数可以是凸的 或者是不连续的 对数函数 上的log x既是拟凹的 又是拟凸的 因而是拟线性的 上限函数 ceil inf zxzx 是既是拟凹的 又 是拟凸的 因而是拟线性的 其中Z是整数集 58 N 上的一些例子 例3 13 2 上的单值函数 1 2 fx x x既非凹也非凸 因为 2 01 10 f x 是不定的 它有一个正的 一个负的特征根 但 f 是拟凹的 因为它的 上水平集 2 12 Ux x x 是凸的 不过 f 在 2 上不是