非线形规划讲稿.docx

一、基本概念

二、一维搜索
由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。
对于非线性规划模型(NP)，可以采用迭代方法求它的最优解。迭代方法的基本思想是：从一个选定的初始点出发，按照某一特定的迭代规则产生一个点列，使得当是有穷点列时，其最后一个点是(NP)的最优解；当是无穷点列时，它有极限点，并且其极限点是(NP)的最优解。
0° 选取初始点，令。
1° 构造搜索方向，依照一定规则，构造在点处关于的可行下降方向作为搜索方向。
2° 寻求搜索步长。以为起点沿搜索方向寻求适当的步长，使目标函数值有某种意义的下降。
3° 求出下一个迭代点。按迭代格式（1）求出
。
若已满足某种终止条件，停止迭代。
4° 以代替，回到1°步。
无约束问题
2.1 一维搜索方法
当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功—失败”，斐波那契法，0.618法等）；插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切线法，二分法等）。
考虑一维极小化问题
（2）
若是区间上的下单峰函数，我们介绍通过不断地缩短的长度，来搜索得（2）的近似最优解的两个方法。
为了缩短区间，逐步搜索得（2）的最优解的近似值，我们可以采用以下途径：在中任取两个关于是对称的点和（不妨设，并把它们叫做搜索点），计算和并比较它们的大小。对于单峰函数，若，则必有，因而是缩短了的单峰区间；若，则有，故是缩短了的单峰区间；若，则和都是缩短了的单峰。因此通过两个搜索点处目标函数值大小的比较，总可以获得缩短了的单峰区间。对于新的单峰区间重复上述做法，显然又可获得更短的单峰区间。如此进行，在单峰区间缩短到充分小时，我们可以取最后的搜索点作为（2）最优解的近似值。

三、无约束极值

无约束极值问题可表述为
（5）
求解问题（5）的迭代法大体上分为两种：一是用到函数的一阶导数或二阶导数，称为解析法。另一是仅用到函数值，称为直接法。
2.3.1 解析法
2.3.1.1 梯度法（最速下降法）
对基本迭代格式
（6）
我们总是考虑从点出发沿哪一个方向，使目标函数下降得最快。微积分的知识告诉我们，点的负梯度方向
，
是从点出发使下降最快的方向。为此，称负梯度方向为在点处的最速下降方向。
按基本迭代格式（6），每一轮从点出发沿最速下降方向作一维搜索，来建立求解无约束极值问题的方法，称之为最速下降法。
这个方法的特点是，每轮的搜索方向都是目标函数在当前点下降最快的方向。同时，用或作为停止条件。其具体步骤如下：
1°选取初始数据。选取初始点，给定终止误差，令。
2°求梯度向量。计算， 若，停止迭代，输出。否则，进行3°。
3° 构造负梯度方向。取
.
4° 进行一维搜索。求，使得

令转2°。
例4 用最速下降法求解无约束非线性规划问题

其中，要求选取初始点，终止误差。
解：（i）
编写M文件detaf.m如下
function [f,df]=detaf(x);
f=x(1)^2+25*x(2)^2;
df(1)=2*x(1);
df(2)=50*x(2);
（ii）编写M文件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
2.3.1.2 Newton法
考虑目标函数在点处的二次逼近式

假定Hesse阵

正定。
由于正定，函数的稳定点是的最小点。为求此最小点，令
，
即可解得
.
对照基本迭代格式（1），可知从点出发沿搜索方向。

并取步长即可得的最小点。通常，把方向叫做从点出发的Newton方向。从一初始点开始，每一轮从当前迭代点出发，沿Newton方向并取步长为1的求解方法，称之为Newton法。其具体步骤如下：
1°选取初始数据。选取初始点，给定终止误差，令。
2°求梯度向量。计算，若，停止迭代，输出。否则，进行3°。
3°构造Newton方向。计算，取
.
4° 求下一迭代点。令，转2°。
例5 用Newton法求解，

选取，。
解：（i）

