在这一节，我们介绍如何用梯度投影法来解如下的优化问题：
\begin{align} \mathop{\min}&\quad f(x)\nonumber\\\mathop{s.t.}&\quad \mathbf{A}_1 x\leq b_1\nonumber\\&\quad \mathbf{A}_2x= b_2\label{equ:originalModel}\end{align}
其中$x\in\mathbb{R}^n,\mathbf{A}_1\in\mathbb{R}^{m_1\times n},b_1\in\mathbb{R}^{m_1},\mathbf{A}_2\in\mathbb{R}^{m_2\times n},b_2\in\mathbb{R}^{m_2}$，并且假设$\left[\begin{array}{lcr}\mathbf{A}_1\\\mathbf{A}_2\end{array}\right]$为行满秩矩阵。
定义：
- 矩阵$\mathbf{P}\in\mathbb{R}^{n\times n}$，若$\mathbf{P}^\prime=\mathbf{P},\mathbf{P}^2=\mathbf{P}$，则称$\mathbf{P}$为投影矩阵。
- 设$\mathbf{A}\in\mathbb{R}^{m\times n}$为行满秩矩阵，则$\mathbf{A}$的零空间为$L_{\mathbf{A}}=\{x\in\mathbb{R}^n|\mathbf{A}x=0\}$，对应的正交空间为$L_{\mathbf{A}}^{\perp}=\{\mathbf{A}^\prime y|y\in\mathbb{R}^m\}$。
对$\forall x\in\mathbb{R}^n$进行正交分解使$x=x_1+x_2,x_1\in L_{\mathbf{A}},x_2\in 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^k$为当前迭代点，对$A_1,b_1$进行分块$A_1=\left[\begin{array}{lcr}\mathbf{A}_{11}\\\mathbf{A}_{12}\end{array}\right]$，$b_1=\left[\begin{array}{lcr}b_{11}\\b_{12}\end{array}\right]$，其中$\mathbf{A}_{11}x^k=b_{11},\mathbf{A}_{12}x^k<b_{12}$。
记 $\mathbf{M}=\left[\begin{array}\mathbf{A}_{11}\\ \mathbf{A}_2\end{array}\right]$ ，$\mathbf{L_M}$为$\mathbf{M}$的零空间。当$s\in\mathbf{L_M}\backslash\{0\}$时，$s$是$x^k$处的可行方向。
对负梯度$-\nabla 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}\nabla f(x^k)$。
若$s^k\neq 0$，则$s^k$是$x^k$处的可行方向。
若$s^k=0$，则$\nabla f(x^k)-\mathbf{M}^\prime(\mathbf{MM}^\prime)^{-1}\mathbf{M}\nabla f(x^k)=0$。记$w=\left[\begin{array}u\\ v\end{array}\right]=-(\mathbf{MM}^\prime)^{-1}\mathbf{M}\nabla f(x^k)$，其中$u$与$\mathbf{A}_{11}$对应，$v$与$\mathbf{A}_2$对应。
$\Longrightarrow$
\begin{align}0&=\nabla f(x^k)+\mathbf{M}^\prime w=\nabla f(x^k)+(\mathbf{A}_{11}^\prime,\mathbf{A}_2^\prime)\left[\begin{array}u\\ v\end{array}\right]\nonumber\\&= \nabla f(x^k)+\mathbf{A}_{11}^\prime u + \mathbf{A}_2^\prime v\label{equ:functionSK}\end{align}
在得到可行下降方向$s^k$后，需求解一维搜索问题$\mathop{\min}_{0\leq\lambda\leq\lambda_{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\}$。
故梯度投影法的算法为：