第九章非线性规划

11.非线性规划我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年H.W.库恩和A.W.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。1.1非线性规划举例[库存管理问题]考虑首都名酒专卖商店关于啤酒库存的年管理策略。假设该商店啤酒的年销售量为A箱,每箱啤酒的平均库存成本为H元,每次订货成本都为F元。如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。我们以Q表示每次定货数量,那么年定货次数可以为QA,年订货成本为QAF。由于平均库存量为2Q,所以,年持有成本为2QH,年库存成本可以表示为:QHQAFQC2)(将它表示为数学规划问题:minQHQAFQC2)(..ts0Q其中Q为决策变量,因为目标函数是非线性的,约束条件是非负约束,所以这是带约束条件的非线性规划问题。[数据拟合问题]假设一年期国债利率在市场中的波动符合下述模型2332211nnnnRRRR其中nR表示一年期国债利率在周期n开始时的利率,误差服从),0(2N。利率的历史观察数据为:表1.9:一年期国债利率历史样本数据123456789101112134.284.143.854.074.184.664.514.544.594.484.474.474.72利用最小二乘法估算3,2,1,ii由于在周期t回归误差的平方为23322112)(tttttRRRRe,Nt,...5,4比如说,当4t时,232124)28.414.485.307.4(e总回归误差为Nttee422我们需要求解下述数学规划问题:minNtttttRRRRe423322112)(..ts3,2,1),,(ii其中i3,2,1,i为决策变量,显然,这是无约束非线性规划问题。[投资组合管理问题]假设首都基金管理公司拥有大批量股票S,并且希望在未来的N天中将其全部卖出。股票S在未来N天的总期望价值为:NtttqpSV1)(其中,Ntqt,...,2,1,是基金公司在第t日卖出股票S的数量,Ntpt,...,2,1,是在t日股票S的平均价格。同时,我们假设价格tp具有下述动态特性:Ntqppttt,...,2,1,1那么基金管理公司应当如何确定股票S每日卖出数量?很显然,不同的卖出方案,基金管理公司获得的收益是不同的。所以目标函数是最大化股票S的总期望价值。约束条件为N日内卖出数量之和应当等于总持有量S,价格动态特征,3以及每日卖出数量大于等于零。我们可以把它表示为最优化问题:maxNtttqpSV1)(..tsNtqNtqppSqttttNtt,...,2,1,0,...,3,2,11其中tq,Nt,...,2,1,这是目标函数为非线性函数,约束条件是线性等式约束条件的非线性规划问题。[生产管理问题]首都电器制造厂生产二款电视机,A和B。已知电视机A每月最大的销售量为500台,电视机B每月的最大销售量为400台。工厂采用随销售量增加而递减销售价格的定价方式对电视机进行定价,那么单台电视机的利润是随着销售量的增加而递减。我们分别以AX和BX表示电视机A和B的月销售量,那么电视机A的销售收入可以表示为:2)500150(300AAXX它说明第一部A型电视机的利润为300元,最后一部(第500)A型电视机的利润为150元。电视机B的销售收入可以表示为:2)400100(200BBXX电视机的生产受到下下述条件限制:)1(装配工时限制:每月最多可供使用的工时是1200小时,而装配一台电视机A需要2工时,装配一台电视机B需要1工时。)2(机器加工能力限制:每日最多可供使用的机时是1350小时,加工一台电视机A需要1机时,加工一台电视机B需要3机时。那么,如何决定每种电视机的月产量,使月销售收入最大。如果我们以二款电视机的月销售收入之和作为目标函数,则电视机生产管理的最优化问题被表示为:max2225.02003.0300BBAAXXXXS4..ts0,4005001350312002BABABABAXXXXXXXX这是目标函数为二次可分离函数,约束条件为线性不等式的非线性规划问题。1.2非线性规划模型现在,我们非线性规划问题的应用进行归纳,建立非线性规划通用数学模型。非线性规划的数学模型可表示为:)(minxfXx)1.1(其中:RRfn:是具有n个自变量的连续(通常存在一阶导数)函数;nRX,是nR的子集合。通常称X为非线性规划问题)1.1(的可行域,如果nRX,则非线性规划问题)1.1(就变为无约束条件的非线性规划问题;如果nRX,则非线性规划问题)1.1(为带约束非线性规划问题。如果点Xx,则称x为可行点。称)(xf为非线性规划问题)1.1(的目标函数,使)(xf在可行域X上达到最小值的点*x为最优解(极小点),对应的目标函数值)(*xf为最优值(极小值)。如果)(xf是线性函数并且X是n维空间中的单纯形,非线性规划)1.1(就变成了线性规划问题。我们通常将非线性规划和线性规划区别对待,非线性规划的求解方法比线性规划复杂许多。为了方便讨论,我们定义带约束条件的非线性规划的标准模型如下:min)(xf..ts.,...,2,1,0)(,...,2,1,0)(sjxgmixhji)2.1(其中:RRhni:和RRgnj:都是连续,可导函数。第一组约束,mixhi,...,2,1),(称为等式约束;第二组约束,sjxgj,...,2,1),(称为不等式约束。非线性规划模型)2.1(的可行域可以表示为:},...,2,1,0)(,,...,2,1,0)(|{sjxgmixhRxXjin∶不难看出,带约束非线性规划模型)2.1(的可行域是nR的子集合,所以它也是非线性规划模型5)1.1(的一个特例。我们将根据非线性规划的标准模型)1.1(,给出非线性规划解的定义。[定义1.1]设Xx*,nRX,RRfn:)1(如果Xx*,并且存在*x的邻域}0,||:||{)(**xxRxxNn使得:)()(*xfxf)(*xNXx则*x是非线性规划)1.1(的局部最优解或局部极小点,称)(*xf是非线性规划)1.1(的局部最优值或局部极小值。)2(如果Xx*,并且存在*x的邻域}0,||:||{)(**xxRxxNn使得:)()(*xfxf}{))((**x＼xNXx则*x是非线性规划)1.1(的严格局部最优解或严格局部极小点,称)(*xf是非线性规划)1.1(的严格局部最优值或严格局部极小值。[定义1.2]设Xx*,nRX,RRfn:)1(如果Xx*,使得:)()(*xfxfXx,则*x是非线性规划)1.1(的全局最优解或全局极小点,称)(*xf是非线性规划)1.1(的全局最优值或全局极小值。)2(如果Xx*,使得:)()(*xfxfXx,则*x是非线性规划)1.1(的严格全局最优解或严格全局极小点,称)(*xf是非线性规划)1.1(的严格全局最优值或严格全局极小值。图)1.1(从几何上说明了局部极小点,严格局部极小点,和严格全局极小点之间的关系。)(xf6严格局部极小点局部极小点严格全局极小点图)1.1(可以看出,对于非线性规划)1.1(,局部或严格局部极小点不是全局或严格全局极小点,反之全局或严格全局极小点一定是局部或严格局部极小点。对于只有两个决策变量的非线性规划问题,我们可以通过图解法进行求解。考虑下述带等式约束的非线性规划问题:min21)(xxxf..ts022221xx)3.1(其可行域X是以原点为中心,半径等于2的圆周长上的所有点,见图)2.1(:2x221x图)2.1(显然,由于非线性规划)3.1(的目标函数是直线,与可行域X的最小相交点为)1,1(*x,它是非线性规划)3.1(的全局最优解,全局最优值为2)(*xf。再考虑下述带等式约束的非线性规划问题:7max21)(xxxf..ts221xx)4.1(显然,非线性规划)4.1(的可行域X是连接点)0,2(和点)2,0(直线上的所有点,参见图)3.1(:2x221x图)3.1(非线性规划)4.1(的目标函数与可行域X的交点为)1,1(*x,它是非线性规划)4.1(的全局最优解,全局最优值为1)(*xf。1.3凸集和凸函数凸集合,以及凸,凹函数在非线性规划的研究中具有特别重要的作用.[定义1.3]设nRS,如果Syx,,并且有:Syx)1(10则称S为凸集。图)4.1(给出了凸集和非凸集的例子.8凸集非凸集图)4.1(不难看出,凸集的几何意义为,如果点Syx,,那么连接点x和y的线段也属于S,即Syx],[。[定义1.4]函数RRxfn:)(,如果nRyx,,都有:)()()1())1((yfxfyxf10则称)(xf为凸函数。如果)(xf是凸函数,则称)(xf为凹函数。)(a凸函数)(b凹函数9)(c非凸,凹函数图)5.1(对于凸函数,)(zf的取值位于连接)(xf和)(yf连线的下方,见图)5.1(的)(a;对于凹函数,)(zf的取值位于连接)(xf和)(yf连线的上方,见图)5.1(的)(b。凸(凹)函数具有以下性质:[定理1.1]设nRC是凸集,niRCxfi,...,2,1,:)(是凸(凹)函数)1(对于nii,...,2,1,0,函数niiixfxf1)()(也是凸(凹)函数。)2(如果nixfi,...,2,1),(是凸函数,则)}({max)(1xfxfini一定是凸函数;如果nixfi,...,2,1),(是凹函数,则)}({min)(1xfxfini一定是凹函数。证明我们只证明)2(的第一部分。对于任意Cxxxn,...,,21,我们有:niiiniiiiniiiiniiixfxfxfxf1111)()()()(,ni,...,2,1那么)(xf是凸函数,证毕。[定义1.5]函数RRxfn:)(,如果)(xf是连续函数,且存在一阶偏导数,则称向量Tnxxfxxfxxfxf))(,...,)(,)(()(21为)(xf在点x处的一阶偏导数或梯度。[定理1.2]设函数RRxfn:)(在凸集nRX上一阶可微)1()(xf是凸函数的充分必要条件是Xyx,:)()()()(xyxfxfyf