第九章非线性规划

1、1 .非线性规划我们讨论过线性规划，其目标函数和约束条件都是自变量的线性函数。如果目标函数是 非线性函数或至少有一个约束条件是非线性等式（不等式），则这一类数学规划就称为非线性规划。在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计，管理科学，风险管理，系统控制，求解均衡模型，以及数据拟合等领域得到越 来越广泛的应用。非线性规划的研究始于三十年代末 ，是由W卡鲁什首次进行的，40年代后期进入系统研 究，1951年H.W.库恩和A.W.塔克提出带约束条件非线性规划最优化的判别条

2、件，从而奠定了非线性规划的理论基础，后来在理论研究和实用算法方面都有很大的发展。非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。无约束问题的求解方法有最陡下降法、共轲梯度法、变尺度法和鲍威尔直接法等。 关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。 总的原则是设法将约束问题化为无约束问题； 把非线性问题化为线性问题从而使复杂问题简单化。求解方法有可行方向法、 约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。虽然这些方法都有较好的效果，但 是尚未找到可以用于解决所有非线性

3、规划的统一算法。1.1 非线性规划举例库存管理问题考虑首都名酒专卖商店关于啤酒库存的年管理策略。假设该商店啤酒的年销售量为 A箱，每箱啤酒的平均库存成本为H元，每次订货成本都为 F元。如果补货方式是可以在瞬间完成的，那么为了降低年库存管理费用，商店必须决定每年需要定多少次货 以及每次订货量。 A A我们以Q表示每次定货数量，那么年定货次数可以为二，年订货成本为F 由于平QQ均库存量为 Q,所以，年持有成本为H2一,年库存成本可以表不为2精品A HC(Q) F - - QQ 2将它表示为数学规划问题 A H八min C(Q) FQQ 2st.Q 0其中Q为决策变量，因为目标函数是非线性的约束条件

4、是非负约束，所以这是带约束条件的非线性规划问题。数据拟合问题假设一年期国债利率在市场中的波动符合下述模型RniRn 12Rn 23& 3其中Rn表示一年期国债利率在周期n开始时的利率，误差 服从N(0, 2)。利率的历史观察数据为：表9.1： 一年期国债利率历史样本数据123456789101112134.284.143.854.074.184.664.514.544.594.484.474.474.72利用最小二乘法估算i,i 1,2,3由于在周期t回归误差的平方为et2比如说，当t 4时，e2(4.07总回归误差为2e我们需要求解下述数学规划问题-2min e(Rt3.85N2et

5、t 4iRti2K 23Rt3)2,t 4,5,.n2i 4.14 24.28 3)N(Rt1Rt12Rt 23Rt 3)t 4st.i (,),i 1,2,3其中i ,i1,2,3为决策变量，显然，这是无约束非线性规划问题。投资组合管理问题假设首都基金管理公司拥有大批量股票S ,并且希望在未来的N天中将其全部卖出。股票S在未来N天的总期望价值为：NV(S) Ptqt t 1其中，qt,t 1,2,., N是基金公司在第t日卖出股票 S的数量，pt,t1,2,.,N是在t日股票S的平均价格。同时，我们假设价格pt具有下述动态特性：PtPt 1 qt,t 1,2,., N那么基金管理公司应当如何

6、确定股票S每日卖出数量？很显然，不同的卖出方案，基金管理公司获得的收益是不同的。所以目标函数是最大化股票S的总期望价值。约束条件为 N日内卖出数量之和应当等于总持有量S，价格动态特征，以及每日卖出数量大于等于零精品我们可以把它表示为最优化问题Nmax V(S) ptqt t 1N qtSt 1s.t. PtPt 1qt,t2,3，,Nqt 0,t1,2,，N其中qt, t 1,2,., N ,这是目标函数为非线性函数，约束条件是线性等式约束条件的非线性 规划问题。生产管理问题首都电器制造厂生产二款电视机，人和8。已知电视机 A每月最大的销售量为500台，电视机B每月的最大销售量为 400台。工

7、厂采用随销售量增加而递减销售 价格的定价方式对电视机进行定价，那么单台电视机的利润是随着销售量的增加而递减。我们分别以Xa和Xb表示电视机 A和B的月销售量，那么电视机 A的销售收入可以表 示为：300 Xa (150 500) X A它说明第一部 A型电视机的利润为 300元，最后一部(第500) A型电视机的利润为150元。 电视机B的销售收入可以表示为：200Xb (100 400)X2电视机的生产受到下下述条件限制：(1)装配工日限制：每月最多可供使用的工时是1200小时,而装配一台电视机 A需要2工时，装配一台电视机 B需要1工时。(2)机器加工能力限制：每日最多可供使用的机时是13

