《约束极值问题》PPT课件.ppt

约束极值问题,最优性条件,考虑函数约束问题 集合 称为可行域(集)，S中任一点称为可行点。 定义：设 ,若gi(x)=0,则称该不等式约束为关于可行点x的起作用约束(紧约束)，若gi(x)0,称为不起作用约束。,I(x)=i|gi(x)=0称为起作用约束指标集， J(x)=i|gi(x)0称为不起作用约束指标集. 可行方向(不等式约束的情况) 考虑问题 设gi(x)可微,若非零向量d满足 则d为x处的可行方向；若d是x处的可行方向，则,定理1 设x*是约束非线性规划问题的一个局部极小值点,则x*处不存在下降可行方向。若f(x), gi(x)在x*处可微，则不存在向量d同时满足 定理2 (不等式约束的KT条件) 设x*是约 束非线性规划问题的局部最优解， 在x*处可微， 在x*处连续，再假设 线性无关,则存在ui0,使得,如果 在x*处也可微，则可写为 包含等式约束的KT条件,例 用KT条件，求解最优化问题 KT条件为 解得KT点(1,0)。由于是凸规划问题，是最优解。,二次规划,目标函数为二次函数，约束条件为线性的,称为二次规划。二次规划的一般形式为 只有等式约束的情况 方法一：化为无约束的形式 方法二：Lagrange乘子法得,例 求解二次规划问题 法一:x3=-3x1,x2=2-2x1，化为无约束问题。 法二:写KT条件，解线性方程组。 不等式约束情况 KT条件为,可行方向法,线性约束的情况 定理:设 是问题的可行解,在 处有 则非零向量d是 处的可行方向的充分必要条件是 可通过如下线性规划问题求可行方向,非线性约束问题 考虑 求一下降可行方向,算法 Step1 给定初始可行点x(0)，令k=0； Step2 求上述线性规划问题的解，若z=0,结束，否则得下降可行方向dk； Step3 沿dk作一维搜索 令 转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),取序列Mk满足Mk+1Mk0, F(x,Mk)=f(x)+Mkp(x). Step0 取初始点x0,精度e0,令k=1. Step1 计算min F(x,Mk)=F(xk,Mk) Step2 若Mkp(xk)e,结束，以xk为原问题的解；否则，令k=k+1，转Step1。,引理1 设Mk+1Mk0,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)得x3=-3x1,代入(2),联立(1)(2)解得 令M趋于无穷，得解 对罚函数的解，有,障碍函数(内罚)法 丰满集:若 则称S为丰满集。 障碍函数：函数 如果满足如下三个条件，则称为S上的障碍函数。 i) B(x)连续；ii) B(x)0； iii)当x趋于S的边界时,B(x)趋于正无穷大,即 如对S=x|gi(x)0, 都是S上的障碍函数。,算法(障碍函数法) 定义B(x),取序列rk满足rkrk+10, F(x,Mk)=f(x)+rkB(x). Step0 取初始点内点x0,精度e0,令k=1. Step1 计算min F(x,rk)=F(xk,rk) Step2 若rkB(xk)e,结束，以xk为原问题的解；否则，令k=k+1，转Step1。,引理3 设rkrk+10,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