在这一节，我们介绍如何用梯度投影法来解如下的优化问题：
egin{align} mathop{min}&quad f(x) onumber\mathop{s.t.}&quad mathbf{A}_1 xleq b_1 onumber\&quad mathbf{A}_2x= b_2label{equ:originalModel}end{align}
其中$xinmathbb{R}^n,mathbf{A}_1inmathbb{R}^{m_1 imes n},b_1inmathbb{R}^{m_1},mathbf{A}_2inmathbb{R}^{m_2 imes n},b_2inmathbb{R}^{m_2}$，并且假设$left[egin{array}{lcr}mathbf{A}_1\mathbf{A}_2end{array} ight]$为行满秩矩阵。
定义：
- 矩阵$mathbf{P}inmathbb{R}^{n imes n}$，若$mathbf{P}^prime=mathbf{P},mathbf{P}^2=mathbf{P}$，则称$mathbf{P}$为投影矩阵。
- 设$mathbf{A}inmathbb{R}^{m imes n}$为行满秩矩阵，则$mathbf{A}$的零空间为$L_{mathbf{A}}={xinmathbb{R}^n|mathbf{A}x=0}$，对应的正交空间为$L_{mathbf{A}}^{perp}={mathbf{A}^prime y|yinmathbb{R}^m}$。
对$forall xinmathbb{R}^n$进行正交分解使$x=x_1+x_2,x_1in L_{mathbf{A}},x_2in L_{mathbf{A}}^{perp}$，则$x_1=mathbf{P_A}x$，其中$mathbf{P_A}=mathbf{I}-mathbf{A}^prime (mathbf{A}mathbf{A}^prime)^{-1}mathbf{A}$称为$mathbf{A}$的投影矩阵。
证明：$x_1=x-x_2=x-mathbf{A}^prime y$ $Longrightarrow$ $mathbf{A}x_1=mathbf{A}x-mathbf{AA}^prime y$ $Longrightarrow$ $y=(mathbf{AA}^prime)^{-1}mathbf{A}(x-x_1)$ $Longrightarrow$ $x_1=x-mathbf{A}^prime[(mathbf{AA}^prime)^{-1}mathbf{A}(x-x_1)]=x-mathbf{A}^prime(mathbf{AA}^prime)^{-1}mathbf{A}x+mathbf{A}^prime(mathbf{AA}^prime)^{-1}mathbf{A}x_1=mathbf{P_A}x$.
设$x^k$为当前迭代点，对$A_1,b_1$进行分块$A_1=left[egin{array}{lcr}mathbf{A}_{11}\mathbf{A}_{12}end{array} ight]$，$b_1=left[egin{array}{lcr}b_{11}\b_{12}end{array} ight]$，其中$mathbf{A}_{11}x^k=b_{11},mathbf{A}_{12}x^k<b_{12}$。
定理：$s eq 0$是$s$在$x^k$处的可行方向当且仅当$s$满足条件$mathbf{A}_{11}sleq 0,mathbf{A}_2s=0$。（注：可行方向指的是$x^k$沿这个方向移动不会超出约束范围）
证明：由于$s$为可行方向，故$mathbf{A}_{11}(x^k+s)leq b_{11},mathbf{A}_{12}(x^k+s)leq b_{12},mathbf{A}_2(x^k+s)=b_2$ $Longrightarrow$ $mathbf{A}_{11}sleq 0,mathbf{A}_2s=0$。
记 $mathbf{M}=left[egin{array}mathbf{A}_{11}\ mathbf{A}_2end{array} ight]$ ，$mathbf{L_M}$为$mathbf{M}$的零空间。当$sinmathbf{L_M}ackslash{0}$时，$s$是$x^k$处的可行方向。
对负梯度$- abla f(x^k)$，我们壳通过投影矩阵$mathbf{P_M}=mathbf{I}-mathbf{M}^prime(mathbf{MM}^prime)^{-1}mathbf{M}$将负梯度投影到$mathbf{L_M}$上，即可得到可行下降方向$s^k=-mathbf{P_M} abla f(x^k)$。
若$s^k eq 0$，则$s^k$是$x^k$处的可行方向。
若$s^k=0$，则$ abla f(x^k)-mathbf{M}^prime(mathbf{MM}^prime)^{-1}mathbf{M} abla f(x^k)=0$。记$w=left[egin{array}\ u\ vend{array} ight]=-(mathbf{MM}^prime)^{-1}mathbf{M} abla f(x^k)$，其中$u$与$mathbf{A}_{11}$对应，$v$与$mathbf{A}_2$对应。
$Longrightarrow$
egin{align}0&= abla f(x^k)+mathbf{M}^prime w= abla f(x^k)+(mathbf{A}_{11}^prime,mathbf{A}_2^prime)left[egin{array}\ u\ vend{array} ight] onumber\&= abla f(x^k)+mathbf{A}_{11}^prime u + mathbf{A}_2^prime vlabel{equ:functionSK}end{align}
定理：若上述1) $ugeq 0$，则$x^k$是KKT点；2) 若$u$ 中有负分量，设$u_{i0}=mathop{min}{u_i}<0$，$ar{ mathbf{M}}$是从$mathbf{M}$中去掉$u_{i0}$对应的行后得到的矩阵，则$ar{s^k}=-mathbf{P_{ar{M}}} abla f(x^k)$是$x^k$的可行下降方向。
证明：1）由$ abla f(x^k)+mathbf{A}_{11}^prime u + mathbf{A}_2^prime v=0$且$ugeq 0$ $Longrightarrow$ $x^k$是KKT点。
2）记$mathbf{M}$中与$u_{i0}$ 对应的行为$alpha_{i0}^prime$，故$u=left[egin{array} &u_{i0} \ ar{u}end{array} ight]$,$mathbf{A}_{11}=left[egin{array} &alpha_{i0}^prime\ ar{mathbf{A}_{11}}end{array} ight]$,$w=left[egin{array} &u_{i0}\ ar{w}end{array} ight]$，则$ar{mathbf{M}}=left[egin{array}&ar{mathbf{A}_{11}}\ mathbf{A}_2end{array} ight]$,$mathbf{M}=left[egin{array} &alpha_{i0}^prime\ ar{mathbf{M}}end{array} ight]$，
令$eta=-(ar{mathbf{M}}ar{mathbf{M}}^prime)^{-1}ar{mathbf{M}} abla f(x^k)$ 。
先用反证法证$ar{s^k} eq 0$。假设$ar{s^k}=0$，即：
egin{equation}0= abla f(x^k)-ar{mathbf{M}}^prime(ar{mathbf{M}}ar{mathbf{M}}^prime)^{-1}ar{mathbf{M}} abla f(x^k)= abla f(x^k)+ar{mathbf{M}}^primeetalabel{equ:2}end{equation}
由式子 ef{equ:functionSK}有：
egin{equation}0= abla f(x^k)+mathbf{M}w= abla f(x^k)+u_{i0}alpha_{i0}+ar{mathbf{M}}^primear{w}label{equ:3}end{equation}
由式子 ef{equ:3}$-$ ef{equ:2}得：$u_{i0}alpha_{i0}+ar{mathbf{M}}^prime(ar{w}-eta)=0$。又由于$u_{i0}<0$，故$mathbf{M}=left[egin{array}&alpha_{i0}^prime\ar{mathbf{M}}end{array} ight]$行向量线性相关，与$mathbf{M}$行满秩条件矛盾，故$ar{s^k} eq 0$。
由于
$$[ abla f(x^k)]^primear{s^k}=- abla f(x^k)mathbf{P_{ar{M}}} abla f(x^k)=-[ abla f(x^k)]^primemathbf{P_{ar{M}}}^primemathbf{P_{ar{M}}} abla f(x^k)=-|mathbf{P_{ar{M}}} abla f(x^k)|^2<0$$
即$ar{s^k}$是$f(x)$在$x^k$处的下降方向。由于$ar{s^k}=-mathbf{P_{ar{M}}} abla f(x^k)$且 $mathbf{ar{M}}mathbf{P_{ar{M}}}=0$，故$mathbf{ar{M}}ar{s^k}=0$，即
egin{equation}ar{mathbf{A}_11}ar{s^k}=0quadmathbf{A}_2ar{s^k}=0end{equation}
所以$mathbf{A}_{11}ar{s^k}=left[egin{array}&alpha_{i0}^prime\ar{mathbf{A}_{11}}end{array} ight]ar{s^k}=left[egin{array}&alpha_{i0}^primear{s^k}\0end{array} ight]$，故只需证$alpha_{i0}^primear{s^k}<0$即可。
由式子 ef{equ:3}可知：
egin{align*}alpha_{i0}^primear{s^k}&=frac{- abla f(x^k)-ar{mathbf{M}}^prime ar{w}}{u_{i0}}ar{s^k}\&=frac{-[ abla f(x^k)]^primear{s^k}-ar{w}^primear{mathbf{M}}ar{s^k}}{u_{i0}}\&=frac{-[ abla f(x^k)]^primear{s^k}}{u_{i0}}<0end{align*}
即$mathbf{A}_{11}ar{s^k}<0,mathbf{A}_2ar{s^k}=0$，故$ar{s^k}$为可行下降方向。
在得到可行下降方向$s^k$后，需求解一维搜索问题$mathop{min}_{0leqlambdaleqlambda_{max}}f(x^k+lambda s^k)$，其中$lambda_{max}=mathop{min}{frac{(b_{12}-mathbf{A}_{12})_i}{(mathbf{A}_{12})_i}|forall i:(mathbf{A}_{12}s^k)_i>0}$。
使用zoutendijk可行方向法确定一维搜索步长。设从可行点$x^k$出发，沿可行方向$d_k$处一维搜索，得到迭代点：$x^{k+1}=x^k+lambda_kd_k$ 。
采用最优一维搜索步长，并保证迭代后的点满足可行性，即解如下的优化问题：
egin{align}mathop{min}&quad f(x^k+lambda_kd_k) onumber\mathop{s.t.}&quad mathbf{A}(x^k+lambda_kd_k)geq b onumber\&quad mathbf{E}(x^k+lambda_kd_k)=e onumber\&quad lambda_k geq 0 label{equ:originalSearch}end{align}
由于$x^k$为可行点，且$d_k$为可行方向，故有$mathbf{E}x^k=e,mathbf{E}d_k=0,mathbf{A}_1x^k=b_1,mathbf{A}_1d_kgeq 0$，所以模型 ef{equ:originalSearch}转化为:
egin{align}mathop{min}&quad f(x^k+lambda_kd_k) onumber\mathop{s.t.}&quad mathbf{A}_2x_k+lambda_kmathbf{A}_2d_kgeq b_2 onumber\&quad lambda_kgeq 0label{equ:search}end{align}
现在我们来确定满足上述模型 ef{equ:search}的约束条件的$lambda_k$的最大值。由$mathbf{A}_2x^k+lambda_kmathbf{A}_2d_kgeq b_2$可知：当$mathbf{A}_2d_kgeq 0$时，$lambda_kgeq 0geq frac{b_2-mathbf{A}_2x^k}{mathbf{A}_2d_k}$总是成立（注意：$b_2-mathbf{A}_2d_k<0$），即$lambda_k$的最大最为无穷大；当$mathbf{A}_2d_k$不全大于0，即存在分量$(mathbf{A}_2d_k)_i<0$时，$lambda_kleq frac{(b_2-mathbf{A}_2x^k)_i}{(mathbf{A}_2d_k)_i}$，即$lambda_k$的最大值为$lambda_{max}=mathop{min}{frac{(b_2-mathbf{A}_2x^k)_i}{(mathbf{A}_2d_k)_i}|forall i:(mathbf{A}_2d_k)_i<0}$。综上所述，最优一维搜索模型为：
egin{equation}mathop{min}_{0leqlambdaleqlambda_{max}}quad f(x^k+lambda d_k)label{equ:optimizationSearch}end{equation} .
故梯度投影法的算法为：
step 1: 给出满足约束条件的初始点$x^0$，令$k=0$。确定精度参数$epsilon>0$；
step 2: 构造搜索方向。对$mathbf{A}_1$和$b_1$进行分块，使$mathbf{A}_1=left[egin{array}mathbf{A}_{11}\mathbf{A}_{12}end{array} ight]$,$b_1=left[egin{array}&b_{11}\b_{12}end{array} ight]$，其中$mathbf{A}_{11}x^k=b_{11},mathbf{A}_{12}x^k<b_{12}$。令$mathbf{M}=left[egin{array}mathbf{A}_{11}\mathbf{A}_2end{array} ight]$，若$mathbf{M}$为空（即$x^k$在可行区域内部），令可行方向$s^k=- abla f(x^k)$，否则令$s^k=-mathbf{P_{M}} abla f(x^k)$。
step 3: 终止条件判断。若$|s^k|>epsilon$，转step 5；若$|s^k|leqepsilon$，则当$mathbf{M}$空时停止(无可下降的方向)，当$mathbf{M}$非空时，求 $left[egin{array}&u\vend{array} ight]=-(mathbf{MM}^prime)^{-1}mathbf{M} abla f(x^k)$，若$ugeq 0$则停止（此时$x^k$为KKT点），否则令$u_{i0}=mathop{min}{u_i}$，转step 4.
step 4: 重新构造搜索方向。令$ar{mathbf{M}}$为从$mathbf{M}$中去掉$u_{i0}$对应的行后得到的矩阵，求$s^k=-mathbf{P_{ar{M}}} abla f(x^k)$。
step 5: 确定步长。令$lambda_{max}=mathop{min}{frac{(b_{12}-mathbf{A}_{12}x^k)_i}{(mathbf{A}_{12}s^k)_i}|forall i:(mathbf{A}_{12}s^k)_i>0}$，求解$mathop{min}_{0leqlambdaleqlambda_{max}}quad f(x^k+lambda s^k)$得到最优解$lambda_k$。
step 6: 确定新的迭代点。令$x^{k+1}=x^k+lambda_ks^k,k=k+1$，转step 2.