非线性规划-无约束问题课件

第三章最优化方法运筹学当要求容器的容积一定，求表面积最小，以使用料最省。第三节非线性规划x1x2s.tx1≥0，x2≥0一连续反应器如图所示，进行如下反应根据预测，市场只能提供物料A600单位/h，产品B的市场需求量FB不超过50单位/h，产品B的价格为C3=2000元/单位。试确定物料A的进料速度FA0、初始浓度CA0、反应器体积V和转化率各取多大，才能使得该反应器在单位时间内的经济效益是最好的？目标函数或约束条件中有非线性函数的规划问题非线性规划非线性规划的最优解可能在其可行域中的任意一点达到不一定是全局最优解求解思路：迭代从一个选定的初始点x0出发，按照某种特定的迭代规则产生一个点列{xk}xk有穷点列：最后一个点为最优解xk无穷点列：其中一个点为最优解对于存在ε>0，使则称x*为R上的局部极小点，f(x*)称为局部极小值→严格局部极小点、严格局部极小值基本概念若对于任意x，有则x*为R上的全局极小点，f(x*)为全局极小值→严格全局极小点、严格全局极小值基本概念Hessian矩阵凸性和凹性的判定（二阶条件）H为对称矩阵多元函数，如何判断H是否正定？特征值f(x)H特征值严格凸函数正定>0凸函数半正定≥0凹函数半负定≤0严格凹函数负定<0既凸又凹（线性函数）=0非凸非凹>0,<0H正定，f(x)为严格凸函数对n维函数必要条件：f(x)在x*处一阶可导充分条件H(x*)正定，则x*为极小值，反之为极大值例求函数的所有稳定点解试判断所得的稳定点是否为最优解求得各点的H特征值和稳定点类型如下：稳定点f(x)特征值1.941，3.8540.985537.030.97局部极小点-1.053，1.028-0.513410.503.50（全局）极小点0.6117，1.49292.83007.0-2.56鞍点一维搜索法步长tk的选定是由使目标函数值沿搜索方向下降最多为依据的，因此这一工作变成了求解以tk为变量的一元函数，故得名一维搜索法。无约束问题适用于某些不能求得一阶导数解析解的问题如求最小回流比其中ij：组分i对组分j的相对挥发度

xDi：塔顶产品中i组分的组成

：由Underwood公式确定用经典的微分方法很难求解斐波那契（Fibonacci）法（分数法）0.618法无需求导，根据函数值判断搜索方向适用于求解已知极值区间的单峰函数一维搜索法（消去法）f(x2)＜f(x1)，去掉[x1,b0]，此时x*[a0,x1]一维搜索法（消去法）f(x)xoa0b0x*x1,x2在x*的右侧x1x2f(x2)＞f(x1)，去掉[a0,x2]，此时x*[x2,b0]一维搜索法（消去法）f(x)xoa0b0x*x1,x2在x*的左侧x1x2f(x2)＝f(x1)：

a.去掉[x1,b0]，此时x*[a0,x1]b.去掉[a0,x2]，此时x*[x2,b0]f(x)xoa0b0x*x1,x2在x*的两侧x1x2斐波那契数列数列{Fn}为斐波那契数列

斐波那契分数斐波那契（Fibonacci）法n012345Fn112358n67891011Fn1321345589144计算步骤选取初始数据，确定单峰区间[a0,b0]根据缩短率计算Fn，再确定最小n值计算初值t1和t2，计算f(t1)、f(t2)当区间变为[a0,t2]反之区间变为[t1,b0]确定n个搜索点以后，每次的区间缩短率为n次计算能得到的区间长度比为要使精度够大，即δ：区间缩短的相对精度如果至某一步则可令可以证明对于斐波那契数列，其奇数项和偶数项都各自收敛于同一极限，该极限值等于0.618法以0.618作为固定的区间缩短率代替斐波那契法不同的缩短率，就得到了0.618法实施更为容易计算步骤选取初始区间[a0,b0]

f(t1)<f(t2)，取[a1=a0,b1=t2]

t’2=t1

t’1=a1+0.382(b1-a1)

