重庆工商大学数学模型与数学实验课件08非线性规划

1、非线性规划 （Nonlinear Programming） 第一章 一般的非线性规划问题 1.1 问题概论（模型） min f (x) s .t 1（两类问题）无约束极值问题与约束极值问题（一些基本定义） 梯度 Hesse矩阵 Jaccobi矩阵 2 1.2 最优解分类 （注：不一定存在） 定义1.2.1 整体（全局）最优解 定义1.2.2 局部最优解 （已有算法基本都是求局部最优解的） 1.3 凸集与凸函数定义1.3.1 凸集定义1.3.2 （严格）凸函数 称定义在凸集K上的实值函数f (x)为凸函数，若 定义1.3.3 凹函数 3定义1.3.4 凸规划（图集上凸函数的极小化问题）定理1.3

2、.1 设 、 均为凸集，则 也是凸集 ，对任意实数， 是凸集。 （证明）（推广）定理1.3.2 有限个凸集的交集必是凸集定理1.3.3 （分离定理）K为闭凸集， 则 定理1.3.4 （支撑超平面定理）4 定理1.3.5 若 均为凸集K上的凸函数，则 也是K上的凸函数。 （请证明）定理1.3.6 设f (x)是凸集K上的凸函数，则 实数C，水平集 必为凸集。 （请证明）定理1.3.7 若f (x) 在开集K 中可微，则f 是K上的（严格）凸函数当且仅当 5证明（充分性） 任取 ，记由条件， （必要性） 6令此即需证。若 f (x) 两阶可微，则有以下的定理：定理1.3.8 设f (x)在开凸集K

3、中二阶连续可微，f 为凸函数的充要条件为：证明：（充分性）7此处从而， (必要性) 任取将 在 x 处展开 ： 8令 得定理1.3.9 证明 9此即说明f 是严格凸函数。定理1.3.10证明 当 充分小时 在 的邻域中，从而导出矛盾，证毕 101.4 最优性条件无约束极小化问题（模型） min s .t （1.4.1)定理1.4.1 （一阶必要条件）若 是可微函数， 是问题（1.4.1)的一个局部最小点的必要条件为： （无约束极小化问题求解）等价于（方程组求解）定理1.4.2 （二阶必要条件）设 为 中的二阶连续可微函数，如果 是 的一个局部极小点，则 11证明：由定理1.4.1， 。对任意的

4、由于 是局部极小点，故对于充分小的 必有此式成立必须有 ，证毕。12定理1.4.3 （二阶充分条件）设 两阶可微，若 满足则点 的一个严格局部极小点，这里 是 的两阶Hesse矩阵定理1.4.4（两阶充分条件）设 两阶连续可微，若 满足 证明：任取显然， 由假设， ，由 的任意性， 是 13定理1.4.5证毕 14具有等式与不等式约束的极小化问题 (NP) min s .t 定义 1.4.1 设x是满足(NP)约束条件的点，记 称I 为x处不等式约束中的积极约束的下标集合 定义1.4.2 （积极约束） 称约束为x处的积极约束定义1.4.3 （正则点）若向量组线性无关，则称x为约束条件的一个正则

5、点。15定理1.4.5 （Kuhn-Tucker条件）设 是(NP)的局部极小点且 其中 16例 求下面问题的 K-T 点 min s .t 解：本问题的 K-T条件为17（1）若 （舍去）若 （舍去）（2） （舍去）（3） 18故有 求得 191.5 迭代算法及收敛速度 迭代算法 记满足要求的点集为 （如 K-T 点集，最优解集等）。算法一般采用迭代方法，即：任给一个初始点步1步2 定义1.5.1 （全局收敛性）设A是求解问题的一个算法，若对任意初始点 在用算法A进行迭代时，或能在有限步求得最优解，或求得一无穷点列 ，该点列的任意聚点均为需求的点。20例1 求解问题 min s .t 算法

