最优化理论与方法概述PPT课件

《最优化理论与方法概述PPT课件》由会员分享，可在线阅读，更多相关《最优化理论与方法概述PPT课件（48页珍藏版）》请在装配图网上搜索。

1、第一章 最优化问题与凸分析根底在日常生活中，无论做什么事情，总是有多种方案可供选择，并且可能出现多种不同的结果。我们在做这些事情的时候，总是自觉不自觉的选择一种最优方案，以期到达最优结果。这种追求最优方案以到达最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论根底就是最优化理论，而凸分析又是最优化理论的根底之一。 1. 最优化问题最优化问题：求一个一元函数或多元函数的极值。 在微积分中，我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。 1.1 最优化问题的例子例1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何

2、剪法使水槽的容积最大？解：设剪去的正方形边长为x，由题意易知，此问题的数学模型为， 2max ( 2 )a x x 配 料 每 磅 配 料 中 的 营 养 含 量钙 蛋 白 质 纤 维 每 磅 本 钱 元 石 灰 石谷 物大 豆 粉 例2.混合饲料配合设每天需要混合饲料的批量为100磅，这份饲料必须含：至少0.8%而不超过1.2%的钙;至少22%的蛋白质;至多5%的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低本钱确定满足动物所需营养的最优混合饲料。 000 10005.008.002.0 10022.050.009.0 100008.0002.000

3、1.0380.0 100012.0002.0001.0380.0 100. 1250.00463.00164.0min 321 32 32 321 321 321 321 xxx xx xx xxx xxx xxxts xxxZ 解 :根 据 前 面 介 绍 的 建 模 要 素 得 出 此 问 题 的 数 学 模 型 如 下 :设 是 生 产 100磅 混 合 饲 料 所 须 的 石 灰 石 、 谷 物 、大 豆 粉 的 量 磅 。 321 xxx 最优化问题的数学模型一般形式向量形式其中1 21 2 1 2min ( )( ) 0 12. ( ) 0 12 ( )ni nj nf x x x

4、g x x x i lst h x x x j m m n ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 1 1( ) ( ) ( ) ( ) ( ) ( )T Tl mG X g X g X H X h X h X ， ， ， ， ，min ( )( ) 0. . ( ) 0fG Xs t H X ， ，X1 2( , , )nX x x x min. . 00jif xs t g xh x 目 标 函 数不 等 式 约 束等 式 约 束 称 满 足 所 有 约 束 条 件 的 向 量 为 可 行 解 ， 或 可 行 点 ， 全 体可 行 点 的 集 合 称 为 可 行

5、 集 ， 记 为 。x | 0, 1,2, , 0,1,2, , i jnD x h x i m g xj p x R 若 是 连 续 函 数 ， 则 是 闭 集 。( ), ( )i jh x g x DD 在 可 行 集 中 找 一 点 ， 使 目 标 函 数 在 该 点 取 最 小 值 ， 即满 足 ： 的 过 程 即 为最 优 化 的 求 解 过 程 。 称 为 问 题 的 最 优 点 或 最 优 解 ， 称 为 最 优 值 。 *x f x * *min . . . 0. 0j if x f x s t g x h x *x *f x定 义 1： 整 体 （ 全 局 ） 最 优 解

6、： 若 ， 对 于 一 切 ，恒 有 则 称 是 最 优 化 问 题 的 整 体 最 优 解 。定 义 2： 局 部 最 优 解 ： 若 ， 存 在 某 邻 域 ， 使 得 对 于一 切 ， 恒 有 则 称 是 最 优 化 问 题的 局 部 最 优 解 。 其 中 严 格 最 优 解 ： 当 ， 有 则 称 为 问 题 的严 格 最 优 解 。 *x D x D *f x f x *x *x D *( )N x*( )x N x D *f x f x *x* *( ) | , 0N x x x x *x x *f x f x *x 1.3 最优化问题的分类与时间的关系：静态问题，动态问题是否有

