非线性规划问题的求解方法

一 、 非 线 性 规 划 问 题 的 几 种 求 解 方 法1. 罚 函 数 法 （ 外 点 法 ） 基 本 思 想 ： 利 用 目 标 函 数 和 约 束 函 数 构 造 辅 助 函 数 ： ),2,1(0)( ),2,1(0)(. )(min ljxh mixgts xf ji )()(),( xPxfxF 要 求 构 造 的 函 数 具 有 这 样 的 性 质 ： 当点 x位 于 可 行 域 以 外 时 ， 取 值 很 大 ， 而离 可 行 域 越 远 则 越 大 ； 当 点 在 可 行 域 内 时 ，函 数 因 此 可 以 将 前 面 的 有 约 束 规 划 问 题 转 换 为 下列 无 约 束 规 划 模 型 ： 其 中 称 为 罚 项 ， 称 为 罚 因 子 ， 称 为 罚 函 数 。 ),( xF ),( xF)(),( xfxF )()(),(min xPxfxF )(xP ),( xF 的 定 义 一 般 如 下 ：)(xP lj jmi i xhxgxP 11 )()()( 函 数 一 般 定 义 如 下 ：)(),( yy ai xg )(,0max ， bj xh |)(| ， 1,1 ba ， a,b 为 常 数 ， 通 常 取 a=b=2。 算 法 步 骤 （ 1） 给 定 初 始 点 x(0)， 初 始 罚 因 子 )1( ， 放 大 系 数 c1； 允 许 误 差 e0,设 置 k=1； （ 2） 以 x(k-1)作 为 搜 索 初 始 点 ， 求 解 无 约 束 规 划 问 题 )()(min xPxf ， 令 x(k)为 所 求 极 小 点 。 （ 3） 当 exP k )( )( ， 则 停 止 计 算 ， 得 到 点 x(k)； 否 则 ， 令 )()1( kk c ， 返 回 （ 2） 执 行 。 如 何 将 此 算 法 模 块 化 : 求 解 非 线 性 规 划 模 型 例 子罚 项 函 数 ：无 约 束 规 划 目 标 函 数 ： 0)1(. )min( 2231 2221 xxts xx )()( xPxf )( )(kxP global lamada%主 程 序main2.m,罚 函 数 方 法x0=1 1; lamada=2;c=10; e=1e-5;k=1;while lamada*fun2p(x0)=ex0=fminsearch(fun2min,x0); lamada=c*lamada; k=k+1;end disp(最 优 解 ),disp(x0) disp(k=),disp(k) 程 序 1： 主 程 序 main2.m 程 序 2： 计 算 的 函 数 fun2p.mfunction r=fun2p(x)%罚 项 函 数r=(x(1)-1)3-x(2)*x(2)2; )( )(kxP 程 序 3： 辅 助 函 数 程 序fun2min.mfunction r=fun2min(x)%辅 助 函 数global lamadar=x(1)2+x(2)2+lamada*fun2p(x); 运 行 输 出 ：最 优 解 1.00012815099165 -0.00000145071779 k=33 练 习 题 ： 1、 用 外 点 法 求 解 下 列 模 型 2、 将 例 子 程 序 改 写 为 一 个 较 为 通 用 的 罚 函 数法 程 序 。 （ 考 虑 要 提 供 哪 些 参 数 ） 1. )2min( 21 2221 xxts xx 2. 内 点 法 （ 障 碍 函 数 法 ）仅 适 合 于 不 等 式 约 束 的 最 优 化 问 题其 中都 是 连 续 函 数 ， 将 模 型 的 定 义 域 记 为 mixgts xfi ,2,1,0)(. )(min ),2,1)(),( mixgxf i ,2,1,0)(| mixgxS i 构 造 辅 助 函 数为 了 保 持 迭 代 点 含 于 可 行 域 内 部 ， 我 们 定 义障 碍 函 数 )()(),( xBxfxF 其 中 )(xB 是 连 续 函 数 ， 当 点 x趋 于 可 行 域 边 界 时 ， )(xB ， B(x)可 以 取 如 下 形 式 ： mi i xgxB 1 )(1)( 或 )(log)( 1 xgxB i mi 在 这 里 是 个 很 小 的 正 数 ， 那 么 当 x趋 于 边 界 时 ， ),( xF 。 3. 问 题 转 化 为 一 个 无 约 束 规 划由 于 很 小 ， 则 函 数 取 值 接 近 于f(x)， 所 以 原 问 题 可 以 归 结 为 如 下 规 划 问 题 的近 似 解 ： ),( xFSxts xF. ),(min 算 法 ： （ 1） 给 定 初 始 内 点 Sx )0( ， 允 许 误 差 e0， 障 碍 参 数 )1( ， 缩 小 系 数 )1,0(b ， 置 k=1； （ 2） 以 )1( kx 为 初 始 点 ， 求 解 下 列 规 划 问 题 ： Sxts xBxf k . )()(min )( ， 令 )(kx 为 所 求 极 小 点 （ 3） 如 果 exB kk )( )()( ， 则 停 止 计 算 ， 得 到 结 果 )(kx ， （ 4） 否 则 令 )()1( kk b ， 置 k=k+1， 返 回 （ 2） 。 练 习 题 ：请 用 内 点 法 算 法 求 解 下 列 问 题 ： 10. 45)(min 2 1 221 x xts xxxf 小 结q讲 解 了 两 个 求 解 有 约 束 非 线 性 最 小 化 规 划特 点 ：q易 于 实 现 ， 方 法 简 单 ；q没 有 用 到 目 标 函 数 的 导 数q问 题 的 转 化 技 巧 （ 近 似 为 一 个 无 约 束 规 划 ） 4、 其 它 求 解 算 法（ 1） 间 接 法（ 2） 直 接 法 q直 接 搜 索 法q以 梯 度 法 为 基 础 的 间 接 法q无 约 束 规 划 的 Matlab求 解 函 数q数 学 建 模 案 例 分 析 （ 截 断 切 割 ， 飞 机 排 队 ） （ 1） 间 接 法在 非 线 性 最 优 化 问 题 当 中 ， 如 果 目 标 函数 能 以 解 析 函 数 表 示 ， 可 行 域 由 不 等 式 约 束确 定 ， 则 可 以 利 用 目 标 函 数 和 可 行 域 的 已 知性 质 ， 在 理 论 上 推 导 出 目 标 函 数 为 最 优 值 的必 要 条 件 ， 这 种 方 法 就 称 为 间 接 法 （ 也 称 为解 析 法 ） 。一 般 要 用 到 目 标 函 数 的 导 数 。 （ 2） 直 接 法直 接 法 是 一 种 数 值 方 法这 种 方 法 的 基 本 思 想 是 迭 代 ， 通 过 迭 代 产 生一 个 点 序 列 X(k) ， 使 之 逐 步 接 近 最 优 点 。 只 用 到 目 标 函 数 。如 黄 金 分 割 法 、 Fibonacci、 随 机 搜 索 法 。 （ 3） 迭 代 法 一 般 步 骤注 意 ： 数 值 求 解 最 优 化 问 题 的 计 算 效 率 取 决于 确 定 搜 索 方 向 P (k)和 步 长 的 效 率 。 （ 1） 选 定 初 始 点 X (0)， k=0 （ 2） 寻 找 一 个 合 适 的 方 向 P (k)， k=0， 1， 2， P (k)为 第 k+1 步 的 搜 索 方 向 。 （ 3） 求 出 沿 P (k)方 向 前 进 的 步 长 )(k （ 4） 得 到 新 的 点 X (k+1)， )()()()1( kkkk PXX 检 验 X (k+1)是 否 最 优 ， 如 果 是 最 优 ， 则 迭 代 结 束 ， 否 则 1 kk ， 转 到 （ 2） 执 行 。 )(k 最 速 下 降 法 （ steepest descent method）由 法 国 数 学 家 Cauchy于 1847年 首 先 提 出 。 在每 次 迭 代 中 ， 沿 最 速 下 降 方 向 （ 负 梯 度 方 向 ）进 行 搜 索 ， 每 步 沿 负 梯 度 方 向 取 最 优 步 长 ，因 此 这 种 方 法 称 为 最 优 梯 度 法 。 特 点 ：方 法 简 单 ， 只 以 一 阶 梯 度 的 信 息 确 定 下 一 步 的 搜 索方 向 ， 收 敛 速 度 慢 ；越 是 接 近 极 值 点 ， 收 敛 越 慢 ；它 是 其 它 许 多 无 约 束 、 有 约 束 最 优 化 方 法 的 基 础 。该 法 一 般 用 于 最 优 化 开 始 的 几 步 搜 索 。 以 梯 度 法 为 基 础 的 最 优 化 方 法求 f(x)在 En中 的 极 小 点 nExxf ),(min思 想 ：q方 向 导 数 是 反 映 函 数 值 沿 某 一 方 向 的 变 化 率 问 题 q方 向 导 数 沿 梯 度 方 向 取 得 最 大 值基 础 ： 方 向 导 数 、 梯 度 q通 过 一 系 列 一 维 搜 索 来 实 现 。q本 方 法 的 核 心 问 题 是 选 择 搜 索 方 向 。q搜 索 方 向 的 不 同 则 形 成 不 同 的 最 优 化 方 法 。 最 速 下 降 法 算 法 ： 1. 给 定 初 始 点 Ex n)1( ， 给 定 误 差 0 ， 令 k=1； 2. 计 算 搜 索 方 向 xd kk f )()( ； 3. 如 果 d k)( ， 则 迭 代 终 止 ， 否 则 通 过 下 列 一 维 搜 索 求 )(k ： dx kkf )()(0min 4. 令 dxx kkkk )()()()1( ， 置 k=k+1， 转 （ 2） 步 执 行 。 算 法 说 明 可 通 过 一 维 无 约 束 搜 索 方 法 求 解dxx kkkk )()()()1( )( )()( xd kk f )(k ： 为 dx kkf )()(0min 的 解 )(k 例 子 ： 用 最 速 下 降 法 解 下 列 问 题分 析 ：1、 编 写 一 个 梯 度 函 数 程 序fun1gra.m2、 求 (可 以 调 用 函 数fminsearch )函数fungetlamada.m3、 最 速 下 降 法 主 程 序 main1.m 22212)(min xxxf 0001.0,1,1)1( Tx初 始 条 件 )(k 第 一 步 ： 计 算 梯 度 程 序 fun1gra.mfunction r=fun1gra(x)%最 速 下 降 法 求 解 示 例%函 数f(x)=2*x12+x22的 梯 度 的 计 算%r(1)=4*x(1);r(2)=2*x(2); 第 二 步 ： 求 最 优 的 目 标 函 数function r=fungetlamada(lamada)%关 于lamada的 一 元 函 数 ， 求 最 优 步 长global x0d=fun1gra(x0);r=2*(x0(1)-lamada*d(1)2+(x0(2)-lamada*d(2)2; %注 意 负 号 表 示 是 负 梯 度 )(k 第 三 步 ： 主 程 序 main1.m%最 速 下 降 方 法 实 现 一 个 非 线 性 最 优 化 问 题% min f(x)=2*x12+x22global x0 x0= 1 1 ;yefi=0.0001;k=1;d=-fun1gra(x0);lamada=1; 主 程 序 main1.m（ 续 ）while sqrt(sum(d.2)=yefilamada=fminsearch(fungetlamada,lamada);%求 最 优 步 长lamada x0=x0-lamada*fun1gra(x0);%计 算x0 d=fun1gra(x0);%计 算 梯 度 k=k+1;%迭 代 次 数enddisp(x=),disp(x0),disp(k=),disp(k),disp(funobj=),disp(2*x0(1)2+x0(2)2) 三 、 Matlab求 解 有 约 束 非 线 性 规 划 1. 用 fmincon函 数 求 解 形 如 下 面 的 有 约 束非 线 性 规 划 模 型一 般 形 式 ： 0)( 0)(. )(min Xc Xc uXl bXA bAXts Xf eq eqeq 用 Matlab求 解 有 约 束 非 线 性 最 小 化 问 题求 解 非 线 性 规 划 问 题 的 Matlab函 数 为 ： fmincon1.约 束 中 可 以 有 等 式 约 束2.可 以 含 线 性 、 非 线 性 约 束 均 可 输 入 参 数 语 法 ：x = fmincon(fun,x0,A,b)x = fmincon(fun,x0,A,b,Aeq,beq)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options,P1,P2, .) 输 入 参 数 的 几 点 说 明q模 型 中 如 果 没 有 A,b,Aeq,beq,lb,ub的 限 制 ， 则 以 空 矩 阵 作 为q参 数 传 入 ；qnonlcon： 如 果 包 含 非 线 性 等 式 或 不 等 式 约 束 ， 则 将 这 些 函 数 编 写 为 一 个 Matlab函 数 ，nonlcon就 是 定 义 这 些 函 数 的 程 序 文 件 名 ；不 等 式 约 束 c(x) 2% nonlcon 如 果 四 个 输 出 参 数 GC = .% 不 等 式 约 束 的 梯 度 GCeq = .% 等 式 约 束 的 梯 度end 输 出 参 数 语 法 ：x,fval = fmincon(.)x,fval,exitflag = fmincon(.)x,fval,exitflag,output = fmincon(.)x,fval,exitflag,output,lambda = fmincon(.)x,fval,exitflag,output,lambda,grad = fmincon(.)x,fval,exitflag,output,lambda,grad,hessian = fmincon(.) 运 用 步 骤 ：将 自 己 的 模 型 转 化 为 上 面 的 形 式写 出 对 应 的 参 数调 用 函 数 fmincon应 用 求 解 示 例 ：请 问 ：1、 结 合 fmincon函 数 ， 需 要 提 供 哪 些 参 数72220. )(min 321 321 xxxts xxxxf 第 一 步 ： 编 写 一 个 M文 件 返 回 目 标 函 数 f在 点x处 的 值 函 数 程 序 function f = myfun(x)f = -x(1) * x(2) * x(3); 函 数 myfun.m 第 二 步 ： 为 了 调 用 MATLAB函 数 ， 必 须 将 模型 中 的 约 束 转 化 为 如 下 形 式 (=)。 这 里 ：A=-1 -2 -2; 1 2 2 ;b=0 72; 7222 022 321 321 xxx xxx bAx 这 是 2个 线 性 约 束 ， 形 如 第 三 步 ： 提 供 一 个 搜 索 起 点 ， 然 后 调 用 相应 函 数 ， 程 序 如 下 ：% 给 一 个 初 始 搜 索 点x0 = 10; 10; 10; x,fval = fmincon(myfun,x0,A,b) 主 程 序 （ 整 体 ） ：A=-1 -2 -2; 1 2 2 ;b=0 72;% 给 一 个 初 始 搜 索 点x0 = 10; 10; 10; x,fval = fmincon(myfun,x0,A,b) 最 后 得 到 如 下 结 果 ： x = 24.0000 12.0000 12.0000 fval = -3.4560e+03 2.非 负 条 件 下 线 性 最 小 二 乘 lsqnonneg 适 合 如 下 模 型 ： 0. 22min Xts dCXX注 意 ： 约 束 只 有 非 负 约 束 语 法 ：x =lsqnonneg(c,d)x =lsqnonneg(c,d,x0)x =lsqnonneg(c,d,x0,options) 3.有 约 束 线 性 最 小 二 乘 lsqlin 适 合 如 下 模 型 ： uXl bA bAXts dCX eqeqX . 22min注 意 ： 约 束 有 线 性 等 式 、 不 等 式 约 束 语 法 ：x = lsqlin(C,d,A,b)x = lsqlin(C,d,A,b,Aeq,beq)x = lsqlin(C,d,A,b,Aeq,beq,lb,ub)x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0)x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options)x,resnorm = lsqlin(.)x,resnorm,residual = lsqlin(.)x,resnorm,residual,exitflag = lsqlin(.)x,resnorm,residual,exitflag,output = lsqlin(.)x,resnorm,residual,exitflag,output,lambda = lsqlin(.) 4.非 线 性 最 小 二 乘 lsqnonlin 适 合 模 型 ： uXlts XFXF i iX . )(21)( 22221min 语 法 ：x = lsqnonlin(fun,x0)x = lsqnonlin(fun,x0,lb,ub)x = lsqnonlin(fun,x0,lb,ub,options)x = lsqnonlin(fun,x0,options,P1,P2, . )x,resnorm = lsqnonlin(.)x,resnorm,residual = lsqnonlin(.)x,resnorm,residual,exitflag = lsqnonlin(.)x,resnorm,residual,exitflag,output = lsqnonlin(.)x,resnorm,residual,exitflag,output,lambda = lsqnonlin(.)x,resnorm,residual,exitflag,output,lambda,jacobian = lsqnonlin(.) 例 1： 求 解 x， 使 得 下 式 最 小 resnorm 等 于 norm(C*x-d)2residual 等 于 C*x-d 2101 )22( 21 k ee kxkxk返 回 参 数 说 明 第 一 步 ： 编 写 M文 件 myfun.m计 算 向 量 Ffunction F = myfun(x)k = 1:10;F = 2 + 2*k-exp(k*x(1)-exp(k*x(2); 第 二 步 ： 调 用 优 化 函 数 lsqnonlin% 给 定 搜 索 起 点x0 = 0.3 0.4 ;% 调 用 求 解 函 数x,resnorm = lsqnonlin(myfun,x0) x = 0.2578 0.2578resnorm %residual or sum of squaresresnorm = 124.3622 5.学 习 回 顾能 力 培 养 ：1、 建 模 分 析 能 力2、 应 用 数 学 能 力3、 算 法 设 计 与 程 序 设 计 谢 谢 ！