6、迭代点列例2 求解 min 算法 21迭代点列 若 若定义 1.5.1 （闭映射）设X何Y分别是两个非空闭集，A是从X到Y的一个点到集的映射，即对任意 有 。设 ，且 若 （例1种的映射是闭的，而例2中的映射则是非闭的） 显然，例2的最优解为 取算法A为X到X的一个映射：定理1.5.1 若对任意取定的 ：（1） （2）存在在 ， （3）算法 A 在 外是闭的则算法 A 必定是全局收敛的。（证明从略）22收敛速度定义1.5.2 设实数列 除有限个 外 除有限个 外 其他 被称为商收敛因子定理1.5.2 仅有以下三种情况之一发生： （1） （2） （3） ，23定义1.5.3 设 ，我们称 为 收

7、敛到 的阶。也称 阶收敛到 （ 对情况1 ，令 ，对情况2 ，令 ） 显然，收敛的阶越大，收敛速度越快。当数列具有一阶收敛速度时 越小数列收敛得越快。定义1.5.4 若 则称数列 超线性收敛于例2 （1） （2）24第二章 一维极值问题的最优化方法 在求解极值问题时我们经常会反复采用如下的一元函数求极值步骤：先求出一个搜索方向 d ，然后沿方向 d 作一维搜索。为此，我们先来介绍一下一维搜索的一些技巧和方法。 问题： min s .t本问题实际上是一个一元函数求极值的问题，为方便起见，以下我们讨论问题： min s .t这里 a 可以是 ，b 可以是 。252.1 仅比较函数值的最优化方法定义

8、2.1 （下单峰函数）定义2.2 （不定区间）包含下单峰函数最小点的区间a ,b方法：按一定的方法在 a ,b 区间中取若干个点，比较这些点上的函数值，不断缩小不定区间。定义2.3 （最优搜索策略）总点数相同而能使不定区间缩得最小的搜索方法。（Fibonacci 方法） Fibonacci数 1， 1， 2， 3， 5， 8， 13， 21， 34，26方法：设目前的不定区间为 a ,b ，尚有 r 个试验点。 令比较（1）若（2）若（3）若最后，当只剩下还有一个试验点时，不定区间的中点 为一试验点，最后一个试验点可取27定理2.1 利用Fibonacci法作一维搜索，经过 n 次试验后，最后

9、的不定区间长度不超过步骤：先根据Fibonacci 法的近似方法0.618法 设初始不定区间为 a ,b ，取28例（1）（2）（3） 取从头开始。 2.1 牛顿方法292.2 牛顿方法迭代公式：步1若 30定理2.2 设 是a ,b上的两阶连续可导函数，且则任取 ，由迭代公式产生的点列 收敛到（证明从略）31第三章 无约束极值问题的最优化方法问题 min s .t3.1 最速下降法 步骤1 取初始点 ， ，令k = 0 步骤2 计算 步骤3 若 停，输出 否则进入下一步 步骤4 求 使得 步骤5 令 32定理3.1 设 一阶连续可导，集合有界，则由上述算法求得的点列 有如下的性质（1） 严格

10、单调下降 （2） 的任一极限点 处必有 令 定理3.2 设 是由最速下降法产生的点列，则对每一步 k ，成立：其中A与a为Q的最大特征值与最小特征值 33据此可知（1）若A=a， 即目标函数的等值面为园，则用最速下降法一步就可求得最优解。（2）A与a的差越小，则用最速下降法求得的点列收敛得越慢。3.2 牛顿法先看二次严格凸函数 解得：对一般的函数 有： 34牛顿法迭代步骤定理3.3 353.3 共轭方向法定理3.4 若36（设计具有二次有限终止性的共轭方向法）仍取取初始点定理3.5 则迭代可在至多n步内终止并求得 的极小点。（共轭方向法的一种实现方法）步1 设已有37步2 若 作一维搜索：定理

