第4章 非线性规划01-基本概念与凸规划

非线性规划NonlinearProgrammingLudongUniversity2020/2/26LudongUniversity2第四章非线性规划由前几章知道，线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。有些实际问题可以表达成线性规划问题，但有些实际问题则需要用非线性规划的模型来表达，借助于非线性规划解法来求解。GlobalminimumLocalminimumxf(x)02020/2/26LudongUniversity3第四章非线性规划基本概念凸函数和凸规划一维搜索方法无约束最优化方法约束最优化方法2020/2/26LudongUniversity4基本概念非线性规划问题非线性规划方法概述2020/2/26LudongUniversity5Example1(a2,b2)(a1,b1)(a3,b3)(x,y)(a2,b2)(a1,b1)(a3,b3)(x,y)(a1,b1)(a3,b3)(x,y)Threecustomerswithknownlocationsonaplanedescribedbycoordinates(ai,bi),i=1,2,3.Problem:Tofindalocationforadepotsothatthetotaldistancetothethreecustomersisminimized.Variable:(x,y)thecoordinatesofthedepotModel:3122)()(),(miniiibyaxyxfUnconstrained2020/2/26LudongUniversity6Example2Usingtheminimummaterialtomakeabox.ThevolumeoftheboxhastobeV=1000.Decision:Boxlength:x,width:y,height:z.Objective:Tominimizesurfaceareaofthebox.Model:min(,,)222s.t,,0fxyzxyxzyzxyzVxyzConstrained2020/2/26LudongUniversity7数学规划设1(,,)TnnxxxR，();(),1,,;(),1,,;nijfxgxiphxjqRR,如下的数学模型称为数学规划(MathematicalProgramming,MP)：min()..()0,1,,,()0,1,,.ijfxstgxiphxjq()0,1,,()0,1,,injgxipXxRhxjq其中约束集或可行域xXMP的可行解或可行点2020/2/26LudongUniversity8向量化表示令1()((),,())Tpgxgxgx，1()((),,())Tqhxhxhx，其中:,:npnqgRRhRR，那么(MP)可简记为min()..0,()0.fxstg(x)hx或者min()xXfx。当p=0，q=0时，称为无约束非线性规划或无约束最优化问题。否则称为约束非线性规划或约束最优化问题。2020/2/26LudongUniversity9最优解和极小点定义4.1.1对于非线性规划(MP)，若Xx*，并且有*()(),X,fxfxx则称*x是(MP)的整体最优解或整体极小点，称*()fx是(MP)的整体最优值或整体极小值。如果有**()(),,fxfxxX,xx则称*x是(MP)的严格整体最优解或严格整体极小点，称*()fx是(MP)的严格整体最优值或严格整体极小值。定义4.1.2对于非线性规划(MP)，若Xx*，并且存在*x的一个领域**()(0,)nNxxRxxR，使**()(),()fxfxxNxX，则称*x是(MP)的局部最优解或局部极小点，称*()fx是(MP)的局部最优值或局部极小点。如果有***()(),(),fxfxxNxXxx，则称*x是(MP)的严格局部最优解或严格局部极小点，称*()fx是(MP)的严格局部最优值或严格局部极小点。2020/2/26LudongUniversity10最优解的几何位置x1x2*x2212121212min,..10,10,10.fxxxxstxxxx2020/2/26LudongUniversity11非线性规划方法概述定义4.1.3设:,,,0nnnfRRxRpRp，若存在0，使()(),(0,)fxtpfxt，则称向量p是函数fx在点x处的下降方向。定义4.1.4设,,,0nnXRxXpRp，若存在0t，使,xtpX则称向量p是函数fx在点x处关于X的可行方向。选取初始点0x，构造搜索方向kp，确定步长kt，令1kkkkxxtp。若1kx满足某种终止条件，停止，输出近似解1kx。2020/2/26LudongUniversity12非线性规划基本跌代格式第1步选取初始点0x，0k；第2步构造搜索方向kp；第3步根据kp，确定步长kt；第4步令1kkkkxxtp。若1kx已满足某种终止条件，停止迭代，输出近似解1kx；否则令1kk，转回第2步。2020/2/26LudongUniversity13凸函数与凸规划凸函数及其性质凸规划及其性质2020/2/26LudongUniversity14ConvexSetx1x2x1x2ConvexsetsNon-convexsetx1x2x1x2ConvexsetsNon-convexset2020/2/26LudongUniversity15凸函数及其性质定义4.2.1设nSR是非空凸集，:fSR，如果对任意的(0,1)有1212((1))()(1)()fxxfxfx，12,,xxS则称f是S上的凸函数，或f在S上是凸的。如果对于任意的(0,1)有1212((1))()(1)()fxxfxfx，12,xx则称f是S上的严格凸函数，或f在S上是严格凸的。注：（1）若f是S上的（严格）凸函数，则称f是S上的（严格）凹函数，或f在S上是（严格）凹的。（2）线性函数,,,TnfxaxbaxRbR在nR上既是凸函数也是凹函数。xf(x)x1x2ax1+(1-a)x2f(αx1+(1-α)x2)αf(x1)+(1-α)f(x2)xf(x)x1x2ax1+(1-a)x2f(αx1+(1-α)x2)αf(x1)+(1-α)f(x2)2020/2/26LudongUniversity16凸函数及其性质定理4.2.1设nSR是非空凸集。（1）若:nfRR是S上的凸函数，0，则f是S上的凸函数；（2）若12,:nffRR都是S上的凸函数，则12ff是S上的凸函数。定理4.2.2设nSR是非空凸集，:fSR是凸函数，cR，则集合(,)()SHfcxSfxc是凸集。注：两个凸函数的乘积不一定是凸函数。注：一般地定理4.2.2的逆定理不成立。称集合,SHfc为函数f在集合S上关于数c的水平集。2020/2/26LudongUniversity17凸函数及其性质定理4.2.3设nSR是非空开凸集，:fSR可微，则（1）f是S上的凸函数的充要条件是12121()()()()Tfxxxfxfx，12,,xxS其中1111()()()(,,)Tnfxfxfxxx是函数f在点1x处的一阶导数或梯度。（2）f是S上的严格凸函数的充要条件是12121()()()(),Tfxxxfxfx1212,,.xxSxx121fxxxxf(x)1x2x2020/2/26LudongUniversity18凸函数及其性质定理4.2.4设nSR是非空开凸集，:fSR二阶连续可导，则f是S上的凸函数的充要条件是f的Hesse矩阵2()fx在S上是半正定的。当2()fx在S上是正定矩阵时，f是S上的严格凸函数。22221121222221222222212()()()()()()()()()()nnnnnfxfxfxxxxxxfxfxfxxxxxxfxfxfxfxxxxxx注：该逆命题不成立。2020/2/26LudongUniversity19凸规划及其性质min()..()0,1,,,(MP)()0,1,,.ijfxstgxiphxjq  ()0,1,,()0,1,,injgxipXxRhxjq其中约束集如果(MP)的约束集X是凸集，目标函数f是X上的凸函数，则(MP)叫做非线性凸规划，或简称为凸规划。2020/2/26LudongUniversity20凸规划及其性质定理4.2.5对于非线性规划(MP)，若(),1,,igxip皆为nR上的凸函数，(),1,,jhxjq皆为线性函数，并且f是X上的凸函数，则(MP)是凸规划。定理4.2.6凸规划的任一局部最优解都是它的整体最优解。min()..()0,1,,,(MP)()0,1,,.ijfxstgxiphxjq  ()0,1,,()0,1,,injgxipXxRhxjq其中2020/2/26LudongUniversity21思考题和练习题思考题：习题3，6（P.151）练习题：习题7，8（P.151）