第六讲 非线性规划问题的求解方法.

Presentation on theme: "第六讲 非线性规划问题的求解方法."— Presentation transcript:

1 第六讲 非线性规划问题的求解方法

2 一、非线性规划问题的几种求解方法 1. 罚函数法（外点法）
一、非线性规划问题的几种求解方法 1. 罚函数法（外点法） 基本思想： 利用目标函数和约束函数构造辅助函数：

3 要求构造的函数 具有这样的性质：当点x位于可行域以外时， 取值很大，而离可行域越远则越大；当点在可行域内时，函数
因此可以将前面的有约束规划问题转换为下列无约束规划模型： 其中称为 罚项， 称为罚因子， 称为罚函数。

4 的定义一般如下： 函数 一般定义如下：

5 算法步骤 如何将此算法模块化:

6 罚项函数： 无约束规划目标函数： 求解非线性规划模型例子

7 程序1：主程序main2.m global lamada%主程序main2.m,罚函数方法 x0=[1 1]; lamada=2;
c=10; e=1e-5; k=1; while lamada*fun2p(x0)>=e x0=fminsearch('fun2min',x0); lamada=c*lamada; k=k+1; end disp(‘最优解’),disp(x0) disp('k='),disp(k)

8 function r=fun2p(x) %罚项函数 r=((x(1)-1)^3-x(2)*x(2))^2;
程序2：计算 的函数fun2p.m function r=fun2p(x) %罚项函数 r=((x(1)-1)^3-x(2)*x(2))^2;

9 程序3：辅助函数程序fun2min.m function r=fun2min(x) %辅助函数 global lamada
r=x(1)^2+x(2)^2+lamada*fun2p(x);

10 运行输出： 最优解 k= 33

11 1、用外点法求解下列模型 2、将例子程序改写为一个较为通用的罚函数法程序。（考虑要提供哪些参数）
练习题： 1、用外点法求解下列模型 2、将例子程序改写为一个较为通用的罚函数法程序。（考虑要提供哪些参数）

12 仅适合于不等式约束的最优化问题 其中 都是连续函数，将模型的定义域记为
2. 内点法（障碍函数法） 仅适合于不等式约束的最优化问题 其中 都是连续函数，将模型的定义域记为

13 为了保持迭代点含于可行域内部，我们定义障碍函数
构造辅助函数 为了保持迭代点含于可行域内部，我们定义障碍函数

14 由于 很小，则函数 取值接近于f(x)，所以原问题可以归结为如下规划问题的近似解：
3. 问题转化为一个无约束规划 由于 很小，则函数 取值接近于f(x)，所以原问题可以归结为如下规划问题的近似解：

15

16 练习题： 请用内点法算法求解下列问题：

17 讲解了两个求解有约束非线性最小化规划 特点： 易于实现，方法简单； 没有用到目标函数的导数 问题的转化技巧（近似为一个无约束规划）
小结 讲解了两个求解有约束非线性最小化规划 特点： 易于实现，方法简单； 没有用到目标函数的导数 问题的转化技巧（近似为一个无约束规划）

18 直接搜索法 以梯度法为基础的间接法 无约束规划的Matlab求解函数 数学建模案例分析（截断切割，飞机排队）
4、其它求解算法 （1）间接法 （2）直接法 直接搜索法 以梯度法为基础的间接法 无约束规划的Matlab求解函数 数学建模案例分析（截断切割，飞机排队）

19 （1）间接法 在非线性最优化问题当中，如果目标函数能以解析函数表示，可行域由不等式约束确定，则可以利用目标函数和可行域的已知性质，在理论上推导出目标函数为最优值的必要条件，这种方法就称为间接法（也称为解析法） 。 一般要用到目标函数的导数。

20 （2）直接法 直接法是一种数值方法 这种方法的基本思想是迭代，通过迭代产生一个点序列{ X(k) }，使之逐步接近最优点。 只用到目标函数。
如黄金分割法、Fibonacci、随机搜索法。

21 注意：数值求解最优化问题的计算效率取决于确定搜索方向P (k)和步长 的效率。
（3）迭代法一般步骤 注意：数值求解最优化问题的计算效率取决于确定搜索方向P (k)和步长 的效率。

22 最速下降法（steepest descent method）
由法国数学家Cauchy于1847年首先提出。在每次迭代中，沿最速下降方向（负梯度方向）进行搜索，每步沿负梯度方向取最优步长，因此这种方法称为最优梯度法。 特点： 方法简单，只以一阶梯度的信息确定下一步的搜索方向，收敛速度慢； 越是接近极值点，收敛越慢； 它是其它许多无约束、有约束最优化方法的基础。 该法一般用于最优化开始的几步搜索。

23 以梯度法为基础的最优化方法 求f(x)在En中的极小点 思想： 基础：方向导数、梯度 方向导数是反映函数值沿某一方向的变化率问题
方向导数沿梯度方向取得最大值

24 通过一系列一维搜索来实现。 本方法的核心问题是选择搜索方向。 搜索方向的不同则形成不同的最优化方法。

25 最速下降法算法：

26 算法说明 可通过一维无约束搜索方法求解

27 例子：用最速下降法解下列问题 初始条件 分析： 1、编写一个梯度函数程序fun1gra.m 2、求 (可以调用函数fminsearch )函数fungetlamada.m 3、最速下降法主程序main1.m

28 第一步：计算梯度程序 fun1gra.m function r=fun1gra(x) %最速下降法求解示例
%函数f(x)=2*x1^2+x2^2的梯度的计算 % r(1)=4*x(1); r(2)=2*x(2);