11、3.4 用上面方法构造出来的向量组为 共轭的。（用于一般函数的共轭方向法）令Step 1. 取初始点 ，允许误差 2. 检验是否满足 ，若满足，停；否则到下一步 3. 令 38 4. 5. 6. 检验 ，若满足，停；否则检查若是，令 7. （算法完） 39定理3.5 设 是具有一阶连续偏导数的凸函数， 是由上述算法产生的无穷点列，水平集 （1） 为严格单调下降数列 （2） 的任意聚点均为问题的最优解3.4 变尺度法 （略）3.5 直接法 （略）40第四章 有约束极值问题问题 min s.t求解约束极值问题的主要途径：（1）可行下降法（无约束问题下降方向法的推广）（2）罚函数法或障碍函数法（将约

12、束加入目标）（3）解一系列线性规划（4）直接法414.1 zoutendijk可行方向法 问题 min s.t 定义4.1（不等式约束中的积极约束的下标集合）设 为问题的可行解，称为不等式约束中的积极约束集合。定义4.2（积极约束）此问题的积极约束有：42定义4.3（可行方向）设 x 是 min s .t （4.1）的可行点，即 ，称方向 d 为 x 处的可行方向，若存在定理4.1 设 x 是（4.1）的一个可行解，则 d 为 x 处的一个可行方向的充要条件为： （证明）43定义4.4 （下降方向）设 x 是（4.1）的可行解，称非零向量 d 为 x 处的一个下降方向，若存在 定理4.2 设

13、则 d 为 x 处的一个下降方向的充要条件为： （证明）定义4.5 （可行下降方向）既可行又下降的方向 44具体算法算法1 求解线性规划 min s .t （4.2)算法2 求解 min s .t （4.3）45算法3 min s .t (4.4)定理 4.3 设 （证明） 46(zoutendijk算法）任取初始点（2）求解对应若（3）令（4）求解 47例4.1用Zoutendijk方法求解 min s .t（取初始点 迭代一次） s .t4849Zoutendijk方法不具有全局收敛性（例从略）4.2 带非线性约束的问题（问题）min s .t （4.5）定义4.4 （积极约束的指标集）

14、定理4.4 设 x 是（4.5）的可行解，I(x)是 x 处的积极约束集合，d是一个非零向量，称 d 为 x 处的一个可行下降方向，如果：50（Zoutendijk可行方向法）根据定理4.4，求 x 处的可行下降方向可求解 求解此式又等价于求解 min s .t为此求解 min s .t （4.6)51定理4.5 设 x 是问题（4.5）的可行解，I(x)是x处的积极约束的下标集，注：当算法综述：任取一初始可行解步1. 记 求解 min s .t52得最优解与线性情况一样，Zoutendijk算法不具有全局收敛性53Frank-Wolfe算法问题 min s .t （4.7）（算法思想）求解

15、min s .t (4.8) 设解为 。因为可行域是凸集， 是此凸集的一个极点，故又因为 ，必有 54Frank-Wolfe算法任取一初始基本可行解步1. 求解线性规划 min s .t 得 ，若步2 55定理4.6 证明：56定理4.7 设对任意可行解 线性规划 均有解，则用Frank-Wolfe算法或能在有限步内求得一个K-T点，或求得一个无穷点列 ，它的任一聚点均为问题的K-T点。证明： 设 有聚点 ，不妨就设 ，设 57这与例 用Frank-Wolfe算法求解 min s .t解： 58求解 min s .t解得59一般讲Frank-Wolfe方法的收敛速度是比较慢的，其优点是求解的线

16、性规划的可行域均相同，若这些线性规划很以求节，则可用此方法求解。既约梯度法 问题 min s .t （4.9）其中60 是n-m维向量。61定理4.8 注（4.9）的 62代入第1式得定理4.9定理4.10 63证明：646566Rosen梯度投影法（1960）定义（投影矩阵）一个n阶方阵P被称为投影矩阵，若67问题 min s .t6869算法70例 min s .t715.序列无约束极小化方法5.1惩罚函数法（问题） min s ,t（此问题的K-T条件为 ）引入Lagrange乘子，构造无约束极值问题 min （惩罚函数法）问题 min s .t设法构造一个函数72其中例如，可取73对给

