《约束极值问题》PPT课件

《《约束极值问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、约束极值问题最优性条件考虑函数约束问题集合称为可行域(集)，S中任一点称为可行点。定义：设,若gi(x)=0,则称该不等式约束为关于可行点x的起作用约束(紧约束)，若gi(x)>0,称为不起作用约束。I(x)={i

2、gi(x)=0}称为起作用约束指标集，J(x)={i

3、gi(x)>0}称为不起作用约束指标集.可行方向(不等式约束的情况)考虑问题设gi(x)可微,若非零向量d满足则d为x处的可行方向；若d是x处的可行方向，则定理1设x*是约束非线性规划问题的一个局部极小值点,则x*处不存在下降可行方向。若f(x),gi(x)在x*处

4、可微，则不存在向量d同时满足定理2(不等式约束的K—T条件)设x*是约束非线性规划问题的局部最优解，在x*处可微，在x*处连续，再假设线性无关,则存在ui≥0,使得如果在x*处也可微，则可写为包含等式约束的K—T条件例用K—T条件，求解最优化问题K—T条件为解得K—T点(1,0)。由于是凸规划问题，是最优解。二次规划目标函数为二次函数，约束条件为线性的,称为二次规划。二次规划的一般形式为只有等式约束的情况方法一：化为无约束的形式方法二：Lagrange乘子法得例求解二次规划问题法一:x3=-3x1,x2=2-2x1，化为无约束问题

5、。法二:写K—T条件，解线性方程组。不等式约束情况K—T条件为可行方向法线性约束的情况定理:设是问题的可行解,在处有则非零向量d是处的可行方向的充分必要条件是可通过如下线性规划问题求可行方向非线性约束问题考虑求一下降可行方向算法Step1给定初始可行点x(0)，令k=0；Step2求上述线性规划问题的解，若z=0,结束，否则得下降可行方向dk；Step3沿dk作一维搜索令转Step2。罚函数法对约束最优化问题设想定义一个新函数(惩罚)并考虑无约束问题显然若x*是无约束问题的最优解，则必是原问题的最优解。p(x)不是普通的函数，不能

6、直接实现，考虑通过极限的方法来实现。序列无约束极小化技术(SUMT)一、罚函数(外罚)法罚函数定义：若函数p(x)满足如下三个条件i)p(x)连续；ii)p(x)≥0；iii)p(x)=0的充要条件是则称其为关于S的罚函数。例如对S={x

7、g(x)≥0,h(x)=0},则是关于S的罚函数。对无约束问题minf(x)+Mp(x),M为罚因子。当M趋于无穷时,解逼近原约束问题的解.算法(罚函数法)定义p(x),取序列{Mk}满足Mk+1>Mk>0,F(x,Mk)=f(x)+Mkp(x).Step0取初始点x0,精度e>0,令k=1.S

8、tep1计算minF(x,Mk)=F(xk,Mk)Step2若Mkp(xk)Mk>0,{xk}由罚函数法产生,则i)F(xk,Mk)≤F(xk+1,Mk+1);ii)p(xk)≥p(xk+1);iii)f(xk)≤f(xk+1).引理2设x*是原约束问题的最优解，则有f(x*)≥F(xk,Mk)≥f(xk).定理若{xk}由罚函数法产生,则在一定的条件下,{xk}收敛到原约束问题的解。例用罚函数法求解优化问题考虑无约束问题令梯度为零得由(1)(3)

9、得x3=-3x1,代入(2),联立(1)(2)解得令M趋于无穷，得解对罚函数的解，有障碍函数(内罚)法丰满集:若则称S为丰满集。障碍函数：函数如果满足如下三个条件，则称为S上的障碍函数。i)B(x)连续；ii)B(x)>0；iii)当x趋于S的边界时,B(x)趋于正无穷大,即如对S={x

10、gi(x)≥0},都是S上的障碍函数。算法(障碍函数法)定义B(x),取序列{rk}满足rk>rk+1>0,F(x,Mk)=f(x)+rkB(x).Step0取初始点内点x0,精度e>0,令k=1.Step1计算minF(x,rk)=F(xk,r

11、k)Step2若rkB(xk)rk+1>0,{xk}由障碍函数法产生,则i)F(xk,rk)≥F(xk+1,rk+1);ii)B(xk)≤B(xk+1);iii)f(xk)≥f(xk+1).引理4设x*是原约束问题的最优解，则有f(x*)≤f(xk)≤F(xk,rk).定理若{xk}由障碍函数法产生,则在一定的条件下,{xk}收敛到原约束问题的解。例用障碍函数法求解优化问题考虑无约束问题令解得令得原问题的最优解为算法优缺点罚函数法：对f(x),g(x)

12、,h(x)要求不高,可处理大量问题,可利用许多无约束优化算法；计算工作量大，解一般落在可行域外。障碍函数法：解落在可行域内部；计算工作量大，初始点须是可行域的内点，不能直接处理等式约束。