（三）非线性规划
第三章——非线性规划
非线性规划
背景
非线性规划目前还没有适于各种问题的一般算法，各个方法都有自己特定的适用范围
注意事项
确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案
提出追求目标，并且，运用各种科学和技术原理，把它表示成数学关系式。
-
给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它
具体量化
寻求限制条件，这些条件通常用变量之间的一些不等式或等式来表示。
与线性规划的区别：非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。而线性优化只能在边界达到。
具体案例
%编写M 文件fun1.m 定义目标函数
function f=fun1(x);
f=sum(x.^2)+8;
%编写M文件fun2.m定义非线性约束条件
function [g,h]=fun2(x);
g=[-x(1)^2+x(2)-x(3)^2
x(1)+x(2)^2+x(3)^3-20]; %非线性不等式约束
h=[-x(1)-x(2)^2+2
x(2)+2*x(3)^2-3]; %非线性等式约束
%编写主程序文件example2.m 如下：
options=optimset('largescale','off');
[x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[],'fun2', options)对于非线性规划模型 (NP——Non-deterministic polynomial^非定常多项式^）可以采用迭代方法求它的最优解。
迭代方法的基本思想是：从一个选定的初始点
x0∈Rn 出发，按照某一特定的迭代规则产生一个点列xk ，使得当xk 是有穷点列时，其最后一个点是(NP)的最优解；当xk 是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。使用迭代方法求解(NP)的关键在于，如何构造每一轮的搜索方向和确定适当的步长。
-
凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优解的集合形成一个凸集。当凸规划的目标函数
f(x) 为严格凸函数时，其最优解必定唯一（假定最优解存在）。由此可见，凸规划是一类比较简单而又具有重要理论意义的非线性规划此处讨论十分浅显，待续^见46页^
无约束问题
一维搜索
当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。常见如下：
-
试探法（“成功—失败”，斐波那契法，0.618 法(斐波那契的近似算法，较易实现效果好)）
斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数，达到预定的某一缩短率。
插值法（抛物线插值法，三次插值法等）
微积分中的求根法（切线法，二分法等）
二次插值法
对极小化问题，当
未完待续
无约束极值问题的解法
-
解析法
-
梯度法（最速下降法）——每轮的搜索方向都是目标函数在当前点下降最快的方向
案例：用最速下降法求解
minf(x)=x21+25x22 其中
x=(x1,x2)T ,要求初始点为x0=(2,2)T 解：
∇f(x)=(2x1,50x2)T %编写M文件detaf.m，定义函数f(x)及其梯度列向量如下 function [f,df]=detaf(x); f=x(1)^2+25*x(2)^2; df=[2*x(1) 50*x(2)]; %编写主程序文件zuisu.m如下： clc x=[2;2]; [f0,g]=detaf(x); while norm(g)>0.000001 p=-g/norm(g); t=1.0;f=detaf(x+t*p); while f>f0 t=t/2; f=detaf(x+t*p); end x=x+t*p; [f0,g]=detaf(x); end x,f0对
∇ 还需熟练其使用，待续~ -
Newton 法：。从一初始点开始，每一轮从当前迭代点出发，沿Newton 方向并取步长为1 的求解方法，称之为Newton 法。
案例：用Newton法求解
minf(x)=x41+25x42+x21x22 选取
x0=(2,2)T %编写M文件nwfun.m 如下： function [f,df,d2f]=nwfun(x); f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2; df=[4*x(1)^3+2*x(1)*x(2)^2;100*x(2)^3+2*x(1)^2*x(2)]; d2f=[2*x(1)^2+2*x(2)^2,4*x(1)*x(2) 4*x(1)*x(2),300*x(2)^2+2*x(1)^2]; %编写主程序文example5.m 如下： clc x=[2;2]; [f0,g1,g2]=nwfun(x); while norm(g1)>0.00001 p=-inv(g2)*g1; x=x+p; [f0,g1,g2]=nwfun(x); end x, f0如果目标函数是非二次函数，一般地说，用Newton 法通过有限轮迭代并不能保证可求得其最优解。为了提高计算精度，我们在迭代时可以采用变步长计算上述问题。具体^见51页^
优点是收敛速度快；缺点是有时不好用而需采取改进措施；此外，当维数较高时，计算的工作量很大
-
变尺度法——Variable Metric Algorithm
它不仅是求解无约束极值问题非常有效的算法，而且也已被推广用来求解约束极值问题。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性，因而使变尺度法获得了很高的声誉。具体^见51页^
-
-
直接法
在无约束非线性规划方法中，遇到问题的目标函数不可导或导函数的解析式难以表示时，人们一般需要使用直接搜索方法。同时，由于这些方法一般都比较直观和易于理解，因而在实际应用中常为人们所采用。
Powell方法：
- 基本搜索
- 加速搜索
- 调整搜索
具体步骤^见54页^
Matlab 求无约束极值问题
-
符号解：
%计算的Matlab程序如下 clc, clear syms x y f=x^3-y^3+3*x^2+3*y^2-9*x; df=jacobian(f); %求一阶偏导数 d2f=jacobian(df); %求Hessian阵 [xx,yy]=solve(df) %求驻点 xx=double(xx);yy=double(yy); for i=1:length(xx) a=subs(d2f,{x,y},{xx(i),yy(i)}); b=eig(a); %求矩阵的特征值 f=subs(f,{x,y},{xx(i),yy(i)});f=double(f); if all(b>0) fprintf('(%f,%f)是极小值点,对应的极小为%f\n',xx(i),yy(i),f); elseif all(b<0) fprintf('(%f,%f)是极大值点,对应的极大值为%f\n',xx(i),yy(i),f); elseif any(b>0) & any(b<0) fprintf('(%f,%f)不是极值点\n',xx(i),yy(i)); else fprintf('无法判断(%f,%f)是否是极值点\n',xx(i),yy(i)); end end
-
数值解：在 Matlab 工具箱中，用于求解无约束极值问题的函数有fminunc 和fminsearch，用法介绍如下。
[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2,) %X0是向量x的初始值，OPTIONS是优化参数,可以使用缺省参数。P1，P2 是可以传递给FUN的一些参数。 [X,FVAL,EXITFLAG,OUTPUT]=FMINSEARCH(FUN,X0,OPTIONS,P1,P2,) %%fminunc,fminsearch区别 %前者多用于连续函数，后者可用于不连续函数（使用的无倒数方法）符号解（准确的叫法是解析解）是准确解。但事实上很多常微分方程是没有解析解的，因此只能能过数值的方法去解决。
-
函数零点与方程组的解
%使用符号求解的程序如下 syms x x0=solve(x^3-x^2+2*x-3) %求函数零点的符号解 x0=vpa(x0,5) %化成小数格式的数据 %求得全部的零点 %求数值解的Matlab程序如下 [email protected](x)x^3-x^2+2*x-3; x=fsolve(y,rand) %只能求给定初始值附近的一个零点
约束极值问题的解法
带有约束条件的极值问题称为约束极值问题，也叫规划问题。
-
简化方法：
- 将约束问题化为无约束问题
- 将非线性规划问题化为线性规划问题
- 将复杂问题变换为较简单问题的其它方法
库恩—塔克条件——非线性规划领域中最重要的理论成果之一，是确定某点为最优点的必要条件，但一般说它并不是充分条件（对于凸规划，它既是最优点存在的必要条件，同时也是充分条件）。
-
二次规划
定义：若某非线性规划的目标函数为自变量 x 的二次函数，约束条件又全是线性的，就称
这种规划为二次规划。-
求解
[X,FVAL]=QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)
-
罚函数法
利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential Unconstrained Minization Technique)。
基本思想：利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。
分为内罚函数法和外罚函数法^见56页^
-
案例：
function g=test(x); M=50000; f=x(1)^2+x(2)^2+8; g=f-M*min(min(x),0)-M*min(x(1)^2-x(2),0)+M*(-x(1)-x(2)^2+2)^2; %实现 [x,y]=fminunc('test',rand(2,1))
Matlab 求约束极值问题
见58页
Matlab 优化工具箱的用户图形界面
optimtool 可应用到所有优化问题的求解，计算结果可以输出到Matlab 工作空间中
飞行管理问题
-
本问题中的优化目标函数可以有不同的形式：如使所有飞机的最大调整量最小；所有飞机的调整量绝对值之和最小等。这里以所有飞机的调整量绝对值之和最小为目标函数，可以得到如下的数学规划模型：
min∑i=16|△θi|s.t.|β0ij+12(△θi+△θj)|>α0ij,i,j=1,2,…,6,i≠j|△θi|≤30∘ -
模型一代码：
clc,clear x0=[150 85 150 145 130 0]; y0=[140 85 155 50 150 0]; q=[243 236 220.5 159 230 52]; xy0=[x0; y0]; d0=dist(xy0); %求矩阵各个列向量之间的距离 d0(find(d0==0))=inf; a0=asind(8./d0) %以度为单位的反函数 xy1=x0+i*y0 xy2=exp(i*q*pi/180) for m=1:6 for n=1:6 if n~=m b0(m,n)=angle((xy2(n)-xy2(m))/(xy1(m)-xy1(n))); end end end b0=b0*180/pi; dlmwrite('txt1.txt',a0,'delimiter','\t','newline','PC'); fid=fopen('txt1.txt','a'); fwrite(fid,'~','char'); %往纯文本文件中写LINGO 数据的分割符 dlmwrite('txt1.txt',b0,'delimiter','\t','newline','PC','-append','roffset', 1)