化工系统工程_03非线性规划

1、nonlinear programming, NLP非线性规划一般包括无约束极值问题：没有任何约束条件约束极值问题：在等式或不等式约束下求最大或最小。非线性规划解理论现状：解析理论：非线性规划问题的解理论本身在所有应用数学进行分析的学科中都是非常重要的基础，例如经济学中的消费者理论、厂商理论都是在非线性规划解理论基础上发展起来的。数值求解：实际求解时，往往只能得到近似解；不能保证是全局最优；常常出现不收敛的情况。因此只要可能，实际建模时尽可能建为线性模型。几类基本优化问题及其困难性几类基本优化问题及其困难性)(minxfSx其中其中一般形式一般形式nRS mRxf)(可行域可行域目标函数目标函

2、数有无约束有无约束, 连续连续, 离散离散, 凸凸, 非凸非凸, 确定确定, 随机随机单目标单目标, 多目标多目标, 连续连续, 可导可导, 凸凸, 非凸非凸求解多元函数的无约束极小点问题目前被人们所广泛接受的一种方法就是下降迭代算法，也称为搜索法。搜索法发展的理由在于：在许多实际问题中，目标函数不满足凸性，于是促使人们考虑直接从函数的特性出发，对局部最优解进行搜索。只利用目标函数值的变化进行试探性搜索称为直接搜索法；根据目标函数的解析性质确定搜索的方法称为解析搜索法。 )(minxfnRx无约束无约束, 单目标单目标, 连续变量连续变量基本方法基本方法寻找下降方向寻找下降方向, 局部搜索前进

3、局部搜索前进一阶可导函数理论解：Max（min）f(x)必要条件：一阶条件：导数（偏导数）0。也就是或者说，梯度0：性质：只是必要条件，满足一阶条件并不一定是极值点。极大点和极小点都满足同样条件。需考察二阶条件才能知道是否为极值点以及是极大点还是极小点。不能保证是全局极值而不是局部极值。01nxfxf0),(1nxfxff数值算法：迭代过程由四个部分组成初始点：可由用户自行选择；搜索方向：从什么方向去寻找下一个点；步长：在搜索方向上走多远，一般有三种方法：固定步长：一次走固定距离；可变步长：如果固定距离目标函数值没有改善，就扩大或缩小步长计算目标函数值；最优步长：在搜索方向上寻找使目标函数值最

4、优的步长（一维搜索）；终止条件：绝对误差，如果|xk+1-xk|e或者|f(xk+1)-f(xk)|e ，e为最初选定的精度标准则停止；相对误差，如果|xk+1-xk|/|xk|e或者|f(xk+1)-f(xk)|/|f(xk)|e，则停止；梯度：如果梯度的长度小于e，则停止。一个公司销售四种药品，每年在每个推销员身上要花费5万元，从推销队伍获得的收入（排除了其他成本之后）为：其中xi为分配给每种药品的推销队伍人数。如何使利润最大呢？3.046.0375.025.013000 )4(1800 )3(1500 )2(2000 )1(xxxx一个公司要建立一个仓库，从那里将货物发送给四个客户，客户

5、的空间位置和需求量分别是：客户 X坐标 Y坐标 年度需求量客户1 5 10 200客户2 10 5 150客户3 0 12 180客户4 12 0 250仓库应该修在什么地方使得总运输里程最小 1234x)(xf1dx 2d局部最优局部最优(陷阱陷阱)全局全局最优最优(一般情况下一般情况下)无法克服的困难无法克服的困难克服困难的两种途径克服困难的两种途径1) 限制问题的类型限制问题的类型前者理论上可彻底解决问题前者理论上可彻底解决问题, 但适用范围小但适用范围小2) 采取跳出局部陷阱的措施采取跳出局部陷阱的措施后者适用范围大后者适用范围大, 但理论上不能保证解决问题但理论上不能保证解决问题最常

6、用的条件最常用的条件 凸性凸性x)(xf)2(xx)1(x) 1 (xf xf)2(xf xl xlxf) 2()1 () 1 () 2()1 () 1 (xfxfxxf凸函数定义凸函数定义1, 0,) 2(),1 (nRxx对任意的对任意的总是成立总是成立x xl凸性能保证局部最优就是全局最优凸性能保证局部最优就是全局最优 1, 0()1 ()1 ()1 (*xfxfxfxfxfxxfxxxf设设*x是全局最优解是全局最优解如果如果 *xfxf, 由凸性可知由凸性可知说明这种点不会是局部最优解说明这种点不会是局部最优解凸集凸集的定义为：集合中任意两个点的连接线段仍然属于该集合，则该集合称为凸

7、集。凸集定义可用数学符号表示如下：如s是凸集，则其中元素满足10,)1 (,1221sxxxsxx定理：任意个凸集的交集仍是凸集设有K个凸集Ri（i1，2，K），用R表示它们的交集，若点x1、x2R，则从交集的定义知xx1（1）x2Ri（i1，2，K）式中01所以：xR也即R也是凸集。增加初始点有助于找到全局最优解增加初始点有助于找到全局最优解x)(xf1dx 2d例例 遗传算法遗传算法Genetic Algorithm容许目标函数上升有助于跳出局部陷阱容许目标函数上升有助于跳出局部陷阱x)(xf1dx 2d例例 禁忌搜索禁忌搜索 模拟退火模拟退火Taboo SearchSimulated A

8、nnealing当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：1. 区域消去法（“成功失败”，斐波那契Fibonacci法，0.618法等）；2. 插值法（抛物线插值法，三次插值法等）；3. 微积分中的求根法（切线法，二分法等）。)(mintfbta)(tf,ba,ba考虑一维极小化问题是区间上的下单峰函数，我们可以通过不断地缩短的长度，来搜索得近似最优解。单峰函数单峰函数设f(x)是定义在取间a.b上的一元函数。x*是f(x)在a,b上的全局极小点。如果f(x)在a,x*)上严格单调下降，在(x*,b上严格单调上升，则称f(x

9、)是a,b上的单峰函数。（下单峰函数） *x*x定理：若f在闭区间axb内为下单峰连续函数，x*点为极小值。设x1、x2为区间内的两点，且ax1x2f(x2)，则极小值不在(a,x1)内；2.若f(x1)f(x2)，则极小值不在(x2,b)内；3.若f(x1)=f(x2)，则极小值在(x1,x2)内。x)(xfba1x2x*x0.618法（黄金分割法）法（黄金分割法） 0.618法和斐波那契（Fibonacci）法都是分割方法，其基本思想是通过取试探点和进行函数值的比较，使包含极小点的搜索区间不断缩短，当区间长度缩短到一定程度时，区间上各点的函数值均接近极小值，从而各点可以作为极小点的近似点。

10、这类方法仅需要计算函数值，用途很广，尤其适用于非光滑及导数表达式复杂或写不出的种种情况。 基本原理基本原理 通过比较搜索区间内两点的函数值，逐步通过比较搜索区间内两点的函数值，逐步缩短搜索区间缩短搜索区间； 比如：x1，x2(a,b),其中 x1x2 , 若f(x1)f(x2),取 x1,b为新的搜索区间。对新的搜索区间，再增加一个新的内点，通过比较上一次保留下来的内点和新选定内点的函数值便可得到一个新的缩小了的搜索区间。 x)(xfba1x2x3x如只进行一次消去操作，只需比较区间a,b中点及距中点很近一点函数值，如此至少可消去原区间的1/2。abx1x2如进行两次消去操作，最好可使剩余区域

11、的中点恰好为消去中考虑的两点中之一，如下图所示消去ax1后x2为x1b的中点。此时便转化为上面情形。abx1x2按此思想可将进行n次消去操作的过程转化为进行n-1次消去的过程。这种方法对区间的划分比例符合Fibonacci分数的定义。12111112111,nnnnnnnnnnnFFFFFFFFFbxbxFFabbxabx1x2在上述原则下，为使去掉的区间长一些，就一次而论，应使两点尽量靠近区间中点，这样无论去掉那一侧，都可使区间缩短近一半，但是，由于此次留下的内点相当靠近留下的区间的一侧，下一步再按对称原则增选内点时，在去掉的区间部分必然较小，总体效益不好，于是可考虑采取如下对策所选内点使区间缩短率固定，即=固定值。按照取点对称取点对称和缩短率恒定缩短率恒定两条原则，计算出=0.618，因此构造出来的算法就称为0.618法。 1x1x2ab1 1 抛物线法抛物线法利用目标函数f（x）的某些信息，构造一个二次函数（抛物线）（x）作为目标函数的近似，用（x）的极小点代替f（x）的极小点。 这里介绍的三点二次法就是利用目标函数在三个不