《管理科学理论课件.ppt》由会员分享，可在线阅读，更多相关《管理科学理论课件.ppt（33页珍藏版）》请在三一办公上搜索。
1、第四章 约束非线性优化的理论与方法,一，等式约束问题1，切向量与正规性定义1 设x0 是由方程组gi(x)=0， i=1,2, ,m，确定的曲面S上的一点，若在S上存在曲线x(t)，x(0)= x0，x(0)=h，则称向量是曲面S上点x0处的切向量。定义2：如果关于h 的线性方程组：系数矩阵,满秩，则称x0为曲面S上的一个正规点。注1 是x0处法空间的一组基。注2 方程组 的一组线性无关的解构成曲面S上x0处切空间的一组基。2，具等式约束问题的极值必要条件考虑二维问题： min f (x,y) S.t. g (x,y)=0结论1:若在极小点(x0,y0)处,g (x0,y0) 0，则f (x0
2、,y0)与g (x0,y0)线性相关，即f (x0,y0) + g (x0,y0)=0。结论2：(Lagrange乘子规则)设(x0,y0)是局部极小点，且g (x0,y0) 0，则存在常数 ，对函数F (x0,y0)= f (x0,y0)+ g (x0,y0)，满足 F(x0,y0)= f (x0,y0) + g (x0,y0)=0.,结论3（充分条件）：设点x0满足必要条件： F(x0)= f (x0) + g (x0)=0.若则x0是局部极小点。二，具不等式约束的问题1，下降方向和可行方向考虑一般非线性约束优化问题：例：求解,1) 下降方向的选择 如果方向P在点x0处是下降方向，则P应与
3、f (x0)同侧，即：记 为点x0处的下降方向集。2) 可行方向的选择 在x0处的可行方向应满足:结论1：若 所有方向P都是可行的。结论2：若 当 时,则P为可行方向。 记 为可行方向集。注：对等式约束而言，所有约束都是起作用约束。2，最优性条件定义1：若对xC和0，有 xC ，则称C为锥，如果C是凸的，则称其为凸锥。定义2：设是约束集，称为x0处的可行方向锥。 下面进一步讨论最优性条件。设x*是问题 的最优解，则x*处,换言之，在x*处满足 的方向P必有 称 为FritzJohn 条件。其中 线性无关。 在最优点x*处应满足 Farkas引理：给定向量a i（i =1,2,k）与b，不存在向
4、量P同时满足条件 和 的充要条件是 向量b 在ai 所张成的凸锥内，即满足,定理1:设x*为问题的一个可行点,并且前t个约束为起作用约束,则x*为最优解的一个必要条件是下式成立:例:考虑问题,从上例看出，满足定理1还需增加一些约束规范，如梯度向量线性无关等，上例有 更一般的有：定理2（KuhnTucker）最优性必要条件：在最优点x*处，设线性无关，则存在满足：称上式为KT条件，满足上式的点称KT点。相应的广义Lagrange函数为：,例1：验证以下问题在最优解处K-T条件成立。解:例2:,解:定理3 设x*是一个可行点，若存在使K-T条件成立，并且对应的Lagrange函数的Hessen阵在
5、子空间M上正定，则x*是一个严格的局部极小点。其中：注 若 线性无关，则M是约束集在x*处的切空间。,定理4： 凸规划问题的可行K-T点必为最优解。3，Lagrange函数的鞍点定义1：如果对有则称点 是Lagrange函数： 的鞍点。定理5 ：若 是鞍点，则 是原问题的整体最优解，但逆一般不成立。例 考虑非线性规划问题：注 可验证x*=(0,0)T是问题的极小点(在x*是处，取* =3，则K-T条件成立)。,下证其Lagrange函数没有鞍点。 反证法 ，假设鞍点 存在，由定理5知， 必为问题的最优解，故 , 由鞍点定义，对所有的x与， 有即: 由于当x1=0，x2取充分大时，总能使右端为负
6、值，推出矛盾。鞍点迭代方法:设Lagrange函数其中为某个取定的步长，迭代过程中逐步缩小，每次迭代需计算两迭代点之间的距离，如距离减小 被接受，否则缩小，最后当两点距离充分小时，迭代终止。,4，对偶问题 原 对 问 偶 题： 问(1) 题(2) 例 考虑问题极小点为x*=(2,2)T，极小值为8，令 因此最优点*= 4，最大值 (*)=8。,1）对偶定理定理1（弱对偶定理）若x 是原问题（1）的可行解，而（，）是对偶问题（2）的可行解，则进一步有：定理2（对偶定理）： 是Lagrange函数鞍点的充要条件是：（i）x* 是原问题的解；（ii）*0，* 是对偶问题的解；（iii）,2）对偶问题
7、的几何解释设原问题为： 对偶问题为：当约束集S在映射（g，f）下的像G是非凸时，可能出现对偶间隙：三，常用非线性约束优化的方法1，序列线性规划法（Sequence Linear Programming）,2, 序列无约束极小化方法例构造新函数如下：为避免间断，令新函数为：F（x）=f（x）+M p（x），其中M为某正数， 为某一连续可微函数。上例取,以下就不同的函数构造方法分别介绍1）外罚函数法（外点法）上例中：注（1）对等式约束问题可取 （2）对不等式约束问题可取,(3) 对一般问题取：定理 设 的最优解存在，Mk为满足Mk+1 Mk (k =1,2, )的正数序列， 且Mk， 如果F(x,
8、 Mk)的极小点序列x (k)存在且收敛到x #，则x #为原问题的最优解。注 由于 ，故常以此作为收敛判别准则。,2）内罚函数法（内点法）罚函数（响应函数）： 对不等式约束问题，取惩罚因子为3）混合罚函数法 对一般约束问题记：,取罚函数为4）精确罚函数法 罚函数取为：例精确罚函数为：,5）乘子法（1）等式约束问题Lagrange函数为罚函数为：其中的迭代公式为（2）不等式约束问题引入松弛变量得增广Lagrange函数：,经过推导得关于z的极小：3）具等式和不等式的问题增广Lagrange函数为：,其中的迭代公式为例解 增广Lagrange函数为：,3，可行方向法定理 如果方向p 满足 则称p
9、是 x（k）处的可行下降方向。1）Zoutendijk可行方向法(1) 线性约束需求解如下线性规划问题例,(2) 非线性约束(具不等式约束问题)点 处的可行方向P应满足但在此严格不等式约束下，可能得不到最优解，为此将严格不等式改为为了避免 的选取过大或过小，引进新变量 ，于是找方向的线性规划问题为:为避免拉锯现象，引入 起约束可行方向法，起作用约束集改为：,全约束可行方向法：求解如下线性规划问题： 设最优解为（P（k）， k），若 k =0，则x（k）为最优解，迭代终止。若 k 0, 则得到可行下降方向P（k） 。 例,取初始点 x(0) =(1/2，1)T。得到找方向的线性规划问题为：其最优
10、解为 ,可行下降方向为,1）相关投影概念（1）正交互补空间（2）正交投影算子定理：设子空间 U 的基矩阵为 N，则(i) 从R到子空间U 的投影算子 f 可表为矩阵(ii)从R 到子空间 V=UT 的正交投影算子 q 可表为矩阵（3）正交投影算子的性质2）线性约束问题,设 x 处起作用约束超平面的法矩阵为 N（其秩为 r）；Q 为从R n 到起作用约束超平面交集上的投影算子，则 (i) 如果 则 是可行下降方向。(ii) 如果当 0，则 x 为K-T点。(3) 步长的选择 先确定出不违反约束的最大步长，再求最优步长。4) 非线性约束的处理 首先将约束线性化，即用迭代点处起作用约束曲面的切平面近
11、似曲面，再用该点处负梯度方向作为近似搜索方向; 最后将,所求得的点投影到约束曲面上. (i) 约束线性化后, 原问题的近似问题为(ii) 拉回措施 设起作用约束的法矩阵为N，取方向 q=N，其中 应满足:线性化得:拉回方向:,5, 直接法网格法 事实上是一种穷举法，在约束区域上打网格，在全部网格点上计算目标函数值，（在满足约束的点上）通过比较目标函数值，选出最优点。随机实验法 ( Monte Carlo ) 在约束区域上随机选出一些（实验）点，希望这些点在区域内的分布是均匀的，被选到的机会相同，由此认识目标函数的大致状况。,迭代方法：产生0，1上均匀分布的n个随机数 x1，x2， xn，令 yi =ai+（bi-ai）xi，i=1，2，n检验该点处约束条件是否成立，如成立，再观察函数值是否下降，否则重新产生随机数。以迭代次数或限定相邻两个目标函数值的变化幅度作为迭代的终止准则。该法适用于维数较低，约束区域较为简单的问题，否则得到的解近似程度较高。,
