2 梯度投影法(精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,梯度投影法,提出问题,目标函数的最速下降方向是负梯度方向但是，在有约束,情况下，沿最速下降方向移动可能导致非可行点,措施：,对负梯度进行,投影,，使得目标函数值不仅改进，,同时又保持迭代点的可行性,梯度投影法,(Gradient Projection Method),梯度投影法,简介,梯度投影法,是,1960,年由,Rosen,提出，并由,Goldfarb,和,Lapidus,于,1968,年加以改进,.,梯度投影法的,基本思想,为,:,当迭代点在可行域内部时，取该点,处的负梯皮方向为可行下降方向；当迭代点在可行域边界上,时，取该点处负梯度方向在可行域边界上的投影产生一个可行,下降方向,(,见图,9.2.1),梯度投影法,基本概念,投影矩阵,为,投影矩阵,p,称为,x,在,V,上的,投影,.,由,行满秩矩阵,产生投影矩阵,则,(1),M,T,的,列向量生成的子空间,为：,(2),M,的,零空间,为：,V,N,=,梯度投影法,基本概念,由,行满秩矩阵,产生投影矩阵,幂等对称阵,性质,梯度投影法,基本原理,如果,M,为空，,即迭代点在可行域内部时，负梯度方向,为可行下降方向；,如果,M,非空，即迭代点在某些约束的边界上时，该点处的负梯度,在,M,的零空间上的投影为可行下降方向,可行下降方向的构造,定理,9.2.2,和定理,9.2.3,梯度投影法,基本原理,x,是,K-T,点；,或可以构造新的投影矩阵以便求得可行下降方向,定理,9.2.3,梯度投影法,基本原理,一维搜索,同,Zoutendijk,法中的一维搜索，即,算法步骤,Step1,梯度投影法,Step2,Step3,Step4,Step5,算法步骤,梯度投影法,Step6,梯度投影法,举例,参见,P256,例,9.1.2.,