17、定的 定义函数74引理5.1 7576777879例5.1用惩罚函数法求解 min s .t80815.2 障碍函数法（问题） min s .t82838485例2 min s .t 第六章 附录 （一）优化模型实例86库存问题 库存管理在企业管理中占有很重要的地位。工厂定期购入原料，存入仓库以备生产之用；商店成批购入各种商品，放在货柜上以备零售；水库在雨季蓄水，以备旱季的灌溉和发电；但是，细心的读者会发现，这些情况下都有一个如何使库存量最优的问题，即库存量应取多大才最为合适？存储量过大，存储费太高；存储量过小，会导致一次性订购的费用增加，或不能及时满足需求而遭到损失。为了保证生产的连续性和均

18、衡性，需要确定一个合理、经济的库存量，并定期订货加以补充，按需求发放，以达到压缩库存物资、加速资金周转的目的。87瞬时送货的确定型库存问题（不允许缺货的情况） 首先考虑最简单的库存问题。假设某工厂生产需求速率稳定，库存下降到零时，再定购进货，一次采购量为，定购点的提前时间为零（即进货有保障、有规律，可根据需求提前订货），在保证不缺货的条件下，试确定最经济的采购量，使库存费用最小。 此时库存费用为 88在本模型中，平均库存量 为常量，所以问题归结为求解如下的优化问题这是一个一元函数求极小值的问题，可用微积分方法求其最优解，求得的解为 这就是所要求的经济采购量和最小费用的库存量，经济学上称这两个公

19、式为平方根公式。 89瞬时送货的确定型库存问题（允许缺货的情况） 前一模型不允许缺货，若允许缺货，则需要支付一定的缺货损失费用 。我们假设 为缺货量，单位缺货在单位时间内产生的缺货损失费用为 （元），单位物资在单位时间内的保管费为 （元）， 为单位时间内物资的需求量，问每次采购量、缺货量取为何值时，才能使库存费用和缺货损失费用之和最小？我们不妨设总费用为 则90 其中 为采购费， 为每次的采购费。 为保管费， 为平均库存量，这里， 为单位物资在计划期内的 保管费， 为一个采购周期内物资的存储时间。所以保管费为91注意到 ，上式可改写为注意到 ，则上式可改写为因此上述库存问题归结为求解92 这是

20、一个求二元函数 的极小值的问题，仍可用微积分方法求解得到 容易证明它们即为使总费用 取得最小值的经济采购量 和最经济的缺货量 ，而最小费用为 。93 最佳捕鱼方案 秘鲁是一个捕鱼业非常发达的国家，随着人们对鱼粉需求量的增长，秘鲁的捕鱼量不断增加。到1960，秘鲁已成为世界上捕鱼量最大的国家，年捕鱼量达到1000万吨，约占全球捕鱼总量的15%。捕鱼量的稳定增长使海洋生物学家越来越感到不安，1972年，生物学家们认为，秘鲁捕鱼量已达到了能维持鱼群正常生长情况下的最大捕获量的两倍，政府如再不加以控制，采取措施制止几近疯狂的捕捞，秘鲁的渔业资源将趋于枯竭，渔业生产会陷入完全崩溃的境地（Paulik,1

21、971）。秘鲁政府部门对生物学家的忠告未予理睬，对渔民们的过度捕捞听之任之。到1973年，生物学家们的担忧开始显现。当年，秘鲁沿海的鱼量猛减，渔民几乎无鱼可捕，出现了所谓“鳀鱼危机”（Idyll，1973年），并引起了全世界范围内粮食价格的上涨。下表是秘鲁海洋学院1974年提供的秘鲁渔业的历史统计数据：94 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 95 如何制定最优捕鱼方案，在不破坏鱼类生态平衡的前提下获得最大的捕鱼量呢？鱼类学家M.Schaefer于1975年在Logistic模型的

