动态规划问题.ppt

文档介绍：一、可行方向法二、惩罚函数法第五部分求解约束非线性规划问题的方法非线性规划与动态规划第一节Zoutendijk可行方向法可行方向法::在罚函数法的基础上,:利用原问题的目标函数和约束条件构造新的目标函数--罚函数,:从可行点出发,沿可行下降方向进行搜索,求出使目标函数值下降的新的可行点。包括选择搜索方向和确定搜索步长两个主要方面。搜索方向的选择方式不同就形成不同的可行方向法。第一节Zoutendijk可行方向法考虑不等式约束非线性最优化问题()I(x0)表示在x0处起作用约束的指标集,即:()第一节Zoutendijk可行方向法起作用约束:假定x0是问题()的一个可行解,(x)0来说,满足它有两种情况:gj(x0)>0,x0不在这个约束条件形成的可行域边界上,这一约束为点x0的不起作用约束(无效约束)gj(x0)=0,x0处于由这个约束条件形成的可行域边界上,称它为点x0的起作用约束(或有效约束).显然,Tucker条件定理1设x0是问题()的可行点,f(x)、gi(x)(iI(x0))在x0点可微,gi(x)(iI(x0))在x0点连续,gi(x0)(iI(x0))线性无关,若x0是问题的局部极小点,则存在非负数ui(iI(x0)),使得如果gi(x)(iI(x0))在x0点可微,则存在不全为零的非负数ui(i=1,2,…,m),使得()()第一节Zoutendijk可行方向法KT点条件()和()均称为问题()的KuhnTucker条件,简称KT条件,满足KT条件的点称为KT点,式()(x)、gi(x)(i=1,2,…,m)是凸函数,x0是()的可行点,f(x),gi(x)(iI(x0))在x0点可微,若x0是()的KT点,则x0是问题()的全局极小点。第一节Zoutendijk可行方向法定理(K-T条件)设x0是问题()的可行点,f(x)、gi(x)(iI(x0))在x0点可微,gi(x)(iI(x0))在x0点连续,hj(x)(j=1,2,…,l)在点x0处具有一阶连续偏导数,且gi(x0)(iI(x0)),hj(x0)(j=1,2,…,l)线性无关,若x0是问题()的极小点,则存在不全为零的数ui0(iI(x0))及vj(符号无限制)(j=1,2,…,l)如果gi(x)(iI(x0))在x0点可微,则存在的非负数ui(i=1,2,…,m),和vj(j=1,2,…,l)使得()()第一节Zoutendijk可行方向法记则向量函数g(x),h(x)的Jacobi矩阵分别为:从而KT条件()可以写成()第一节Zoutendijk可行方向法例1求最优化问题的K:因为所以KT条件为:解得:KT点为:第一节Zoutendijk可行方向法例2写出下述非线性规划问题的K—T条件,并根据这些条件求非线性规划的K——T点为x0,各函数的梯度为则得该问题的K—T条件如下: