运筹学―第六章 非线性规划

非线性规划基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法基本概念非线性规划问题非线性规划方法概述非线性规划问题例1曲线的最优拟合问题已知某物体的温度与时间t之间有如下形式的经验函数关系：tcetcc321(*)其中1c，2c，3c是待定参数。现通过测试获得n组与t之间的实验数据),(iit，i=1，2，…,n。试确定参数1c，2c，3c，使理论曲线(*)尽可能地与n个测试点),(iit拟合。tn1i221)]([min3itciietcc例2构件容积问题设计一个右图所示的由圆锥和圆柱面围成的构件，要求构件的表面积为S，圆锥部分的高和圆柱部分的高x2之比为a。确定构件尺寸，使其容积最大。x1x2x30,02..)3/1(max212121222211221xxSxxxxaxxtsxxaV非线性规划设nTnRxxx),...,(1，RRqjxhpixgxfnji:,...,1),(;,...,1),();(,如下的数学模型称为非线性规划（NLP）：qjxhpixgtsxfji,...,1,0)(,...,1,0)(..)(minqjxhpixgRxXjin,...,1,0)(,...,1,0)(约束集或可行域Xx可行解或可行点向量化表示令Tpxgxgxg))(),...,(()(1Tpxhxhxh))(),...,(()(1，其中，qnpnRRhRRg:,:，那么(NLP)可简记为0)(ming(x)xf或者0)()(minxhxf当p=0,q=0时，称为无约束非线性规划或者无约束最优化问题。否则，称为约束非线性规划或者约束最优化问题。二维问题的图解0301..])4()4min[(22212221xxxtsxx3),(1),(])4()4[(),(2212221211222121xxxgxxxxgxxxxf【例6.3】我们考虑非线性规划问题：目标函数和2个约束条件是：11x2x132R12(4,4)C=3C=5X*图6-1最优解和极小点定义6.1对于非线性规划(NLP)，若Xx*，并且有X),()(*xxfxf则称*x是NLP的整体最优解或整体极小点，称)(*xf是NLP的整体最优值或整体极小值。如果有**),()(xxX,xxfxf则称*x是NLP的严格整体最优解或严格整体极小点，称)(*xf是NLP的严格整体最优值或严格整体极小值。定义6.2对于非线性规划(NLP)，若Xx*，并且存在*x的一个领域),0()(**RxxRxxNn，使XxNxxfxf)(),()(**，则称*x是(MP)的局部最优解或局部极小点，称)(*xf是(MP)的局部最优值或局部极小点。如果有***,)(),()(xxXxNxxfxf，则称*x是(MP)的严格局部最优解或严格局部极小点，称)(*xf是(MP)的严格局部最优值或严格局部极小点。凸函数和凸规划凸函数及其性质凸规划及其性质凸函数的定义若-f是S上的（严格）凸函数，则称f是S上的（严格）凹函数，或f在S上是（严格）凹的。定义6.3设为定义在n维欧氏空间中某凸集S上的函数，若对任何实数(01)以及S中任意两点X(1)和X(2),恒有，则称为定义在S上的凸函数。若对任何实数(01)以及S中任意两点X(1)和X(2),恒有,则称为定义在S上的严格凸函数。)()1()())1(()2()1()2()1(XfXfXXf)(Xf)(Xf)()1()())1(()2()1()2()1(XfXfXXf)(Xf凸函数与凹函数的几何意义xx(1)x(2)x(1)+(1)x(2)f(x(1))f(x(2))f(x(1)+(1)x(2))f(x(1))+(1)f(x(2))(a)凸函数oxf(x)x(2)x(1)+(1)x(2)x(1)of(x(1))f(x(1)+(1)x(2))f(x(1))+(1)f(x(2))f(x(2))(b)凹函数图6—2性质6.1设nRS是非空凸集。（1）若RRfn:是S上的凸函数，0，则f是S上的凸函数；（2）若RRffn:,21都是S上的凸函数，则21ff是S上的凸函数。性质6.2设nRS是非空凸集，RRfn:是凸函数，Rc，则集合cxfSxcfHS)(),(是凸集。凸函数的性质定理6.1设nRS是非空开凸集，RSf:可微，则（1）f是S上的凸函数的充要条件是)()()()(12121xfxfxxxfT，Sxx21,其中Tnxxfxxfxf))(,....,)(()(1111是函数f在点1x处的一阶导数或梯度。（2）f是S上的严格凸函数的充要条件是)()()()(12121xfxfxxxfT，2121,,xxSxx凸函数的判定定理6.2设nRS是非空开凸集，RSf:二阶连续可导，则f是S上的凸函数的充要条件是f的Hesse矩阵)(2xf在S上是半正定的。当)(2xf在S上是正定矩阵时，f是S上的严格凸函数。22221222222122122122122)()()(....)(...)()()(....)()()(nnnnnxxfxxxfxxxfxxxfxxfxxxfxxxfxxxfxxfxf凸函数的判定凸规划及其性质qjxhpixgtsxfji,...10,)((NLP),...,1,0)(..)(minqjxhpixgRxXjin,...,1,0)(,...,1,0)(约束集如果(NLP)的约束集X是凸集，目标函数f是X上的凸函数，则(NLP)叫做非线性凸规划，或简称为凸规划。定理6.3对于非线性规划(NLP)，若pixgi,...,1),(皆为nR上的凸函数，qjxhj,...,1),(皆为线性函数，并且f是X上的凸函数，则NLP是凸规划。定理6.4凸规划的任一局部最优解都是它的整体最优解。若目标函数为严格凸函数，且最优解存在，则其最优解必唯一。凸规划的性质非线性规划方法概述定义4.1.3设0,,,:pRpRxRRfnnn，若存在0，使),0(),()(txftpxf则称向量p是函数f(x)在点x处的下降方向。定义4.1.4设0,,,pRpXxRXnn，若存在0t，使Xtpx则称向量p是函数f(x)在点x处关于X的可行方向。非线性规划基本迭代格式第1步选取初始点0x，k:=0;第2步构造搜索方向kp；第3步根据kp，确定步长kt；第4步令kkkkptxx1，若1kx已满足某种终止条件，停止迭代，输出近似解1kx；否则令k:=k+1，转回第2步。一维搜索方法目标函数为单变量的非线性规划问题称为一维搜索问题(t)min)0(0maxttt其中Rt。精确一维搜索方法0.618法Fibonacci法非精确一维搜索方法Goldstein法Armijo法Fibonacci法我们引进Fibonacci数列的概念。设,3,2,12110nFFFFFnnnn0123456789101112…Fn1123581321345589144233…nnFF1121325385138211334215534895514489233144…表6—41．确定试点个数n。根据事先给定的精度，利用abFn算出nF，然后由Fibonacci法，确定最小的搜索次数n。若给定的是区间缩短的相对精度ababnn11，则利用1nF确定搜索次数n。2．求出最初两个试点的位置。由公式（6-14），可知第一次缩短时的两个试点的位置为：)()()(00101001000201abFFatbaFFbabFFatnnnnnn它们在区间内的位置是对称的（其中bbaa00,）。（6-17）Fibonacci法的步骤3．计算目标函数值)(1tf和)(1tf，并比较其大小。若)(1tf)(1tf，则令121101,,tttbaa，并且令)(111212baFFbtnn；否则，令120111,,ttbbta，并且令)(111212abFFatnn；4．计算目标函数值)(2tf和)(2tf（其中一个已经算出），如第3步那样一步步迭代。计算试点的一般公式为：)()(11111111kkknknkkkkknknkkabFFatbaFFbt（6-18）Fibonacci法的步骤5．当进行到1nk时，由（6-18）经化简可得：)(212211nnnnbatt这样无法比较)(1ntf和)(1ntf的大小以确定最终区间，为此，我们取)(21)(212221221nnnnnnnabatbat其中为任意小的数。这样即可得最终区间11,nnba。在1nt和1nt这两个点中，以函数值较小者为近似极小点，相应的函数值为近似极小值。Fibonacci法的步骤【例6.5】试用Fibonacci法求函数12)(2tttf的近似极小点和近似极小值，其中函数的定义区间为[0，3]，要求搜索精度5.0。解：容易验证，在区间[0，3]上，12)(2tttf为凸函数。已知5.0，由（6-16）式，65.0)03(nF，查表6—1得5n，3,000ba。125.1)30(853)(005401baFFbt875.1)03(850)(005401abFFat765625.0)875.1()(,015625.0)125.1()(11ftfftf，因为)()(11tftf，所以，取125.1,875.1,01211ttba，75.0)875.10(53875.1)(114312baFFbt，0625.0)75.0()(2ftf，因为015625.0)(2tf所以)()(22tftf，取125.1,875.1,75.02322ttba，5.1)75.0875.1(3275.0)(223223abFFat，25.0)5.1()(3ftf，因为015625.0)(3tf所以)()(33tftf，取,5.1,75.033ba125.134tt取1.0，则05.1)5.175.0(6.05.1)(1.0213334babt，0025.0)05.1()(4ftf，因为015625.0)(4tf所以)()(44tftf，取,125.1,75.044ba则05.14t为近似最小点（精确解为1t）近似极小值为0025.0)05.1(f（精确值为0)1(f）。缩短后的区间长度为5.0375.075.0125.10.618法（近似黄金分割法）第1步确定单谷区间[a,b]，给定最后区间的相对精度〉0;第2步计算最初两个试点，令k:=1,)(382.00001abat)(618.00001abat第3步比较)(ktf和)(ktf的大小：第一种情况：若)(ktf)(ktf，则令,,1kkkktbaa并判断精度，若00ababkk，则停止计算，可取)(211kkkba