8、50小时，加工一台电视机 A需要1机时，加工一台电视机 B需要3机时。那么，如何决定每种电视机的月产量 ，使月销售收入最大。如果我们以二款电视机的月销售收入之和作为目标函数,则电视机生产管理的最优化问精品题被表不为max S 300Xa 0.3XA200XB 0.25X22Xa XB 1200Xa 3XB 1350stXa 500XB 400Xa,XB 0这是目标函数为二次可分离函数，约束条件为线性不等式的非线性规划问题。1.2 非线性规划模型现在,我们非线性规划问题的应用进行归纳，建立非线性规划通用数学模型。非线性规划的数学模型可表示为：min f(x)(1.1)x X其中：f：RnR是具有

9、n个自变量的连续(通常存在一阶导数)函数；X Rn,是Rn的子集合。通常称X为非线性规划问题(1.1)的可行域，如果XRn,则非线性规划问题(1.1)就变为无约束条件的非线性规划问题；如果X Rn,则非线性规划问题(1.1)为带约束非线性规划问题。如果点X X，则称X为可行点。称f(x)为非线性规划问题(1.1)的目标函数，使f (x)*在可彳T域X上达到最小值的点x为最优解(极小点),对应的目标函数值f(x )为最优值(极小值)。如果f (x)是线性函数并且 X是n维空间中的单纯形，非线性规划(1.1)就变成了线性规划问题。我们通常将非线性规划和线性规划区别对待，非线性规划的求解方法比线性规

10、划复杂许多。为了方便讨论，我们定义带约束条件的非线性规划的标准模型如下：min f (x)hi(x) 0,i 1,2,.,ms.t.(1.2)gj(x) 0, j 1,2.s其中：1Rn R和gj:RnR都是连续，可导函数。第一组约束，hi(x),i1,2,.,m称为等式约束；第二组约束，g j (x), j 1,2,., s称为不等式约束。非线性规划模型(1.2)的可行域可以表示为：X： x Rn|hi(x) 0,i 1,2,.,m,gj(x) 0, j 1,2,.,s不难看出，带约束非线性规划模型(1.2)的可行域是Rn的子集合，所以它也是非线性规划模(1.1)的一个特例。我们将根据非线性

