3 既约梯度法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,既约梯度法,简介,1963,年，,Wo1fe,将,线性规划的单纯形法,推广到具有非线性,目标函数的问题，提出了产生可行下降方向的另一类方法，,称为,既约梯度法,(Reduced Gradient Method).,问题,既约梯度法,基本原理,(1),用既约梯度构造可行下降方向,假设问题,(9.3.1),的约束是非退化的，且,Rank(A,)=m,基矩阵,非基矩阵,非基变量列,基变量列,(9.3.1),(9.3.2),既约梯度法,基本原理,(1),用既约梯度构造可行下降方向,这是一个,n-m,维问题，而且除变量非负约束外不带其它约束,条件,因此,问题,(9.3.3),是比原来问题较低维的简单问题,为,既约梯度法,基本原理,(1),用既约梯度构造可行下降方向,根据定理,9.1.1,非零向量,d,为,x,处的可行下降方向的充要条件为,分解,d,为,:,(9.3.5),(9.3.4),=,=,既约梯度法,基本原理,(1),用既约梯度构造可行下降方向,d,为可行下降方向,如果取,Wolfe,的修正式,此修正式可能会使算法收敛到非,K-T,点,.,既约梯度法,基本原理,(1),用既约梯度构造可行下降方向,Mc,Cormick,的修正式,可行下降方向,d,满足,结论,既约梯度法,基本原理,(1),用既约梯度构造可行下降方向,结论：,定理,9.3.1,(2),确定一维搜索步长,一维搜索问题,算法步骤,Step1,Step2,Step3,Step4,Step5,Step6,Wolfe,既约梯度法,既约梯度法,推广,Abadie,和,Carpentier,(1969),成功地把,Wolfe,既约梯度法推广于求,解,带非线性等式约束,的情形，提出了著名的,GRG,法,(Generalized,Reduced Gradient Method,广义既约梯度法,).,数值实例表明，,GRG,法是目前求解约束非线性最优化问题的最有效的方法之一,.,举例,参见,P262,例,9.3.1.,。