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