非线形规划讲稿一、根本概念二、一维搜索由于线性规划的目的函数为线性函数，可行域为凸集，因此求出的最优解就是整个可行域上的全局最优解非线性规划却不然，有时求出的某个解虽是一局部可行域上的极值点，但并不一定是整个可行域上的全局最优解对于非线性规划模型(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 用最速下降法求解无约束非线性规划问题其中，要求选取初始点，终止误差解：〔 = 1 \_roman i〕编写M文件detaf.m如下function [f,df]=detaf(_);f=_(1)2+25__(2)2;df(1)=2__(1);df(2)=50__(2);〔 = 2 \_roman ii〕编写M文件zuisu.mclc_=[2;2];[f0,g]=detaf(_);while norm(g)>0.000001p=-g'/norm(g);t=1.0;f=detaf(_+t_p);while f>f0t=t/2;f=detaf(_+t_p);end_=_+t_p[f0,g]=detaf(_)end2.3.1.2 Newton考虑目的函数在点处的二次逼近式假定Hesse阵正定由于正定，函数的稳定点是的最小点。
为求此最小点，令，即可解得.对照根本迭代格式〔1〕，可知从点出发沿搜索方向并取步长即可得的最小点通常，把方向叫做从点出发的Newton方向从一初始点开场，每一轮从当前迭代点出发，沿Newton方向并取步长为1的求解方法，称之为Newton法其详细步骤如下：1°选取初始数据选取初始点，给定终止误差，令2°求梯度向量计算，假设，停顿迭代，输出否那么，进展3°3°构造Newton方向计算，取.4° 求下一迭代点令，转2°例5 用Newton法求解，选取，解：〔 = 1 \_roman i〕编写M文件nwfun.m如下：function [f,df,d2f]=nwfun(_);f=_(1)4+25__(2)4+_(1)2__(2)2;df(1)=4__(1)3+2__(1)__(2)2;df(2)=100__(2)3+2__(1)2__(2);d2f(1,1)=12__(1)2+2__(2)2;d2f(1,2)=4__(1)__(2);d2f(2,1)=d2f(1,2);d2f(2,2)=300__(2)2+4__(1)__(2);〔 = 2 \_roman ii〕编写M文件：clc_=[2;2];[f0,g1,g2]=nwfun(_)while norm(g1)>0.00001 dead loop,for i=1:3p=-inv(g2)_g1',p=p/norm(p)t=1.0,f=detaf(_+t_p)while f>f0t=t/2,f=detaf(_+t_p),end_=_+t_p[f0,g1,g2]=nwfun(_)end假如目的函数是非二次函数，一般地说，用Newton法通过有限轮迭代并不能保证可求得其最优解。
Newton法的优点是收敛速度快；缺点是有时不好用而需采取改良措施，此外，当维数较高时，计算的工作量很大§3 约束极值问题带有约束条件的极值问题称为约束极值问题，也叫约束规划问题求解约束极值问题要比求解无约束极值问题困难得多为了简化其优化工作，可采用以下方法：将约束问题化为无约束问题；将非线性规划问题化为线性规划问题，以及能将复杂问题变换为较简单问题的其它方法二次规划假设某非线性规划的目的函数为自变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划Matlab中二次规划的数学模型可表述如下：这里是实对称矩阵，是列向量，是相应维数的矩阵Matlab中求解二次规划的命令是[_,FVAL]= QUADPROG(H,f,A,b,Aeq,beq,LB,UB,,OPTIONS)_的返回值是向量，FVAL的返回值是目的函数在_处的值〔详细细节可以参看在Matlab指令中运行help quadprog后的帮助〕例8 求解二次规划解 编写如下程序：h=[4,-4;-4,8];f=[-6;-3];a=[1,1;4,1];b=[3;9];[_,value]=quadprog(h,f,a,b,[],[],zeros(2,1))求得。
罚函数法利用罚函数法，可将非线性规划问题的求解，转化为求解一系列无约束极值问题，因此也称这种方法为序列无约束最小化技术，简记为?SUMT (Sequential Unconstrained Minimization Technique)罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目的函数，把问题转化为无约束非线性规划问题主要有两种形式，一种叫外罚函数法，另一种叫内罚函数法，下面介绍外罚函数法考虑如下问题：s.t.取一个充分大的数 ，构造函数〔或这里 ，，，为适当的行向量，Matlab中可以直接利用 和 函数〕那么以增广目的函数为目的函数的无约束极值问题的最优解也是原问题的最优解例9 求以下非线性规划解 ( = 1 \_roman i)编写 M 文件 test.m function g=test(_);M=50000;f=_(1)2+_(2)2+8;g=f-M_min(_(1),0)-M_min(_(2),0)-M_min(_(1)2-_(2),0)+M_abs(-_(1)-_(2)2+2);( = 2 \_roman ii)在Matlab命令窗口输入[_,y]=fminunc('test',rand(2,1))即可求得问题的解。
§4 飞行管理问题在约10，000m高空的某边长1601〕不碰撞的标准为任意两架飞机的间隔 大于8km2〕飞机飞行方向角调整的幅度不应超过30度； 3〕所有飞机飞行速度均为每小时800km4〕进入该区域的飞机在到达区域边缘时，与区域内飞机的间隔 应在60km以上； 5〕最多需考虑6架飞机； 6〕不必考虑飞机分开此区域后的状况请你对这个防止碰撞的飞行管理问题建立数学模型，列出计算步骤，对以下数据进展计算〔方向角误差不超过0.01度〕，要求飞机飞行方向角调整的幅度尽量小设该区域4个顶点的座标为(0,0)，(160,0)，(160,160)，(0,160)记录数据为：飞机编号 横座标 纵座标 方向角〔度〕1 150 140 2432 85 85 2363 150 155 220.54 145 50 1595 130 150 230新进入 0 0 52注：方向角指飞行方向与轴正向的夹角。
试根据实际应用背景对你的模型进展评价与推广提示：，，其中为飞机的总架数，为时刻第架飞机的坐标，分别表示第架飞机飞出正方形区域边界的时刻这里，，； ，，； 其中为飞机的速度，分别为第架飞机的初始方向角和调整后的方向角令其中，那么两架飞机不碰撞的条件是习题：某工厂向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交40台，第二季末交60台，第三季末交80台工厂的最大消费才能为每季100台，每季的消费费用是〔元〕，此处为该季消费发动机的台数假设工厂消费的多，多余的发动机可移到下季向用户交货，这样，工厂就需支付存贮费，每台发动机每季的存贮费为4元问该厂每季应消费多少台发动机，才能既满足交货合同，又使工厂所花费的费用最少〔假定第一季度开场时发动机无存货〕第 8 页 共 8 页。