约束极值问题.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,约束极值问题,最优性条件,考虑函数约束问题,集合 称为可行域,(,集,),，,S,中任一点称为可行点。,定义：设,若,g,i,(,x,)=0,则称该不等式约束为关于可行点,x,的起作用约束,(,紧约束,),，若,g,i,(,x,)0,称为不起作用约束。,I,(,x,)=,i,|,g,i,(,x,)=0,称为起作用约束指标集，,J,(,x,)=,i,|,g,i,(,x,)0,称为不起作用约束指标集,.,可行方向,(,不等式约束的情况,),考虑问题,设,g,i,(,x,),可微,若非零向量,d,满足,则,d,为,x,处的可行方向；若,d,是,x,处的可行方向，则,定理,1,设,x,*,是约束非线性规划问题的一个局部极小值点,则,x,*,处不存在下降可行方向。若,f,(,x,),g,i,(,x,),在,x,*,处可微，则不存在向量,d,同时满足,定理,2(,不等式约束的,KT,条件,),设,x,*,是约,束非线性规划问题的局部最优解，,在,x,*,处可微，在,x,*,处连续，再假设,线性无关,则存在,u,i,0,使得,如果 在,x,*,处也可微，则可写为,包含等式约束的,KT,条件,例 用,KT,条件，求解最优化问题,KT,条件为,解得,KT,点,(1,0),。由于是凸规划问题，是最优解。,二次规划,目标函数为二次函数，约束条件为线性的,称为二次规划。二次规划的一般形式为,只有等式约束的情况,方法一：化为无约束的形式,方法二：,Lagrange,乘子法得,例 求解二次规划问题,法一,:,x,3,=-3,x,1,x,2,=2-2,x,1,，化为无约束问题。,法二,:,写,KT,条件，解线性方程组。,不等式约束情况,KT,条件为,可行方向法,线性约束的情况,定理,:,设 是问题的可行解,在 处有,则非零向量,d,是 处的可行方向的充分必要条件是,可通过如下线性规划问题求可行方向,非线性约束问题,考虑,求一下降可行方向,算法,Step1,给定初始可行点,x,(0),，令,k,=0,；,Step2,求上述线性规划问题的解，若,z,=0,结束，否则得下降可行方向,d,k,；,Step3,沿,d,k,作一维搜索,令 转,Step2,。,罚函数法,对约束最优化问题,设想定义一个新函数,(,惩罚,),并考虑无约束问题,显然若,x,*,是无约束问题的最优解，则必是原问题的最优解。,p,(,x,),不是普通的函数，不能直接实现，考虑通过极限的方法来实现。,序列无约束极小化技术,(SUMT),一、罚函数,(,外罚,),法,罚函数定义：若函数,p,(,x,),满足如下三个条件,i),p,(,x,),连续；,ii),p,(,x,),0,；,iii),p,(,x,)=0,的充要条件是,则称其为关于,S,的罚函数。,例如 对,S,=,x,|,g,(,x,),0,h,(,x,)=0,则,是,关于,S,的罚函数。,对无约束问题,min,f,(,x,)+,Mp,(,x,),M,为罚因子。当,M,趋于无穷时,解逼近原约束问题的解,.,算法,(,罚函数法,),定义,p,(,x,),取序列,M,k,满足,M,k,+1,M,k,0,F,(,x,M,k,)=,f,(,x,)+,M,k,p,(,x,).,Step0,取初始点,x,0,精度,e,0,令,k,=1.,Step1,计算,min,F,(,x,M,k,)=,F,(,x,k,M,k,),Step2,若,M,k,p,(,x,k,),M,k,0,x,k,由罚函数法产生,则,i),F,(,x,k,M,k,),F,(,x,k,+1,M,k,+1,);,ii),p,(,x,k,),p,(,x,k,+1,);iii),f,(,x,k,),f,(,x,k,+1,).,引理,2,设,x,*,是原约束问题的最优解，则有,f,(,x,*),F,(,x,k,M,k,),f,(,x,k,).,定理 若,x,k,由罚函数法产生,则在一定的条件下,x,k,收敛到原约束问题的解。,例 用罚函数法求解优化问题,考虑无约束问题,令梯度为零得,由,(1)(3),得,x,3,=-3,x,1,代入,(2),联立,(1)(2),解得,令,M,趋于无穷，得解,对罚函数的解，有,障碍函数,(,内罚,),法,丰满集,:,若 则称,S,为丰满集。,障碍函数：函数 如果满足如下三个条件，则称为,S,上的障碍函数。,i),B,(,x,),连续；,ii),B,(,x,)0,；,iii),当,x,趋于,S,的边界时,B,(,x,),趋于正无穷大,即,如对,S,=,x,|,g,i,(,x,),0,都是,S,上的障碍函数。,算法,(,障碍函数法,),定义,B,(,x,),取序列,r,k,满足,r,k,r,k,+1,0,F,(,x,M,k,)=,f,(,x,)+,r,k,B,(,x,).,Step0,取初始点内点,x,0,精度,e,0,令,k,=1.,Step1,计算,min,F,(,x,r,k,)=,F,(,x,k,r,k,),Step2,若,r,k,B,(,x,k,),r,k,+1,0,x,k,由障碍函数法产生,则,i),F,(,x,k,r,k,),F,(,x,k,+1,r,k,+1,);,ii),B,(,x,k,),B,(,x,k,+1,);iii),f,(,x,k,),f,(,x,k,+1,).,引理,4,设,x,*,是原约束问题的最优解，则有,f,(,x,*),f,(,x,k,),F,(,x,k,r,k,).,定理 若,x,k,由障碍函数法产生,则在一定的条件下,x,k,收敛到原约束问题的解。,例 用障碍函数法求解优化问题,考虑无约束问题,令,解得,令 得原问题的最优解为,算法优缺点,罚函数法：对,f,(,x,),g,(,x,),h,(,x,),要求不高,可处理大量问题,可利用许多无约束优化算法；,计算工作量大，解一般落在可行域外。,障碍函数法：解落在可行域内部；,计算工作量大，初始点须是可行域的内点，不能直接处理等式约束。,