运筹学 第2版 教学课件 作者 沈荣芳 第十四章　非线性规划.ppt

《运筹学 第2版 教学课件 作者 沈荣芳 第十四章　非线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十四章　非线性规划第一节　基本概念第二节　一维搜索方法第三节　最速下降法和DFP法第四节　单纯形法第五节　约束最优化方法第一节　基本概念一、非线性规划的数学模型二、函数的凸性三、非线性规划寻优方法概述一、非线性规划的数学模型非线性规划的数学模型通常表示为以下形式Minf(x)j(x)≥0，j=1，2，…，k其中X=(x1，x2，…，xn)，T是n维欧氏空间En中的向量(点)，f(x)为目标函数，j(x)≥0为约束条件。目标函数和约束条件中至少有一个是自变量x的非线性函数。二、函数的凸性1.一元函数的情况2.多元函数的情况

2、3.凸函数的基本性质4.函数的凸性与局部极值及全局最优值之间的关系1.一元函数的情况图　14-12.多元函数的情况图　14-23.凸函数的基本性质(1)若f1(x)与f2(x)为凸集D上的两个凸函数，则对任意的正数a与b，函数af1(x)+bf2(x)仍为D上的凸函数。(2)当函数f(x)在凸集D上二阶导数连续时，则对于所有的x∈D，f(x)为凸函数的充分必要条件是：赫森矩阵A为半正定。若赫森矩阵A为正定，则f(x)为严格凸函数。4.函数的凸性与局部极值及全局最优值之间的关系设f(x)为定义在凸集D上的一个函数，一般来说，

3、f(x)的极值点不一定是它的最优点。但是，若f(x)为D上的一个凸函数，则f(x)的任何极值点，同时也是它的最优点。若f(x)是严格的凸函数，则它有唯一的最优点。三、非线性规划寻优方法概述1.间接寻优方法(解析法)2.直接寻优方法(搜索法)1.间接寻优方法(解析法)利用求导数寻求函数极值的方法，即古典的微分法就属于这一类。这类方法要求把一个非线性规划问题用数学方程式描述出来，然后按照函数极值的必要条件用数学分析的方法求出其解析解，再按照充分条件或者问题的实际物理意义间接地确定最优解，因此称为间接法，也称为解析法。2.直接寻

4、优方法(搜索法)这是一种数值方法，利用函数在某一局部区域的性质或一些已知点的数值。来确定下一步计算的点，这样一步步搜索、逼近，最后达到最优点。直接寻优方法又分为两大类：消去法和爬山法。第二节　一维搜索方法一、概述二、黄金分割法(0.618法)一、概述(1)确定初始搜索区间，该区间必须是单峰区间。(2)确定最优步长。一、概述图　14-3图　14-4二、黄金分割法(0.618法)第三节　最速下降法和DFP法一、最速下降法二、DFP法一、最速下降法(1)取初始点x1∈En，允许误差ε＞0，令k∶=1。(2)计算zk=-fx(xk

5、)T。(3)检验是否满足条件(4)求单变量极值问题的最优解λk∈E1(5)令xk+1=xk+λkzk，k∶=k+1，转到(2)。一、最速下降法图　14-5二、DFP法(1)取初始点x1∈En，允许误差ε＞0。(2)检验是否满足条件(3)则H1=I(n)，I(n)为n×n单位矩阵，记(4)令=zk=-Hkgk。(5)求单变量极值问题的最优解λk：(6)令x(k+1)=xk+λkzk。(7)检验是否满足条件‖fx(xk+1)T‖≤ε？若满足，则迭代停止，得到点xk+1；否则，当k=n时，令x1∶=xk+1，转到(3)；当k＜n

6、时，令gk+1=fx(xk+1)T，ΔgK=gk+1-gk，Δxk=xk+1-xk，计算n×n阶方阵(8)令k∶=k+1，转到(4)。第四节　单纯形法一、基本原理二、计算方法三、计算举例一、基本原理图　14-6二、计算方法(1)计算函数值Fi=F(X(i))(i=0，(2)求出反射点，对于n维的情况，除最差点X(H)外n个顶点的质量中心X(F)的坐标可表示为(3)若FR=F(X(R))＞FG，先比较FR和FH，若FR＞FH，则先对换XH与XR，然后压缩步长，否则直接压缩步长。(4)若FR＜FG，要加大步长。(5)若FS＜F

7、G，把X(H)点舍去，以X(S)点和其他n个顶点构成新的单纯形，重复上述步骤。(6)进行单纯形的收缩，令(7)上述步骤要继续进行到满足三、计算举例例3目标函数为F(X)=x21+x22-x1x2-4x2-10x1+60设X(0)=(0，0)T，E1=(1，0)T，E2=(0，1)T取初始步长h=2，延伸系数μ=2，压缩因子λ=0.75，精度ε=0.001。试用单纯形法求极小。第五节　约束最优化方法一、拉格朗日(Lagrangian)乘子法二、罚函数法一、拉格朗日(Lagrangian)乘子法引进待定乘子λ，将有等式约束的寻

8、优问题转化为无约束的寻优问题的做法，称为拉格朗日乘子法。二、罚函数法1.内点法2.外点法3.内点法与外点法的比较4.计算实例二、罚函数法1.内点法2.外点法3.内点法与外点法的比较内点法与外点法相比较各有优缺点：(1)内点法首先要在可行域内求可行的初始点，这当约束条件增多时，往往是困难的；而外点法则不需