22、基础上建立了捕鱼问题的优化模型，提出了一个最优捕鱼方案的建议。以下，让我们来看看他所建立的模型。 用 记t时刻海洋中鱼的数量，r为鱼的净增长率，K为环境所能供养的饱和鱼量。 假设 在无捕捞情况下，鱼类按Logistic模型增长，即鱼的数量满足Logistic模型：96 (1) 考虑捕鱼对鱼类生长的影响。令h为捕捞率， ，此时，鱼类增长满足的微分方程为： (2) 正如第三章中Logistic模型所指出的，微分方程(1)有一个平衡解 x=K，当时，随着t趋于无穷，将有 。对于微分方程（2），平衡点的位置发生了改变，它被移到了方程 的根 处97 满足 即 易见， 为二次曲线 与直线 交点 ，即 （3

23、） 令捕鱼必须控制在 即 现在我们将进一步分析，在此前提下，又应如何捕鱼，才能使每年的捕获总量最大。 98将（3）代入捕鱼量公式得到在平衡条件下的捕鱼量：为求捕鱼量最大，令 ，求得 ，代入上式可得： 最大捕获量为： 此时99 通常情况下，渔民考虑的主要还是经济利益的最大化，此时，模型将变得复杂一些。设鱼的单价为p，单位时间的捕捞成本为CE，则由时刻a到时刻b这段时间内渔民捕鱼的收益最大，约束条件为（2）式成立，即此时要求解的问题为 上式是一个泛函极值问题，可用欧拉方程求解，因本书不准备介绍求解泛函极值的变分方法，我们只建立了此问题的数学模型，而不讨论其求解，有兴趣的读者可参考杨启帆、边馥萍编著

24、的数学模型 100光学中的折射定理 光在由一种介质进入另一种介质时，在界面处会发生折射现象。人们发现，折射现象 造成的结果是所谓“最短时间”效应，即光线会走最快的路径。 设光在介质1中的传播速度为 而在介质2中的传播速度为 。在同一种介质中，光的传播速度是常数，因而，在同种介质中它将沿着直线方向传播。现取两种介质的分界面上的一条直线为x轴，设一束光线由介质1中的A（0，a）点经x轴上的P(x,0)点，进入介质2，并沿某直线方向行进到B（d，b）点。设直线段AP与x轴的法线的夹角为 ，直线段PB与x轴的法线的夹角为 ，下面，我们将根据最短时间效应来推导出光学中的折射定理。光线由A传到B所需的时间

25、为101公式 故光线由A传播到B的总时间为最短时间效应对应的优化问题为 （ 0，d）102令得注意到 和（5.19）时又可写成此即光学中的折射定理。103身体结构的优化 在长期的生物进化过程中，动物体内的结构已趋于某种程度的最优化状态，本节将举两个实例来加以说明。本节采用的方法不同于一般的优化问题的研究，在一般优化问题中，我们研究的问题是为了达到某种意义下的最优化，人们应当如何去做。而本节要研究的却是：假设生物的结构在进化过程中不断优化，适者生存，逐步达到了某种意义下的最优化，那么，生物的结构应当具有哪些特征？ 例1（血管的分支） 假设 动物的血管系统经长期进化，几何形状已经达到了使能量消耗大

26、到最低的优化标准。104 血液在动物的血管中不停地循环流动着，在此过程中消耗的总能量显然与血管系统的几何形状有关。我们不可能讨论整个血管系统的几何形状，那样的话会涉及到太多的生理知识，对此我们甚至尚未完全搞清楚。在本节中，我们只研究血管分支处粗细血管半径的比例和分岔角度，我们希望知道，它们在消耗能量最小的原则下应取何值。为研究这一问题，我们先做如下假设： 假设： （1）一条粗血管在分支处只分成两条较细的血管 ，在分支点附近三条血管位于同一平面，并且有一对称轴。如若不然，血管长度增加必然导致能量消耗的增加，不符合优化原则，我们称此假设为几何假设。105 （2）在考察血液流动受到的阻力时，将这种流

