非线性规划53080

《非线性规划53080》由会员分享，可在线阅读，更多相关《非线性规划53080（59页珍藏版）》请在装配图网上搜索。

1、2 0 2 1 /6 /1 6 1 非 线 性 规 划Non-linear Programming 2 0 2 1 /6 /1 6 2 非 线 性 规 划v基 本 概 念v凸 函 数 和 凸 规 划v一 维 搜 索 方 法v无 约 束 最 优 化 方 法v约 束 最 优 化 方 法 2 0 2 1 /6 /1 6 3 基 本 概 念v非 线 性 规 划 问 题v非 线 性 规 划 方 法 概 述 2 0 2 1 /6 /1 6 4 非 线 性 规 划 问 题例 1 曲 线 的 最 优 拟 合 问 题 已 知 某 物 体 的 温 度 与 时 间 t之 间 有 如 下 形 式 的 经 验 函 数

2、关 系 ： tcetcc 321 (*) 其 中 1c ， 2c ， 3c 是 待 定 参 数 。 现 通 过 测 试 获 得 n 组 与 t之 间 的 实 验 数 据 ),( iit ， i=1， 2， ,n。 试 确 定 参 数 1c ， 2c ， 3c ， 使 理 论 曲 线 (*)尽 可 能 地 与 n 个 测 试 点 ),( iit 拟 合 。 t n1i 221 )( min 3 itcii etcc 2 0 2 1 /6 /1 6 5 例 2 构 件 容 积 问 题设 计 一 个 右 图 所 示 的 由 圆 锥 和 圆 柱 面 围 成 的 构 件 ， 要 求 构 件 的 表 面

3、积 为 S， 圆 锥 部 分 的 高 h 和 圆 柱 部 分 的 高 x2之 比 为 a。 确 定 构 件 尺 寸 ， 使 其 容 积 最 大 。 x 1 x2 x3 0,0 2 . )3/1( max 21 2121222211 221xx Sxxxxaxxts xxaV 2 0 2 1 /6 /1 6 6 数 学 规 划设 nTn Rxxx ),.,( 1 ， RRqjxhpixgxf nji :,.,1),(;,.,1),();( , 如 下 的 数 学 模 型 称 为 数 学 规 划 (Mathematical Programming, MP)： qjxh pixgts xfji ,.

4、,1,0)( ,.,1,0)( . )( min qjxh pixgRxX jin ,.,1,0)( ,.,1,0)( 约 束 集 或 可 行 域Xx MP的 可 行 解 或 可 行 点 2 0 2 1 /6 /1 6 7 向 量 化 表 示当 p=0,q=0时 ， 称 为 无 约 束 非 线 性 规划 或 者 无 约 束 最 优 化 问 题 。否 则 ， 称 为 约 束 非 线 性 规 划 或 者 约 束最 优 化 问 题 。 2 0 2 1 /6 /1 6 8 最 优 解 和 极 小 点定 义 4.1.1 对 于 非 线 性 规 划 (MP)， 若 Xx * ， 并 且 有 X ),()(

5、 * xxfxf 则 称 *x 是 (MP)的 整 体 最 优 解 或 整 体 极 小 点 ， 称 )( *xf 是 (MP)的 整 体 最 优 值 或 整 体 极 小 值 。 如 果 有 * ),()( xxX,xxfxf 则 称 *x 是 (MP)的 严 格 整 体 最 优 解 或 严 格 整 体 极 小 点 ， 称 )( *xf 是 (MP)的 严 格 整 体 最 优 值 或 严 格 整 体 极 小 值 。 2 0 2 1 /6 /1 6 9 非 线 性 规 划 方 法 概 述定 义 4.1.3 设 0,: pRpRxRRf nnn ， 若 存 在 0 ， 使 ),0( ),()( tx

6、ftpxf 则 称 向 量 p是 函 数 f(x)在 点 x 处 的 下 降 方 向 。 不 可 行 方 向 2 0 2 1 /6 /1 6 1 0 非 线 性 规 划 基 本 迭 代 格 式 第 1步 选 取 初 始 点 0 x ， k:=0; 第 2步 构 造 搜 索 方 向 kp ； 第 3步 根 据 kp ， 确 定 步 长 kt ； 第 4步 令 kkkk ptxx 1 ， 若 1kx 已 满 足 某 种 终 止 条 件 ， 停 止 迭 代 ， 输 出 近 似 解 1kx ； 否 则 令 k:=k+1， 转 回 第 2步 。 迭 代 法 的 基 本 格 式 2 0 2 1 /6 /1

7、 6 1 1 常 用 停 止 规 则 2 0 2 1 /6 /1 6 1 2 凸 函 数 和 凸 规 划q凸 函 数 及 其 性 质q凸 规 划 及 其 性 质 2 0 2 1 /6 /1 6 1 3 凸 函 数 及 其 性 质 定 义 4.2.1 设 nRS 是 非 空 凸 集 ， RSf : ， 如 果 对 任 意 的 )1,0( 有 )()1()()1( 2121 xfxfxxf ， Sxx 21, 则 称 f是 S上 的 凸 函 数 ， 或 f在 S上 是 凸 的 。 如 果 对 于 任 意 的 )1,0( 有 )()1()()1( 2121 xfxfxxf ， 21 xx 则 称 f

8、是 S上 的 严 格 凸 函 数 ， 或 f在 S上 是 严 格 凸 的 。 若 -f是 S上 的 （ 严 格 ） 凸 函 数 ， 则 称 f是 S上 的 （ 严 格 ） 凹 函 数 ， 或 f在 S上 是 （ 严 格 ） 凹 的 。 2 0 2 1 /6 /1 6 1 4(a) 凸 函 数 (b)凹 函 数 2 0 2 1 /6 /1 6 1 5定 理 4.2.2 设 nRS 是 非 空 凸 集 ， RRf n : 是 凸 函 数 ， Rc ， 则 集 合 cxfSxcfH S )(),( 是 凸 集 。 2 0 2 1 /6 /1 6 1 6 2 0 2 1 /6 /1 6 1 7 定 理

9、 4.2.4 设 nRS 是 非 空 开 凸 集 ， RSf : 二 阶 连 续 可 导 ， 则 f是S上 的 凸 函 数 的 充 要 条 件 是 f的 H esse矩 阵 )(2 xf 在 S上 是 半 正 定 的 。 当 )(2 xf 在 S上 是 正 定 矩 阵 时 ， f是 S上 的 严 格 凸 函 数 。（ 注 意 ： 该 逆 命 题 不 成 立 。 ） 222212 22222122 122122122 )()()( . )(.)()( )(.)()()( nnn nnx xfxx xfxx xf xx xfx xfxx xf xx xfxx xfx xfxf 2 0 2 1 /6

10、 /1 6 1 8 凸 规 划 及 其 性 质 qjxh pixgts xfji ,.10,)( (MP) ,.,1,0)( . )( min qjxh pixgRxX jin ,.,1,0)( ,.,1,0)( 约 束 集如 果 (MP)的 约 束 集 X是 凸 集 ， 目 标 函 数 f是X上 的 凸 函 数 ， 则 (MP)叫 做 非 线 性 凸 规 划 ，或 简 称 为 凸 规 划 。 2 0 2 1 /6 /1 6 1 9 定 理 4.2.5 对 于 非 线 性 规 划 (MP)， 若 pixgi ,.,1),( 皆 为 nR 上 的 凸 函 数 ， qjxhj ,.,1),( 皆

11、为 线 性 函 数 ， 并 且 f是 X上 的 凸 函 数 ， 则 (MP)是 凸 规 划 。 定 理 4.2.6 凸 规 划 的 任 一 局 部 最 优 解 都 是 它的 整 体 最 优 解 。 2 0 2 1 /6 /1 6 2 0 例 4.2.3 验 证 下 列 （ MP） 是 凸 规 划2 2 21 2 3 1 2 3 1 3 1 2 1 22 21 1 2 32 1 2 3 3 1 2 3min ( , , ) 2 2 2. ( ) 0( ) 2 16( ) 0f x x x x x x xx xx x xst g x x x xg x x x xg x x x x 2 0 2 1

12、/6 /1 6 2 1 一 维 搜 索 方 法 目 标 函 数 为 单 变 量 的 非 线 性 规 划 问 题 称 为 一 维 搜 索 问 题 (t) min )0( 0 max ttt 其 中 Rt 。 精 确 一 维 搜 索 方 法 0.618法 Newton法非 精 确 一 维 搜 索 方 法 G oldstein法 Armijo法 2 0 2 1 /6 /1 6 2 2 0.618法 （ 近 似 黄 金 分 割 法 ） 2 0 2 1 /6 /1 6 2 3 例 4.3.1 用 0.618法 求 解 的 单 谷 区 间 为 0,3，30min ( ) 2 1t t t t ( )t 0

13、.5 解 答 2 0 2 1 /6 /1 6 2 4 在 0.618法 中 每 次 迭 代 搜 索 区 间 按 常 比 例 缩小 ， 所 以 要 使 给 定 的 单 谷 区 间 减 少 到 所 要求 的 区 间 精 度 ， 需 要 的 迭 代 次 数 是 可 以 预估 的 。 另 外 若 每 次 每 次 迭 代 按 不 同 比 例 缩小 搜 索 区 间 ， 但 仍 要 求 每 次 迭 代 只 计 算 一个 函 数 值 ， 且 希 望 在 搜 索 点 个 数 相 同 的 情况 下 使 最 终 的 搜 索 区 间 的 长 度 最 小 ， 按 此要 求 设 计 的 方 法 是 Fibonacci法

14、2 0 2 1 /6 /1 6 2 5 Newton法 思 想 2 0 2 1 /6 /1 6 2 6 Newton法)( min t 其 中 )(t 是 二 次 可 微 的 ， 且 0)( t 。 2 0 2 1 /6 /1 6 2 7 从 任 意 初 始 点 开 始 的 Newton法 产 生 的 点 列 ，一 般 来 说 不 一 定 收 敛 ， 即 使 收 敛 ， 其 极 限点 也 不 一 定 是 的 极 小 点 ， 只 能 保 证 它 是 的 驻 点 。 但 当 初 始 点 充 分 接 近 时 ， 可以 证 明 Newton法 是 收 敛 的 。 ( )t( )t *t 2 0 2 1

15、 /6 /1 6 2 8a b c d )0( )(ty ty )0()0( tmy )0()0( 1 tmy )0()0( 2 G oldstein法 2 0 2 1 /6 /1 6 2 9 2 0 2 1 /6 /1 6 3 0 G oldstein法 步 骤 2 0 2 1 /6 /1 6 3 1 例 4.3.3 用 Goldstein法 求 解 取 30min ( ) 2 1t t t t 0 1 22, 0.2, 0.7, 2t m m 解 答 2 0 2 1 /6 /1 6 3 2 Armijo法)0( )(ty tmy )0()0( kt kMt取 定 Mm 10 ， 用 一 下

16、 两 个 式 子 限 定 kt 不 太 大 也 不 太 小 ： )0()0()( kk mtt )0()0()( kk mMtMt 2 0 2 1 /6 /1 6 3 3 无 约 束 最 优 化 方 法v无 约 束 问 题 的 最 优 性 条 件v最 速 下 降 法v共 轭 方 向 法 )( min xf (UMP) 其 中 nTn Rxxx ),.,( 1 ， RRf n : 2 0 2 1 /6 /1 6 3 4 无 约 束 问 题 的 最 优 化 条 件定 理 4.4.1 设 RRf n : 在 点 nRx 处 可 微 。 若 存 在 nRp ， 使 0)( pxf T 则 向 量 p是

17、 f在 点 x 处 的 下 降 方 向 。 定 理 4.4.2 设 RRf n : 在 点 nRx 处 可 微 。 若 *x 是 (UMP)的 局 部 最 优 解 ， 则 0)( * xf 定 理 4.4.3 设 RRf n : 在 点 nRx 处 的 H esse矩 阵 )( *2 xf 存在 。 若 0)( * xf ， 并 且 )( *2 xf 正 定 则 *x 是 (UMP)的 局 部 最 优 解 。 定 理 4.4.4 设 RRf n : ， nRx * ， f是 nR 上 得 可 微 凸 函 数 。 若 有 0)( * xf 则 *x 是 (UMP)的 整 体 最 优 解 。 2

18、0 2 1 /6 /1 6 3 5 最 速 下 降 法设 （ NMP） 问 题 中 的 目 标 函 数 RRf n : 一 阶 连 续 可 微 2 0 2 1 /6 /1 6 3 6 2 0 2 1 /6 /1 6 3 7 第 1步 选 取 初 始 点 0 x ， 给 定 终 止 误 差 0 ， 令 0:k ； 第 2步 计 算 )( kxf ， 若 )( kxf ， 停 止 迭 代 ， 输 出 kx 。 否 则 进 行 第 3步 ； 第 3步 取 )( kk xfp 第 4步 进 行 一 维 搜 索 ， 求 kt ， 使 得 )(min)( 0 kktkkk tpxfptxf 令 kkkk

19、ptxx 1 ， 1: kk ， 转 第 2步 。 2 0 2 1 /6 /1 6 3 8解 答 2 0 2 1 /6 /1 6 3 9 随 着 迭 代 次 数 的 增 加 ， 收 敛 速 度 越 来 越 慢 最 速 下 降 法 的 相 邻 两 个 搜 索 方 向 是 彼 此 正交 的 具 有 全 局 收 敛 性 2 0 2 1 /6 /1 6 4 0解 答 2 0 2 1 /6 /1 6 4 1 随 着 迭 代 次 数 的 增 加 ， 收 敛 速 度 越 来 越 慢 最 速 下 降 法 的 相 邻 两 个 搜 索 方 向 是 彼 此 正交 的 具 有 全 局 收 敛 性 2 0 2 1 /6

20、 /1 6 4 2 共 轭 方 向 法 2 0 2 1 /6 /1 6 4 3 2 0 2 1 /6 /1 6 4 4 F-R法 步 骤 2 0 2 1 /6 /1 6 4 5解 答 2 0 2 1 /6 /1 6 4 6 F-R法 具 有 二 次 终 止 性 。 对 一 般 可 微 函 数 的无 约 束 优 化 问 题 ， 当 函 数 满 足 一 定 的 条 件时 ， 可 以 证 明 F-R方 法 具 有 全 局 收 敛 性 其 收敛 速 度 比 最 速 下 降 法 快 F-R法 强 烈 依 赖 于 一 位 搜 索 的 精 确 性 2 0 2 1 /6 /1 6 4 7 约 束 最 优 化

21、方 法v约 束 最 优 化 问 题 的 最 优 化 条 件v简 约 梯 度 法v惩 罚 函 数 法 qjRRh piRRg RRfRx nj ni nn ,.,1 : ,.,1 ,: : , 其 中 ,.,1 0)( 1 0)( . )( min qjxh ,.,pixgts xf ji (MP) 2 0 2 1 /6 /1 6 4 8 约 束 最 优 化 问 题 的 最 优 化 条 件 qjxh pixgRxX jin ,.,1,0)( ,.,1,0)( ,0)( |)( * IixgixI i Xx * JjxhqJ j ,0)(,.,2,1 *， 即令 定 理 4.5.1 设 RRf n

22、 : 和 )(,: *xIiRRg ni 在 点 *x 处 可 微 ， )(, *xIIigi 在 点 *x 处 连 续 ， JjRRh nj ,: 在 点 *x 处 连 续 可 微 ， 并 且 各 JjxhxIixg ji ),( ),( ),( * 线 性 无 关 。 若 *x 是 (MP)的 局 部 最 优 解 ， 则 存 在 两 组 实 数 )(, * xIii 和 Jjj ,* ， 使 得 )( ,0 0)()()( * *)( * * xIi xhxgxfi Jj jjxIi ii K -T条 件 2 0 2 1 /6 /1 6 4 9 定 理 4.5.2 对 于 (MP)问 题

23、， 若 JjhIigf ji , , , 在 点 *x 处 连 续 可 微 ， 可 行 点 *x 满 足 (MP)的 K -T条 件 ， 且 )(, , *xIigf i 是 凸 函 数 ， Jjhj , 是 线 性 函 数 ， 则 *x 是 (MP)的 整 体 最 优 解 。 2 0 2 1 /6 /1 6 5 0 简 约 梯 度 法 0 . )( min x bAxts xf 其 中 ， RRfRx nn : , ， mAr nm )( ， mRb (4.5.12) 定 理 4.5.3 对 于 非 线 性 规 划 问 题 (4.5.12)， 设 f是 可 微 函 数 ， lk Xx ， 并

24、 且 有 分 解 kNkBk xxx ， 0kBx 。 若 kNkBk ppp 由 下 式 确 定 ， kNkkkB kBkikiki kikikikN pNBp Iirrx rrpp 1 0 0 ,: (*) 则 （ 1） 当 0kp 时 ， kp 是 f在 点 kx 处 关 于 lX 的 可 行 下 降 方 向 ； （ 2） 0kp 的 充 要 条 件 是 kx 是 问 题 (4.5.12)的 K -T点 。 0 , | xbAxRxX nl 2 0 2 1 /6 /1 6 5 1 Wolfe法 步 骤 2 0 2 1 /6 /1 6 5 2 惩 罚 函 数 法思 想 ： 利 用 问 题

25、中 的 约 束 函 数 做 出 适 当 的 带 有 参 数 的 惩罚 函 数 ， 然 后 在 原 来 的 目 标 函 数 上 加 上 惩 罚 函 数 构 造 出带 参 数 的 增 广 目 标 函 数 ， 把 (MP)问 题 的 求 解 转 换 为 求 解一 系 列 无 约 束 非 线 性 规 划 问 题 。罚 函 数 法障 碍 函 数 法 2 0 2 1 /6 /1 6 5 3 罚 函 数 法 qjxh pixgts xfji ,.,1,0)( ,.,1,0)( . )( min qjxh pixgRxX jin ,.,1,0)( ,.,1,0)(设 法 适 当 地 加 大 不 可 行 点 处

26、 对 应 的 目 标 函 数 值 ， 使不 可 行 点 不 能 成 为 相 应 无 约 束 极 小 化 问 题 的 最 优 解 。 qj jpi ic xhcxgcxp 1 21 2 )(2)0),(max()(罚 函 数 )( min xFc )()()( xpxfxF cc 2 0 2 1 /6 /1 6 5 4 实 际 应 用 中 ， 选 取 一 个递 增 且 趋 于 无 穷 的 正 罚函 数 参 数 列 qj jkpi ikc xhcxgcxp k 1 21 2 )(2)0),(max()(其 中 *)()()( min xpxfxF kk cc * 2 0 2 1 /6 /1 6 5

27、 5 罚 函 数 法 计 算 步 骤 第 1步 选 取 初 始 点 0 x ， 罚 参 数 列 ,.)2,1( kck ， 给 出 检 验 终 止 条 件 的 误 差 0 ， 令 k:=1； 第 2步 按 (*)构 造 函 数 )(xp kc ， 再 按 (*)构 造 (MP) 的 增 广 目 标 函 数 ， 即 )()()( xpxfxF kk cc 第 3步 选 用 某 种 无 约 束 最 优 化 方 法 ， 以 1kx 为 初 始 点 ， 求 解 )( min xF kc ， 设 得 到 最 优 解 kx 。 若 kx 已 满 足 某 种 终 止 条 件 ， 停 止 迭 代 ， 输 出

28、kx 。 否 则 令 k:=k+1， 转 第 2步 ； 2 0 2 1 /6 /1 6 5 6 障 碍 函 数 法 pixgts xfi ,.,1,0)( . )( min Tp xgxgxg )(),.,()( 1令 可 行 域 X的 内 部 记 为 0)( | xgRxX no 在 可 行 区 域 的 边 界 上 筑 起 一 道 “ 墙 ” ， 当 迭 代 点 靠 近边 界 时 ， 所 构 造 的 增 广 目 标 函 数 值 陡 然 增 大 ， 于 是 最优 点 就 被 “ 挡 ” 在 可 行 区 域 内 部 了 。 2 0 2 1 /6 /1 6 5 7 构 造 障 碍 函 数当 oXx

29、 时 ， pi ikd xgdxB k 1 )(1)( 或 pi ikd xgdxB k 1 )(ln)( 其 中 ， kd 为 罚 参 数 或 罚 因 子 )()()( xBxfxF kk dd ,.2,1 ),( min kxF kd 2 0 2 1 /6 /1 6 5 8 障 碍 函 数 法 步 骤 第 1步 选 取 初 始 点 oXx 0 ， 罚 参 数 列 ,.)2,1( kdk ， 给 出 检 验 终 止 条 件 0 ， 令 k:=1； 第 2步 做 障 碍 函 数 )(xB kd ， 构 造 增 广 目 标 函 数 )()()( xBxfxF kk dd 第 3步 选 用 某 种 无 约 束 最 优 化 方 法 ， 以 1kx 为 初 始 点 求 解 od XxxF k ),( min 得 到 最 优 解 kx 。 若 kx 已 满 足 某 种 终 止 条 件 ， 停 止 迭 代 ， 输 出 kx 。 否 则 ， 令 k:=k+1， 转 第 2步 。 若 有 不 当 之 处 ， 请 指 正 ， 谢 谢 ！