编写M文件nwfun.m如下：
function [f,df,d2f]=nwfun(x);
f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;
df(1)=4*x(1)^3+2*x(1)*x(2)^2;
df(2)=100*x(2)^3+2*x(1)^2*x(2);
d2f(1,1)=12*x(1)^2+2*x(2)^2;
d2f(1,2)=4*x(1)*x(2);
d2f(2,1)=d2f(1,2);
d2f(2,2)=300*x(2)^2+4*x(1)*x(2);
（ii）编写M文件：
clc
x=[2;2];
[f0,g1,g2]=nwfun(x)
while norm(g1)>0.00001 %dead loop,for i=1:3
p=-inv(g2)*g1',p=p/norm(p)
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,g1,g2]=nwfun(x)
end
如果目标函数是非二次函数，一般地说，用Newton法通过有限轮迭代并不能保证可求得其最优解。
Newton法的优点是收敛速度快；缺点是有时不好用而需采取改进措施，此外，当维数较高时，计算的工作量很大。

§3 约束极值问题
带有约束条件的极值问题称为约束极值问题，也叫约束规划问题。
求解约束极值问题要比求解无约束极值问题困难得多。为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法。
3.1 二次规划
若某非线性规划的目标函数为自变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划。
Matlab中二次规划的数学模型可表述如下：

这里是实对称矩阵，是列向量，是相应维数的矩阵。
Matlab中求解二次规划的命令是
[X,FVAL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)
X的返回值是向量，FVAL的返回值是目标函数在X处的值。（具体细节可以参看在Matlab指令中运行help quadprog后的帮助）。
例8 求解二次规划

解 编写如下程序：
h=[4,-4;-4,8];
f=[-6;-3];
a=[1,1;4,1];
b=[3;9];
[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))
求得
。
3.2 罚函数法
利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因而也称这种方法为序列无约束最小化技术，简记为 SUMT (Sequential Unconstrained Minimization Technique)。
罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法，下面介绍外罚函数法。
考虑如下问题：

s.t.
取一个充分大的数 ，构造函数

（或
这里 ，，，为适当的行向量，Matlab中可以直接利用 和 函数。）则以增广目标函数为目标函数的无约束极值问题

的最优解也是原问题的最优解。
例9 求下列非线性规划

解 (i)编写 M 文件 test.m
function g=test(x);
M=50000;
f=x(1)^2+x(2)^2+8;
g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)...
+M*abs(-x(1)-x(2)^2+2);
(ii)在Matlab命令窗口输入
[x,y]=fminunc('test',rand(2,1))
即可求得问题的解。
§4 飞行管理问题
在约10，000m高空的某边长160km的正方形区域内，经常有若干架飞机作水平飞行。区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行飞行管理。当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：
1）不碰撞的标准为任意两架飞机的距离大于8km;
2）飞机飞行方向角调整的幅度不应超过30度；
3）所有飞机飞行速度均为每小时800km;
4）进入该区域的飞机在到达区域边缘时，与区域内飞机的距离应在60km以上；
5）最多需考虑6架飞机；
6）不必考虑飞机离开此区域后的状况。
请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进行计算（方向角误差不超过0.01度），要求飞机飞行方向角调整的幅度尽量小。
设该区域4个顶点的座标为(0,0)，(160,0)，(160,160)，(0,160)。记录数据为：
飞机编号 横座标 纵座标 方向角（度）
1 150 140 243
2 85 85 236
3 150 155 220.5
4 145 50 159
5 130 150 230
新进入 0 0 52
注：方向角指飞行方向与轴正向的夹角。
试根据实际应用背景对你的模型进行评价与推广。
提示：

，，
其中为飞机的总架数，为时刻第架飞机的坐标，分别表示第架飞机飞出正方形区域边界的时刻。这里
，，；
，，；
其中为飞机的速度，分别为第架飞机的初始方向角和调整后的方向角。
令

其中，

则两架飞机不碰撞的条件是。

习题：
某工厂向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交40台，第二季末交60台，第三季末交80台。工厂的最大生产能力为每季100台，每季的生产费用是（元），此处为该季生产发动机的台数。若工厂生产的多，多余的发动机可移到下季向用户交货，这样，工厂就需支付存贮费，每台发动机每季的存贮费为4元。问该厂每季应生产多少台发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季度开始时发动机无存货）。