27、动视为粘性液体在刚性管道内的运动，即将血管近似看成刚体，这是一种近似。事实上血管是有弹性的，这种近似对结果的影响很小，我们称之为物理假设。 （3）血液对血管提供的营养随着管壁内表面 积和管壁的厚度的增加而增加。管壁厚度和 血管半径成正比，我们称之为生理假设。 根据几何假设，我们作血管分支图5-4如下： 设一条粗血管在C处分叉为两条细血管并形成对称的几何图形。粗细血管的半径分别为 ，分岔处角度为 。 106 考察长度为 l 的一段粗血管AC和长度为 的细血管CB和 ，ACB（ ）的水平和垂直距离为L和H，另外血液在粗细血管中单位时间内的流量分别为q和 ，显然 。 由假设2，根据流体力学定律：粘性

28、物质在刚性管道内流动所受到的阻力与流速的平方成正比，与管道半径的四次方成反比。从而血液在粗细血管内受到阻力分别为 和其中 k 为比率系数。107 由假设3，在单位长度的血管内，血液为管壁提供营养所消耗的能量为 ，其中 b为比率系数。 根据上述假设及对假设的进一步分析，我们可以得到血液从粗血管A点流动到细血管B点，用于克服阻力及给管壁提供营养所消耗的能量为此外易得： 108将上式代入前一式中并注意到 ，得要使总能量 消耗达到最小，应求解此多元函数最小值问题，根据必要条件，应有： ，即109 解得： 故110以上公式给出的就是我们要找的血管分岔的最优解 ，由于 ， 可以算出 和 的大致范围分别为

29、上述结果和生物学家经验观察吻合得相当好。我们甚至还可以估计出血管分支次数和毛细血管的总数。通过解剖实验，可以测出最粗的大动脉血管半径和最细的毛细血管半径。例如，狗的大动脉血管半径 与毛细血管半径 之比大约为1000。设血管总共分支了n次，将由粗到细各级血管的半径记为 111由于 易得即狗大约有 根毛细血管 。 112人是怎样咳嗽的 人们在咳嗽时会收缩气管，目的在于压缩空气以增加气流的速度。这就产生了一个问题，为了使咳嗽时气流速度最大，气管应当收缩多少，事实是否真的如此？假设: 气管是弹性物质，气流在通过气管壁时会受到因摩擦而引起的阻力，根据实验结果，平均气流速度满足的方程为： （厘米/秒） 1

30、13 其中 为以厘米为单位的气管在松弛状态下的半径， 是一个和气管长度有关的正常数。 根据微积分知识，当 v 达到最大时，应当满足：即 ，由此解得，要使v达到最大，应 有：即为了使气流速度最大，咳嗽时应收缩大约1/3（33%）左右。实际情况又如何呢？经X光检查证实，人们在咳嗽时气管真的大约要收缩1/3左右。114（二）逻辑模型补充（无理数的发现） （实数域概念的产生） 牛顿、莱布尼兹虽然建立了微积分，但当时 的微积分还包含着另一个严重的问题。极限的引入使人们认识了无理数，从而产生了实数的概念。可是实数列的极限是否必定也是实数呢，会不会产生像有理数那样的情况（如 不是可以写成有理数列的极限吗，但

31、 却不是有理数）这一问题直到20世纪初才被解决，人们证明了实数的完备性，即任意实数列的极限必定仍是实数，这才使我们完全放下心来，微积分才真正成为了一门严格的数学学科。 115全体实数组成的集和不同于全体有理数组成的集合，在全体实数组成的集合中，你除了可以放心地进行加减乘除以外、也可以大胆地乘方、开方，不必担心运算的结果是否会出界。具有这种性质的数集被称为“数域”，故全体实数组成的集合被人们称为实数域。实数域的完备性则进一步说明在实数域中你甚至还可以大胆地进行极限运算，不必担心计算结果是否会出界。116（在实数集中到底是有理数多还是无理数多）人们在接受无理数并搞清了实数集的完备性（即实数集中只有有理与无理数）后，自然会想：究竟是有理数多还是无理数多？让我们再一次运用逻辑推理的方法来简要地讨论一下这一问题。 为了简单起见，我们仅比较