29 第二步：求 最优的目标函数 function r=fungetlamada(lamada) %关于lamada的一元函数，求最优步长
第二步：求 最优的目标函数 function r=fungetlamada(lamada) %关于lamada的一元函数，求最优步长 global x0 d=fun1gra(x0); r=2*(x0(1)-lamada*d(1))^2+(x0(2)-lamada*d(2))^2; %注意负号表示是负梯度

30 第三步：主程序main1.m %最速下降方法实现一个非线性最优化问题 % min f(x)=2*x1^2+x2^2 global x0
yefi=0.0001; k=1; d=-fun1gra(x0); lamada=1;

31 主程序main1.m（续） while sqrt(sum(d.^2))>=yefi
lamada=fminsearch(‘fungetlamada’,lamada);%求最优步长lamada x0=x0-lamada*fun1gra(x0);%计算x0 d=fun1gra(x0);%计算梯度 k=k+1;%迭代次数 end disp('x='),disp(x0),disp('k='),disp(k),disp('funobj='),disp(2*x0(1)^2+x0(2)^2)

32 三、Matlab求解有约束非线性规划

33 1. 用fmincon函数求解形如下面的有约束非线性规划模型
一般形式：

34 用Matlab求解有约束非线性最小化问题
求解非线性规划问题的Matlab函数为： fmincon 1.约束中可以有等式约束 2.可以含线性、非线性约束均可

35 输入参数语法： 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, ...)

36 输入参数的几点说明 模型中如果没有A,b,Aeq,beq,lb,ub的限制，则以空矩阵[ ]作为 参数传入；
nonlcon：如果包含非线性等式或不等式约束，则将这些函数 编写为一个Matlab函数， nonlcon就是定义这些函数的程序文件名； 不等式约束 c(x)<=0 等式约束 ceq(x)=0. 如果nonlcon=‘mycon’ ; 则myfun.m定义如下 function [c,ceq] = mycon(x) c = ...     % 计算非线性不等式约束在点x处的函数值 ceq = ...   %计算机非线性等式约束在点x处的函数值

37 2个不等式约束， 2个等式约束 3个决策变量x1，x2，x3 如果nonlcon以‘mycon1’作为参数值，则程序mycon1.m如下

38 对照约束条件编写myfun1.m function [c,ceq] = mycon1(x)
c(1) = x(1)*x(1)+x(2)*x(2)+x(3)*x(3)-100 c(2) = 60 - x(1)*x(1) + 10*x(3)*x(3) ceq(1) = x(1) + x(2)*x(2) + x(3) - 80 ceq(2) = x(1)^3 + x(2)*x(2) + x(3) - 80

39 nonlcon的高级用法 允许提供非线性约束条件中函数的梯度 设置方法：
options = optimset('GradConstr', 'on') 如果提供非线性约束条件中函数梯度， nonlcon的函数必须如下格式：

40 参数nonlcon的函数一般格式如下 function [c,ceq,GC,GCeq] = mycon(x)
c = ...          % 计算非线性不等式约束在点x处的函数值 ceq = ...     %计算机非线性等式约束在点x处的函数值 if nargout > 2   % nonlcon 如果四个输出参数    GC = ...      % 不等式约束的梯度    GCeq = ...    % 等式约束的梯度 end

41 输出参数语法： [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(...) 运用步骤： 将自己的模型转化为上面的形式 写出对应的参数 调用函数

42 请问： 1、结合fmincon函数，需要提供哪些参数

43 第一步：编写一个M文件返回目标函数f在点x处的值函数程序
函数myfun.m function f = myfun(x) f = -x(1) * x(2) * x(3);

44 第二步：为了调用MATLAB函数，必须将模型中的约束转化为如下形式(<=)。
这是2个线性约束，形如 这里： A=[ ; ]; b=[0 72]’;

45 第三步：提供一个搜索起点，然后调用相应函数，程序如下：
% 给一个初始搜索点 x0 = [10; 10; 10]; [x,fval] = fmincon('myfun',x0,A,b)

46 主程序（整体）： A=[-1 -2 -2; 1 2 2 ]; b=[0 72]’; % 给一个初始搜索点
x0 = [10; 10; 10]; [x,fval] = fmincon('myfun',x0,A,b)

47 最后得到如下结果：  x = fval = e+03

48 2.非负条件下线性最小二乘 lsqnonneg
适合如下模型： 注意：约束只有非负约束

49 x =lsqnonneg(c,d) x =lsqnonneg(c,d,x0) x =lsqnonneg(c,d,x0,options)
语法： x =lsqnonneg(c,d) x =lsqnonneg(c,d,x0) x =lsqnonneg(c,d,x0,options)

50 3.有约束线性最小二乘lsqlin 适合如下模型： 注意：约束有线性等式、不等式约束

51 语法： 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(...)

52 4.非线性最小二乘lsqnonlin 适合模型：

53 语法： 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(...)

54 resnorm 等于 norm(C*x-d)^2 residual 等于C*x-d
返回参数说明 resnorm 等于 norm(C*x-d)^2 residual 等于C*x-d 例1：求解x，使得下式最小

55 第一步：编写M文件myfun.m计算向量F
function F = myfun(x) k = 1:10; F = 2 + 2*k-exp(k*x(1))-exp(k*x(2));

56 第二步：调用优化函数lsqnonlin % 给定搜索起点 x0 = [0.3 0.4] ; % 调用求解函数
[x,resnorm] = lsqnonlin('myfun',x0) x = resnorm %residual or sum of squares resnorm =

57 能力培养： 1、建模分析能力 2、应用数学能力 3、算法设计与程序设计
5.学习回顾 能力培养： 1、建模分析能力 2、应用数学能力 3、算法设计与程序设计

58 谢 谢！