7、约束条件：有约束问题，无约束问题函数类型：线性规划，非线性规划 2、梯度与Hesse矩阵2.1 等值线二维问题的目标函数 表示三维空间中的曲面。在空间直角坐标系中，平面与曲面的交线在平面上的投影曲线为取不同的值得到不同的投影曲线。每一条投影曲线对应一个值，所以我们称此投影曲线为目标函数的等值线或等高线。1, 2( )t f x x 1 2( , )t f x xt C 1 2x x， 2 21 2 1 2( )f x x x x ， 2.2 n元函数的可微性与梯度梯度：多元函数 关于 的一阶导数 1 2( ) ( , , )Tnf f ff x x x x ( )f x x Hesse 矩阵：

8、多元函数 关于 的二阶偏导数矩阵 2 2 22 2 1 112 2 22 21 2 22 2 2 2 21 2f X f X f Xx x x xnxf X f X f Xf X f X x x x xnxf X f X f Xx x x xn n xn ( )f x x 例 ： 求 目 标 函 数的 梯 度 和 Hesse矩 阵 。解 ： 因 为 那 么 又 因 为 ： 故 Hesse阵 为 ： 2 2 21 2 3 1 2 2 3 3( ) 2 2 3f x x x x xx x x x 220 222 0222 Xf 2,2,2 0,2,2 232322222 312212212 xfx

9、x fxf xx fxx fxf TxxxxxxxXf 2331221 22,3222,22 233 22 xxxXf 211 22 xxxXf 3222 3122 xxxxXf 下 面 几 个 公 式 是 今 后 常 用 到 的 ： 1 ， 那 么 2 ， 那 么 (单 位 阵 3 ， Q对 称 ， 那 么 4 假 设 ， 其 中 f： 那 么 ： Tf X b X nnXfbXf 0. 2 12 Tf X X X IXfXXf 2. 12 Tf X X QX ., 2 QXfQXXf 0t f X tp .1RRn .: 11 RR 02 0 .TTt f X tp pt p f X tp

10、 p 3、 多元函数的Taylor展开 多 元 函 数 Taylor展 开 式 在 最 优 化 理 论 中 十 分 重 要 。许 多 方 法 及 其 收 敛 性 的 证 明 都 是 从 它 出 发 的 。 定 理 ： 设 具 有 二 阶 连 续 偏 导 数 。 那 么 ： 其 中 而 0 11: nf R R 212T Tf X p f X f X p p f X p .X X p )|(|21 |)(| 202000 000 popxfppxfxfpxf popxfxfpxf TTT 多 元 函 数 Taylor展 开 其 他 形 式 ： 0 0 02 20 0 0 0( )1( ) ( )

11、 (| | )2 TTf x f x f x x xx x f x x x o x x 凸 集 和 凸 函 数 在 非 线 性 规 划 的 理 论 中 具 有 重 要 作 用 ， 下 面给 出 凸 集 和 凸 函 数 的 一 些 根 本 知 识 。定 义 1 设 ， 若 对 D中 任 意 两 点 与 ， 连 接 与 的 线 段 仍 属 于 D； 换 言 之 ， 对 ， D， 0,1恒 有 +(1- ) D则 称 D为 凸 集 。 + (1- ) 称 为 和 的 凸 组 合 。nRD )1(x )2(x )1(x)2(x )1(x )2(x a)1(xa )2(xa)1(xa a )2(x )1