11、规划的标准模型(1.1),给出非线性规划解的定义。定义1.1 设xX , X Rn, f : Rn R. .一 *(1)如果xX ,并且存在x的邻域N (x )_ n*x R ：|x x |0使得:* .f(x ) f(x)*x X N(x )I*则x是非线性规划(1.1)的局部最优解或局部极小点_ * ，称f (x )是非线性规划(1.1)的局部最优值或局部极小值。 .一 *(2)如果xX，并且存在X的邻域N(x )x Rn:|x x |0使得:*f(x ) f(x)x (X* _ * _N(x Mx I* . 则x是非线性规划(1.1)的严格局部最优解或严格局部极小点. *，称 f (x)

12、是非线性规划(1.1)的严格局部最优值或严格局部极小值。定义1.2 设xX , X Rn, f : Rn R. .一 *(1)如果xX,使得：f(x) f (x) x X,则 x是非线性规划(1.1)的全局最优解或全局极小点一， ， * 、 . . .，称f (x )是非线性规划(1.1)的全局最优值或全局极小值。 .一 *(2)如果x，r .， * 、， 、_ _*X ,使得：f (x ) f (x) x X ,则x是非线性规划(1.1)的严格全局最优解或严格全局极小点，称f (x )是非线性规划(1.1)的严格全局最优值或严格全局极小值。图(1.1)可以看出，对于非线性规划(1.1),局部

13、或严格局部极小点不是全局或严格全局极小点反之全局或严格全局极小点一定是局部或严格局部极小点。对于只有两个决策变量的非线性规划问题，我们可以通过图解法进行求解。考虑下述带等式约束的非线性规划问题：min f(x) x1x222_-s.t. X1X22 0(1.3)其可行域X是以原点为中心，半径等于J2的圆周长上的所有点，见图(1.2):图(1.2)显然，由于非线性规划(1.3)的目标函数是直线，与可行域X的最小相交点为* _ *x ( 1, 1),它是非线性规划(1.3)的全局最优解，全局最优值为f(x )2。再考虑下述带等式约束的非线性规划问题max f(x)x1x2s.t. xix22(1.

14、4)显然,非线性规划(1.4)的可行域 X是连接点(2,0)和点(0,2)直线上的所有点,参见图(1.3)：图(1.3) * .非线性规划(1.4)的目标函数与可行域X的交点为x (1,1)，它是非线性规划(1.4)的 *全局最优解，全局最优值为f (x ) 1。1.3凸集和凸函数凸集合，以及凸，凹函数在非线性规划的研究中具有特别重要的作用定义1.3 设SRn,如果 x, y S,并且有：(1 )x y S 01则称S为凸集。图(1.4)给出了凸集和非凸集的例子.精品不难看出x, y S。定义1.4凸集图(1.4),凸集的几何意义为函数 f (x)： RnR,如果f(1 )xy) (1则称f

15、(x)为凸函数。如果 f(x)是凸函数，则称x, y S ,那么连接点x和y的线段也属于x, y Rn,都有:)f(x) f(y) 0f(x)为凹函数。S,即(b)凹函数精品(c)非凸，凹函数图(1.5)对于凸函数，f(z)的取值位于连接f(x)和f(y)连线的下方，见图(1.5)的(a)；对于凹 函数，f(z)的取值位于连接f(x)和f(y)连线的上方，见图(1.5)的(b)。凸(凹)函数具有以下性质：定理1.1 设C Rn是凸集，fi(x):C R,i 1,2,，n是凸(凹)函数n(1)对于i 0,i1,2,n,函数f(x) ifi(x)也是凸(凹)函数。i 1(2)如果fi(x),i 1

16、,2，n是凸函数，则f(x) max fi (x)一定是凸函数；如 1 i n果fi (x),i1,2,，n是凹函数，则f (x)m” fi (x) 一定是凹函数。证明 我们只证明(2)的第一部分。对于任意 x1, x2,，xnC ,我们有：nnnnf( ixi)fi(ixi) ifi(xi) if(xi), i 1,2,ni 1i 1i 1i 1那么f (x)是凸函数，证毕。f(x)Txn定义1.5 函数f(x):Rn R,如果f(x)是连续函数，且存在一阶偏导数，则称向量f(x)f(x) f(x),Xix2为f (x)在点x处的一阶偏导数或梯度。定理1.2 设函数f(x):RnR在凸集XR

17、n上一阶可微(1) f(x)是凸函数的充分必要条件是x, y X :f(y) f(x)f(x)T(y x)(2) f (x)是凹函数的充分必要条件是x, y X :f (y) f (x)f (x)T(y x)定理1.2是判断可微函数f (x)是否为凸(凹)函数的一个判别定理。 从几何上来说，函 数f (x)是凸函数的充分必要条件是 f (x)在图形上任一点处的切线都在曲线的下方，见图(1.6)。定理1.3(1)设f (x) ： RnR是凸函数，x是局部极小点，那么x 一定是全局极小n点。(2) f (x) ： RR是凹函数，x是局部极大点，那么x 一定是全局极大点。 、. . . . . .一

18、 * 证明我们只证明f(x)为凸函数的情况(1)。如果x不是全局极小点，则存在x使得_ _ _ * . . .f(x) f(x)。根据凸函数性质，对于所有(0,1),_ * _ * _ _ *f( x (1)x) f(x ) (1)f(x) f(x )这表明在x和x的连线上的点，其取值严格小于f(x )，所以x不可能是局部极小点。(2) 证明过程与(1)类似，请大家自己完成，证毕。定义1.6 函数f(x)：RnR,如果f(x)存在二阶偏导数，则称矩阵2f(x)2f(x)2f(x)2-XiXi X2Xi Xn22 f (X)2f (X)2 f (X)f (x)X2 X1X；X2 Xn2 f (X

19、)2f (X)2 f (X)2Xn XiXn X2Xn为f (X)在点X处的二阶偏导数矩阵，通常称其为Hessian矩阵。定理1.4 设f(x)： RnR是在凸集XRn上二阶可微(1) f(x)是凸函数的充分必要条件是 定的。(2) f (X)是凹函数的充分必要条件是 定的。f(x)的二阶Hessian矩阵 2 f (x)是半正f(x)的二阶Hessian矩阵 2 f (x)是半负例i.i判断下述函数的凸凹性(1) f(x)eX, x R(2) f(x)x12, X R(3) f (Xi,X2)2X1222x2 X1x2 , x R''X解：(i) f (x) e 0,所以f(

20、x)函数是凸集R上的的凸函数.i 3 2(2) f (x)-X 30,所以f(x)函数是凸集R上的的凹函数4(3) f(,X2)的 Hessian 矩阵为：2f(x)为了判断2 f(x)的半正(负)定性，计算:2def( 2f (x)2I) def 0(2)20那么，i 22,所以矩阵 2 f (x)为负定矩阵，f(x)为凸集R上的凹函数下面的定理说明了凸, 凹函数与凸集, 及凸集与凸集之间的关系. 定理 1.5如果f(x):Rn R是凸函数，对于任何c R,集合Lc x:f(x) c是凸集。(2) 如果 f (x) : R nR 是凹函数, 对于任何c R, 集合Lcx : f (x) c

21、是凸集。(3) 如果 Ci ,i 1,2,., n 是凸集 , 那么 C Ci 也是凸集。证 明 我 们 只 证 明(1)。 如 果f(x) 是凸函 数 , 对于 任 意 x1,x2Lc, 有f(Xi) c, f(X2) c。这表明：f( x1(1 )x2)f(x1)(1 )f(x2)c所以(Xi (1)X2) L ,根据Xi,X2的任意性，Lc是凸集，证毕。如果非线性规划问题的目标函数为凸或凹函数, 约束条件的可行集为凸集, 则这类非线性规划称为凸规划。定义1.7 设f(X): C R是凸函数，CRn是凸集，考虑下述两类非线性规划问题min f(X)maX - f(X)s.t. X Cs.t

22、. X C那么 , 它们都是凸规划问题。接下来 , 考虑带约束条件的非线性规划模型:min f(X)(1.5)hi (X)0,i 1,2,., mIgj (X) 0, j 1,2,.,s非线性规划模型(1.5) 是凸规划的必要条件为(1) f(X):CR是凸函数(2)几：Rn R, i 1,2,., m都是线性函数(3) gj : RnR, j1,2,., s都是凸函数。1.4 非线性规划应用非线性规划模型在许多领域中都获得广泛应用, 在本节中, 我们将介绍非线性规划在生产管理 , 金融投资方面的应用.1.4.1 选址问题首都电视机厂的产品在 n个城市中销售。为了提供优质服务，现在打算建立服务

23、中心设第i个城市的地址坐标为（xi, yi）, i希望选择地址的位置使所有城市到服务中心的距离最短。以坐标（a,b）表示服务中心的位置1,2,.,n ,该问题等价于找到能够覆盖所有城市半径最小的园，其几何意义见下图数学规划模型为这是非线性规划问题。1.4.2投资组合管理图(1.7)min r22(x a)(yib) r,i1,2,.,ns.t.r 0n设Xi,i 1,2,.,n为持有第i种证券品种的比例，满足 1, ri,i 1,2,., n为第i i 1种证券品种的收益率为投资组合的收益率,Q为证券品种的方差-协方差矩阵，等于:qn加qmQq21q22q2nqmqn2qnn数学规划模型为：m

24、inqjXiXjri Xi 1nstxi1i 1x 0,i 1,2,n这是目标函数为二次函数，约束条件为线性函数的非线性规划问题。1.4.3指数化投资指数化投资是根据目标指数中的成份证券的权重创建跟踪投资组合的投资方法。设为预算投资额，Xi,i 1,2,.,n为投资在第i种证券品种的投资额，那么：nxi Bi 1设初始投资组合为xi00,i1,2,.,n , C为现金，则：nB Cx0i 1 nn设F (xi, xi0)为从初始投资组合x0到投资组合xi的交易成本，所以：i 1i 1nxiBF(xi,x0)i 1设投资组合与目标指数的跟踪误差为：E .J- S)2 I t 1其中rt是跟踪组合