f(t1)＞f(t2)，取[a1=t1,b1=b0]

t’2=a1+

0.618(b1-a1)

t’1=t2

Lt2t1a0b0La1b1t’2t’1a1b1t’2t’1搜索n个点后的区间长度缩短为或者说，迭代k次以后的区间长度变为即已知搜索的相对精度，迭代次数满足例用0.618法求设初始区间为a0=-1.0，b0=3.0，要求剩余区间长度不大于0.1解本例可以通过解析法求得精确解第一次搜索选取两个初始试算点比较得，可以得到下一次搜索区间第二次搜索计算试算点确定下一轮搜索区间迭代次数kak-1bk-1x(k,1)x(k,2)φ(x(k,1))φ(x(k,2))剩余区间长度1-130.5281.4721.750782.694782.4722-11.472-0.0556960.5282.058791.750781.5276963-0.0556961.4720.5280.888421.750781.900870.9441164-0.0556960.888420.3049560.5281.788041.750780.58346450.3049560.888420.5280.6655361.750781.777400.3605860.3049560.6655360.44270.5281.75321.750780.228……101.750021.750060.0325不断用低次（不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近最优解多项式近似（插值法、抛物线法）使用导数的方法对于迭代格式使目标函数f下降最快的方向是点xk的负梯度方向称为f在xk的最速下降方向每一轮都从点xk出发沿最速下降方向进行搜索的方法，称为最速下降法最速下降法具体步骤选取初始点x0，给定终止误差求梯度向量。计算

，若

，停止迭代，输出xk构造负梯度方向进行搜索。求tk，使得令

，重新求梯度向量最速下降法例求解令x(0)=(μ1,μ2)T,μ1，μ2为任意实数假设x(0)不是最优点则令代入目标函数，求最优步长t0有令因故x(1)为最优解，最优值f(x*)=0对于目标函数的等值线为圆的问题，最速下降法总能一步得到最优解例用最速下降法求解

取x(0)=(2,2)T令代入目标函数，得t(0)=2.005继续迭代，得kt(k)x1x202.0052.0002100.0810411.8501.920-0.0033.8433.68720.0710.0710.0713.5470.13130.0650.0680.0000.1360.463×10-240.0030.0030.0030.1260.164×10-2可能在任何类型的稳定点终止。通过分析Hessian矩阵来检验是否是极小点。对f(x)的尺度太灵敏，收敛缓慢，容易产生大量摆动（局部最速下降，相邻搜索方向彼此正交）。最速下降法f(x)为二阶可导函数，且在每个搜索方向上能准确最小化，则较少次迭代即可收敛计算量略大，收敛速度大幅提高搜索方向结合当前梯度方向和前一次梯度方向，搜索方向共轭解大型线性或非线性方程组最有效的方法之一存储空间小，稳定性高共轭梯度法牛顿法（Newton’smethod）

（Newton-Raphsonmethod）若H正定，则Q(x)的稳定点xk+1为最小点，该点可表示为解得对照可得由此，可反复利用方程直到满足收敛条件牛顿法例用牛顿法求解该函数的一阶、二阶导数分别为一维函数的牛顿法若取初始点x(0)=3，则故迭代次数kx(k)φ’(x(k))φ’’(x(k))|φ’(x(k))|03-52245215.167153.352184.33153.35224.33532.302109.44632.30234.0403.38386.8703.38344.0010.005584.0470.0055|φ’(x(k))|<0.01例求解解，取x(0)=(0,0)T有得为检验x(1)是否为最优点，即x(1)为最优点几何意义牛顿法收敛速度很快，对于严格凸函数，只需一步即可得到极小值对纯牛顿法模型，如果初始值与局部极小值不是足够接近，通常不收敛需要计算一阶、二阶导数，计算量大，存储空间大对于一阶导数非单调变化的函数，往往会失败牛顿法为避免计算二阶导数矩阵H及其逆阵，我们设法构造另一个矩阵，用它来逼近二阶导数矩阵的逆阵

，称拟牛顿法拟牛顿法（Quasi-NewtonMethod）构造近似矩阵当f(x)为二阶函数，H