12、(x )2(x5、凸 集 、 凸 函 数 和 凸 规 划 例 规 定 ： 欧 式 空 间 是 凸 集 ， 空 集 是 凸 集 ， 单 点 集 x 为 凸 集 nR 例 :证 明 集 合 是 凸 集 。 其 中 ， A为 m n矩 阵 ， b为 m维 向 量 。证 明 ： 任 取 ， 那 么所 以 ， 1 2,X X S 1 2,AX b AX b 1 2 1 2 (1 ) (1 ) (1 )A X X AX AX b b ba a a a a a | S X AX b 1 2(1 )X X Sa a 例：给定线性规划 ，其中 ，假设令 ，那么 是凸集。min . 0TC Xst AX bX ,

13、 , ,n m m n nC R b R A R X R * | , 0R X AX b X *R 凸 集 的 性 质有 限 个 凸 集 的 交 集 仍 然 是 凸 集 。 设 是 凸 集 ， 则 是 凸 集 。1 2, , , kD D D 1 2 kD D D 设 是 凸 集 ， 则 是 凸 集 。D | , D y y x x D 凸 集 的 和 集 仍 然 是 凸 集 。 设 是 凸 集 ， 则 是 凸 集 。1 2,D D1 2 1 2 | , , D D y y x z x D z D 推 论 ： 设 是 凸 集 ， ， 则 也 是 凸 集 ， 其 中 。iD 1k i ii Di

14、 R 1,2, ,i k 定 义 3 极 点 顶 点 ： 设 D是 凸 集 , 假 设 D中 的 点 x 不 能 成 为 D中 任 何 线 段 上 的 内 点 ， 那 么 称 x为 凸 集 D的 极 点 。设 D为 凸 集 ， X D,假 设 X不 能 用 X(1) D,X(2) D两 点 的 一 个 凸 组 合 表 示 为 X= X(1)+ (1- )X(2),其 中 0 1 ， 那 么 称 X为 D的 一 个 极 点 。 k ii=1 =1定 义 2.凸 组 合 ： 设 X(1)， X(2)， ， X(k)是 n维 欧 式 空 间 中 的 k个点 ， 若 存 在 1, 2, k满 足 0

15、i 1,( i=1,2,k), 使 X= 1X(1)+ 2 X(2)+ k X(k)， 则 称 X为 X(1)， X(2)， ， X(k)的 凸 组 合 。 定 义 4 设 D为 R 中 非 空 凸 集 ， 若 对 ， D ， (0,1)恒 有 n )1(x )2(xaf +(1- ) + (1- )f (*)1(xa )2(xa )( )1(xfa a )( )2(x则 称 为 D上 的 凸 函 数 ； 进 一 步 ， 若 时 ， (*)式仅 成 立 。)(xf xf(x) ( ) ( ) ( ) ( )Tf y f x f x y x 证 明 ： 必 要 性( (1 ) ) ( ) (1

16、) ( )f x y f x f ya a a a 即 ( ( ) ( ) ( ( ) ( )f x y x f x f y f xa a 由 Taylor公 式( ( ) ( ) ( ) ( ) (| ( )|)Tf x y x f x f x y x o y xa a a (| ( )|)( ) ( ) ( ) ( )T o y xf y f x f x y x a a 令 得0a ( ) ( ) ( ) ( )Tf y f x f x y x ( (1 ) ) ( ) (1 ) ( )f x y f x f ya a a a 设 那 么 ( ) ( ) ( ) ( )Tf y f x f

17、 x y x 充 分 性 , , 0,1x y D a 令 (1 )x y za a 即所 以 ( (1 ) ) ( ) (1 ) ( )f x y f x f ya a a a (1 )x y Da a ( ) ( ) ( ) ( )Tf x f z f z x z ( ) ( ) ( ) ( )Tf x f z f z x z 同 理 ( ) ( ) ( ) ( )Tf y f z f z y z ( ) (1 ) ( ) ( ) (z) ( ( ) (1 )( )Tf x f y f z f x z y za a a a ( ) (1 ) ( ) ( ) 0f x f y f za a

18、( (1 ) ) ( ) (1 ) ( )f x y f x f ya a a a 定 理 3 二 阶 条 件 ： 设 D是 R 中 非 空 开 凸 集 , 是 定 义 在 D上 的 二 次 可微 函 数 ,那 么 是 凸 函 数 的 充 要 条 件 为 对 x D, 0,即 Hesse矩 阵 半 正 定 。n )(xf)(xf )(2 xf)(2 xf若 x D , 0， 即 Hesse矩 阵 正 定 ， 则 为 严 格凸 函 数 。 )(2 xf )(xf 证 明 ： 必 要 性, , 0,nx D p R p D 所 以 0, ( , ), x p D a a 由 Taylor公 式 2

19、 21( ) ( ) ( ) ( ) ( )2T Tf x p f x f x p p G x p oa a a a 令 得0a 因 为 为 开 集 。由 一 阶 条 件( ) ( ) ( )Tf x p f x f x pa a 所 以 2 21 ( ) ( ) 02 Tp G x p oa a 221 ( )( ) 02 T op G x p aa ( ) 0 Tp G x p 由 p的 任 意 性 ， 半 正 定 。( )G x 充 分 性,x y D 其 中 ( ), 0,1x y x a a 因 为 半 正 定故 为 凸 函 数 。( )G 所 以 ( ) ( ) ( ) ( )Tf

20、 y f x f x y x ( )f x 1( ) ( ) ( ) ( ) ( ) ( )( )2T Tf y f x f x y x y x G y x 严 格 凸 函 数 ？ 充 分 性,x y D 其 中 ( ), 0,1x y x a a 因 为 正 定 ，故 为 严 格 凸 函 数 。( )G 所 以 ( ) ( ) ( ) ( )Tf y f x f x y x ( )f x 1( ) ( ) ( ) ( ) ( ) ( )( )2T Tf y f x f x y x y x G y x x y 例：判断以下函数的凹凸性。12解： 2 21 1 2 2( ) 3 2 2 10f

21、x x x x x 2 21 2( )f x x x 1 21 2( ) ( )1 6 2, 4 1,f x f xx xx x （ ）2 2 2 2 2 21 2 1 2 2 1( ) ( ) ( ) ( )6, 4, 0,f x f x f x f xx x x x x x 2 6 0( ) 0 4f x 是 正 定 的 ， ( )f x故 是 凸 的 。2 21 22 ( )f x x x （ ） 因 ， 2 2 0( ) 0 2f x 故 ，( )f x所 以 是 凹 的 。 若 规 划 ljh migts fji ,2,1,0)( ,2,1,0)(. )(min xxx 中 , 和

22、- 为 凸 函 数 , 是 线 性 函 数 ,则 上 述 问 题 为凸 规 划 。)(xf )(xig )(xih定 义 6:凸 规 划 设 D 为 凸 集 , 是 定 义 在 D上 的 凸 函数 ， 那 么 称 规 划 问 题 为 凸 规 划 。min ( )x D f x ( )f xnR 例：线性规划 是凸规划。min . 0TC Xst AX bX 例：数学规划 易知， 与 都是凸函数，所以该规划是凸规划。2 21 2 1 21 21 2min 2 2. 1 0, 0 x x x xst x xx x 2 21 2 1 2( ) 2 2f X x x x x 1 2( ) 1g X x

23、 x 对于一般的规划P，其局部最优解不一定是全局最优解，其可行集也未必是凸集。但假设P是凸规划，那么有下面的结论。 定理4：设规划P是凸规划，那么 1 P的可行集R为凸集； 2 P的最优解集合R*是凸集； 3 P的任何局部最优解都是全局最优解。定 理 5： 1)凸 规 划 的 任 意 局 部 极 小 点 就 是 整 体 极 小 点 ，且 极 小 点 集 合 是 凸 集 。 (2)如 果 凸 规 划 的 目 标 函 数 是 严 格 凸 函 数 ， 又 存 在极 小 点 ， 那 么 它 的 极 小 点 还 是 唯 一 的 。 练习：1、求 的梯度和Hesse矩阵。2、判断函数 的凹凸性。3、判断下述非线性规划是否为凸规划？2 2 21 2 3 1 3( ) 3 2 3 4f x x x x xx 2 21 1 2 2( ) 2 3f x x xx x 2 2 21 2 32 21 21 31 2 3min ( ) 2. 4 5 10 , , 0f x x x xst x xx xx x x