25、的收益率，%为目标指数的收益率。它们的计算方法是根据过去一个阶段 的历史指数点位和成份证券价格：stln(IJIt1)n yi,trtln(HnJ)yi,t 1 i 1yi,t R,t (xi / Pi,T )其中11是指数的价格,P,t是第i种证券在时刻t的价格。xi/PiT是第i种证券的数量。指数化投资中最小化跟踪误差的数学规划模型为：1 T /、2min E(rtst)T . t inXi B F(Xi,x0)st. i ixi 0,i1,2,., n1.5无约束优化问题考虑无约束的非线性规划问题：min f (x)(1.6)x Rn一般来说，求解无约束非线性规划问题(1.6)将涉及到以

26、下三个方面，首先，确定极小点xRn必须满足的条件，其次设计某种迭代算法来搜寻极小点x,最后，求解的最终目标一般是求全局极小点，而极小点x满足的必要条件只能保证它是局部极小点，所以需要找出局部极小点也是全局极小点的条件。1.5.1 无约束优化问题的最优性条件如果f(x):RR是二次可微的一元函数，设x0R,对于接近x0的所有x,有：f (x) f (Xo) f (x0)(x Xo)f (Xo )(x Xo)显然，极值点存在的条件为：(1)必要条件：f (Xo)0'''(2)充分条件：如果f(Xo)0且f(Xo)0, Xo为极小点；如果f(Xo)0且''f

27、(Xo) 0 , Xo为极大点。设f (x) ： RnR为二次可微的多元函数，极值点存在的条件为：定理1.6(一阶，二阶必要条件)n(1) 一阶必要条件：对于点X R ,如果x是f(x)的局部极值点，则f (X ) 0。(2)二阶必要条件：对于点x*Rn,如果x*是f(x)的局部极值点，则2 f (x*)为半正定矩阵证明假设x为局部极小值点，我们先证明条件(1)。对于向量D Rn和 0, f(x)在点D处的一阶泰勒展开式为：* Tf(x D) f(x ) f (x ) ( D)或:DT f(x*) limf(x D) f(x)00D Rn替换D Rn,获得:DTf(x*) limf(x D)

28、f(x) 00综合上述结果，有:_ T _*_DT f (x ) 0DRn由D的任意性，所以:_ *f(x ) 0我们再证明条件(2) 。 f (x)在点xD处的二阶泰勒展开式为_*_*_* Tf(x D) f (x ) f (x ) D2-DT 2_ *f (x )D o(一、， ， *、 因为f(x ) 0,上式可以表示为：*f(x D) f(x )22 -* _f(x )Do()2*由于x是局部极小值，一定存在足够小的使得(0,)：_ * _ *f(x D) f(x) 020所以，当0, DT 2f (x*)D0,这说明2f(x)为半正定矩阵，证毕。我们必须注意到满足一阶和二阶必要条件的

29、点不定是极值点,考虑单变量函数3*f (x) x ,在原点x0处有：f (x ) 0,和f (x ) 0,但是x一30即不是f(x) x的极小点也不是极大点定理1.7(充分条件)设函数f(x)： Rn一*n 一一.* ._R在x Rn处二阶可微，若f(x)满足 f(x ) 0并且f (x )为正定矩阵，则x是f (x)的局部极小值。、一 II、1 , * 、* . .* ，证明 设N(x )为点x的邻域，对于d N(x ),根据二阶泰勒展开式f(x* d) f (x*) f(x*)Td ；dT 2 f (x*)d o(|d|2)、一一.»。.*、丁。_*2设 0为2f(x)的最小特征

30、值，dT 2f(x )d |d| ,则：_ *f(x d)_ *f(x )o(2 一(|d|2)d2如果|d|足够小，相对于-,我们可忽略需，那么由刑0,有_ * _ *f(x d) f(x ) 0、 r*_ .所以，x是f (x)的局部极小值，证毕。1 o o的取值范围对例1.2分析函数f(xi,x2) -( xi2x2) xi的极值点，说明参数极值点的影响。解将函数f（x1,x2）以矩阵表示f(x)-xT Qx bTx 2其中：xx1 , QX2根据定理1.6,有:_ * _f(x ) Qx b 02f(x)0 x110x20如果 0,0 ,局部极小点位于x1Lx； 0,因为函数f （x1

31、，x2）是以（,0）为圆心的椭圆，而f （x1，x2）又是凸函数，所以局部极小值 f （- ,0）也是全局极小值。x2待画x1(1.9)我们可根据上述一阶必要条件求出函数f (x) 的所有驻点, 然后再利用充分条件判断那些驻点为极值点。但是 , 求解方程组f (x)0可能是件非常复杂的工作, 在实际应用中几乎没有太大价值。为此, 我们需要设计迭代算法, 并利用计算机来搜寻f (x) 的极值点。(1.6) , 搜寻最优解的基本思路是根据某一特定迭0,1,2,. ,其中 f* inf f (x) x Rn1.5.2 无约束优化问题的迭代算法对于不带约束条件的非线性规划问题代规则产生如下逼近最优解的

32、点列 k| k f*,k如果点列 k 还满足下述条件:012k则称具有这种性质的迭代算法称为下降迭代算法。非线性规划问题(1.6)的下降迭代算法的基本步骤为步骤一：从一个初始迭代点 X0开始：选择迭彳t方向d 0,使得沿这个方向能找到使目标函数值下降的点。步骤二：计算点xk的搜索方向d k和迭代步长 k。步骤三 : 确定迭代步长k 。步骤四：令xk 1xkkdk,使得f(xk1)f (xk)。如果xk 1为极小点，迭代停止否则转第二步。显然构成下降迭代算法的方式是多种的, 它们之间的主要区别是在于如何选择迭代方向和步长。我们将重点研究利用目标函数f (x) 的一阶 , 二阶导数构造迭代方向的下

33、降迭代算法 , 它们是最陡下降法, 共轭下降法, 和 Newton 下降法。 利用一阶导数构造下降迭代法的基本原理是选择迭代方向d k , 使其与梯度向量之间满足：f(xk)Tdk 0同时 , 为了确定迭代步长k , 我们需要一维优化技术.1.5.3 一维函数最优化算法由于一维非线性函数极小化问题是诸多无约束非线性规划问题算法的基础，我们将首先考虑如下一维非线性函数的极小化问题：min f(x)(1.7)x a,b我们也可将极小化问题(1.7)看作是带约束条件的一维非线性规划问题.我们首先分析 任彳xo a,b为极值点的必要条件.一般来说，使目标函数f (x)达到局部极小值的点必须 是以下以下

34、三类情形之一：情形1：存在满足a x° b的点，并且使得目标函数一阶导数为零，即f'(xo) 0,称xo为驻点.图（1.10）图(1.10)说明，当f (x)的取值从左边至右通过驻点xo时，f (x)从负值变为正值，则xo是局部极小点.反之，xo是局部极大点.怕形2：对于任思a xo b,目标函数在点xo处的一阶导数f (xo)不存点图(1.10)如果f (x)在点X0处不存在一阶导数,X0可能是极小点或不是极小点.在这种f#况下,判断极小点的方法是通过检查在X0邻域函数f (x)值的变化，即f (x)在X X0和X X0的值.如果f (X0) f (X1)并且f(X0) f

35、(X2);则X0是极小点；如果f(X。)f(X1)并且f(X0)f(X2)，则X0不是极小点情形3：区间a,b的端点a和b图(1.10)从图中可以看出，如果f (a)0 ,则端点a是极小点；如果f (b) 0,则端点b是极小点.例1.3设有函数：f(X)2 (x 1)20x33 (X 4)2 3 X 6求f (x)在区间0,6中的所有极值点和最大值解：情形 1 对于 0 x 3, f (x) 2(x 1),及 f (x)2 ,极值点为x 1;对于3 x 6, f (x) 2(x 4),及 f (x) . . _ " . .2,极值点为x 4.由于f (1) 0 , x 1是局部极大点

36、.由于f (4) 0, x 4是局部极小点情形2： f(x)在x 3处一阶导数不存在.考虑f (2.9)1.61 ,f(3)2 ,f(3.1)2.19, x3不是局部极值点情形3：考虑区间0,6的端点.因为f'(0)2 0, x 0是局部极小点；因为, ' _ f (6) 4 0, x 6是局部极大点.综合上述三种情形,在区间0,6上，函数f(x)有两个局部极大点x 1和x 6 .因为f(1) 2及f(6) 1,我们可求得x 1使f(x)达到最大值.例1.4产品定价的非线性规划问题在市场经济中，互相竞争的企业的一项重要决策是确定它们产品的价格.如果市场对产品的需求是价格的线性函

37、数：D a bP其中a, b为待定参数.如果单位产品的生产成本为c,那么，产品的利润可表示为：(P c)(a bP)所以，确定利润最大化的价格等同于求解非线性规划首都食品厂生产系列零食产品 .一小袋葡萄干的生产成本为人民币 0.55元，其销售价在 1.10元到1.50之间.市场部门收集了在三个城市葡萄干的价格在1.10元，1.30元，和1.50元情况小的销量，见下表：表9.2:葡萄干在三个城市的销售数据单位成本:0.55元需求重单位：千袋销售价格(元)北京地区上海地区广东地区低价:1.10353224中价:1.30322717高价:1.5022169.首先，利用表解：我们将用Excel的规划求

38、解功能求解这个产品定价的非线性规划问题9.2中的数据分别估计三个地区的需求函数：北京地区：D 87.5P2 195P 73.625上海地区：D75P2 155P 47.75广东地区：D12.5P2 5P 44.625它们是通过Excel的曲线拟合功能实现的(参见表至表.表9.3:北京地区需求函数的拟合北京地区表9.4:上海地区需求函数的拟合上熟跑区7 = -75x3-h155x - 47 751飙椅嘉*意将行坝式而列114030*加忖QQQ Q5Q表9.5：广东地区需求函数的拟合厂东地区30亲列1零项式保列1)2010户-12.5K2- 5K + 44.625口0,000,501.0C1.50

39、2,00价格为了利用Excel的规划求解，我们设定I 6为目标单元格，以H4为可变单元格，其取值 范围为 H4 1.10，和 H4 1.50.表9.6:产品定价的非线性规划问题11洞里入曾下的才箭r)LP«>需求电单密;千购成本口£5北百慷口匕比区亡东区苗北市地区匕海博K产篇恒格等求事 而茶拿需求拿 饰珞再茕堂 需米量中海mD O 3 -.3.13.5导1- 1- V Q1.29 士为 27 32广本区域 告求聿17.3D总金或审7£jS&5E熨表9.6说明，使葡萄干利润最大的价格应当为1.29元.1.5.4 一维搜索技术在某些，f#况下，非线性规划

40、(1.7)的目标函数不具有一阶导数，或者是根本无法求出满足f (x) 0的解，这时我们无法用上一节介绍的方法求解(1.7).我们将讨论在 f (x)是单峰函数情况下的迭代算法.定义1.8 设函数f (x) : RR是区间a,bR上的单变量函数，如果下述条件存在c a,b,使f(c)x"X)(2) f(x)在a,c上严格递减,在c, b上递增成立，称a,b是函数f(x)的单峰区间，而f(x)则称为是a,b上的单峰函数。ab图(1.10)可见，一个区间是某函数的单峰区间意味着，在该区间中函数只有一个极小值。图(1.10)中的区间a,b是f(x)的单峰区间，或f(x)是区间a,b上的单峰函

41、数。为了求解一维函数的极小化问题(1.7), 一般可先从它的单峰区间a, b开始，通过不断地缩短单峰区间a,b的长度来搜索问题(1.7)的最优解。下面介绍求问题(1.7)最优解的两个方法：黄金分割法和Fibonacci法。(1)黄金分割法假设初始单峰区间为 匕0,d,黄金分割法的基本思路是在区间a0,b0中选取两个对称点a1和b1,并假设a1 b1。如果f (a1) f (“),那么极小点一定为于区间a。,"；如果f(a1)f("),那么极小点一定为于区间a1,bO。显然a0,bj和a1,b0是缩短了单峰区.、-t,. *、，、-间g0,d,图(1.11)说明了在f(a1)

42、 f (b1)的情况下，极小点x是位于区间a0,b1之间。f(x)*.a0x a1b1b0图(1.11)对于新的单峰区间a。，"或ai,bo,重复以上做法直到单峰区间缩短到足够小时 ，取 最后的收敛点作为最优点的近似值。为了使某单峰区间的长度能尽快缩短，考虑下列情况：.一 1设 lb。 a。，给定 02,根据图(1.12) , b1 a。(1 )l , b。 “ l,而区间bo,b1的长度与区间ao,b1的长度的比例等于ao,b1与ao,bo的比例:(1)(1.8)1 (1)1 l a°lbjbo l 图(1.12)为了计算 值，我们将式(1.8)改写为：2 31 O1那么

43、，我们只需要求解上述二次方程.考虑到O一,可求得解为O.382。2这样一来，在一次迭代之后，单峰区间缩短了 (1) O.618。因为每次迭代的步长都等于1，所以在n步之后，单峰区间缩短到(1)n O.618n.例1.5用黄金分割法搜索如下一维最小化问题：min f(x) 4x2 6x 3在区间O,1上的近似极小点和极小值，要s求缩短后的区间长度不大于原区间长度的8% .解 容易3证，f(x)在区间O,1上的精确解为 x O.75 , f (x )5.25 .因为aoO ,bo 1,选择前两个迭代点：x10.382 1, x10.618 1f(x1) 4 0.3822 6 0.382 34.71

44、-'一一 一 2一一一 一一f(x1)4 0.61860.61835.11由于f(x1)f(x1)，极小值点在区间x1,b0中，为了进行下一步迭代，令：ax10.618 ,"b01,则有：x20.618 0.382 (1 0.618)0.764x20.618 0.618 (1 0.618)0.854精品2 _f(x2)40.76460.76435.2492f(x2)40.85460.85435.21由于 f(x2)f (x2)，极小值点在区间a1,x2中，令：a2 a1 0.618, b2 x20.764 ,有：0.6740.708x30.618 0.382 (0.764 0

45、.618)x30.618 0.618 (0.764 0.618)f(x3) 4 0.6742 6 0.674 35.227f(x3) 4 0.7082 6 0.708 35.243由于 f(x3) f J3)极小值点是在区间x3,b2中，令：a3 x3 0.708b3b20.764,因为b3a30.7640.7080.056 0.08，所以我们可以确定区间a3,b3为最终区间b°a。10极值点为b3 0.764，极小值为f (b3)5.249.(2) Fibonacci 法Fibonacci法的基本思想是在每次迭代中使用不同步长1，1 k, k 0,2 , k 1,2,n根据黄金分割

46、比例(1.8),则有：,k 1,2,，n 1为了以最快速度求得最优解，考虑下述最小化问题：min(11)(12)(1st,k k 2,k1,2,., n 11,2,., n(1.9)定义1.9 设F0F11,Fk1Fk1Fkk 1,2,.,n1 ,则称数列Fk为Fibonacci数列，其中Fk被称为第k个Fibonacci数,相邻两个Fibonacci数之比5Fk为 Fibonacci 分数。前十项Fibonacci数列如下：Fk 18 13 2134 55定理1.8 数学规划(1.9)的最优解为：1 FnkFn k 21,2,.,n其中Fk是第k个Fibonacci数。例1.6用Fibona

47、cci法搜索如下一维最小化问题2min f (x) x 2x10% .在区间1,2上的近似极小点和极小值，要求缩短后的区间长度不大于原区间长度的，一、*、Q ，、一 、一- *解 容易3证，f(x)在区间1,2上的精确解为x 1 , f(x ) 0.因为缩短后的区间长1 1度与区间1,2的长度的比值为 ,，根据题意要求 0.1，或Fn10,所以n 6,即需FnFn要迭代6次.因为a。1, b0 2,选择前两个迭代点并计算迭代点处的函数值：Xib0F5F6(a0b0)2 袅 1 2)0.154X1a。F5-5(b0 a0)1F6争(明0.846f(Xi)2_0.15420.1540.7157f(

48、Xi)0.846220.8460.0237由于f(x1)f(X1),令：a1 X10.154,b1b02,则获得新的迭代点：X2X10.846,x2a1a1) 0.1545(2 0.154) 1.3088f(X2)一 一 20.8460.8460.0237f(X2)1.30821.3080.0949由于f(x2)'f (X2),令：a?a10.154,b2X21.308 ,重新计算迭代点：X3x20.846X3b2F3.b2) 1.30835(0.154 1.308) 0.616f(X3)0.61620.616 10.1475f(X3)0.84620.846 10.0237由于f(X3

49、)f (x3),令：a 3 X30.616, b3b21.308，重新计算迭代点：X4X30.846X4a3F2汕F 3a3) 0.6162(1.308 0.616) 1.077f(X4)一 一 20.8460.846 10.0237f(X4)21.0771.077 10.0059 ，'、由于f(X4)f(X4),令：a4 X40.846, b4b31.308，重新计算迭代点：x5x4 1.077精品x5a41-(1.308 0.846) 1.077Fi1(b4 a4)0.846F2精品f(X5)1.0772 21.077 10.0059f(X5)1.0772 21.077 10.0059由于 f(X5)f(X5)令：a5x51.077,b5b41.308，这时区间长