Jordan Lecture Note-3: 梯度投影法

    在这一节，我们介绍如何用梯度投影法来解如下的优化问题：

其中$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[

定义：

1. 矩阵$\mathbf{P}\in\mathbb{R}^{n\times n}$，若$\mathbf{P}^\prime=\mathbf{P},\mathbf{P}^2=\mathbf{P}$，则称$\mathbf{P}$为投影矩阵。 
2. 设$\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_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[

 定理：$s\neq 0$是$s$在$x^k$处的可行方向当且仅当$s$满足条件$\mathbf{A}_{11}s\leq 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}s\leq 0,\mathbf{A}_2s=0$。

 记 $\mathbf{M}=\left[

    对负梯度$-\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[

$\Longrightarrow$

定理：若上述1) $u\geq 0$，则$x^k$是KKT点；2) 若$u$ 中有负分量，设$u_{i0}=\mathop{\min}\{u_i\}<0$，$\bar{ \mathbf{M}}$是从$\mathbf{M}$中去掉$u_{i0}$对应的行后得到的矩阵，则$\bar{s^k}=-\mathbf{P_{\bar{M}}}\nabla f(x^k)$是$x^k$的可行下降方向。

 证明：1）由$\nabla f(x^k)+\mathbf{A}_{11}^\prime u + \mathbf{A}_2^\prime v=0$且$u\geq 0$ $\Longrightarrow$ $x^k$是KKT点。

2）记$\mathbf{M}$中与$u_{i0}$ 对应的行为$\alpha_{i0}^\prime$，故$u=\left[

$$\begin{array} &u_{i0} \\ \bar{u}\end{array}$$ \right]$,$\mathbf{A}_{11}=\left[ $$\begin{array} &\alpha_{i0}^\prime\\ \bar{\mathbf{A}_{11}}\end{array}$$ \right]$,$w=\left[ $$\begin{array} &u_{i0}\\ \bar{w}\end{array}$$ \right]$，则$\bar{\mathbf{M}}=\left[ $$\begin{array}&\bar{\mathbf{A}_{11}}\\ \mathbf{A}_2\end{array}$$ \right]$,$\mathbf{M}=\left[ $$\begin{array} &\alpha_{i0}^\prime\\ \bar{\mathbf{M}}\end{array}$$ \right]$，

令$\beta=-(\bar{\mathbf{M}}\bar{\mathbf{M}}^\prime)^{-1}\bar{\mathbf{M}}\nabla f(x^k)$ 。

先用反证法证$\bar{s^k}\neq 0$。假设$\bar{s^k}=0$，即：

$$\begin{equation}0=\nabla f(x^k)-\bar{\mathbf{M}}^\prime(\bar{\mathbf{M}}\bar{\mathbf{M}}^\prime)^{-1}\bar{\mathbf{M}}\nabla f(x^k)=\nabla f(x^k)+\bar{\mathbf{M}}^\prime\beta\label{equ:2}\end{equation}$$

由式子 $\ref{equ:functionSK}$ 有：

$$\begin{equation}0=\nabla f(x^k)+\mathbf{M}w=\nabla f(x^k)+u_{i0}\alpha_{i0}+\bar{\mathbf{M}}^\prime\bar{w}\label{equ:3}\end{equation}$$

由式子 $\ref{equ:3}$ $-$ $\ref{equ:2}$ 得：$u_{i0}\alpha_{i0}+\bar{\mathbf{M}}^\prime(\bar{w}-\beta)=0$。又由于$u_{i0}<0$，故$\mathbf{M}=\left[

$$\begin{array}&\alpha_{i0}^\prime\\\bar{\mathbf{M}}\end{array}$$ \right]$行向量线性相关，与$\mathbf{M}$行满秩条件矛盾，故$\bar{s^k}\neq 0$。

     由于

$$\nabla f(x^k)\bar{x^k}=-\nabla f(x^k)\mathbf{P_{\bar{M}}}\nabla f(x^k)=-[\nabla f(x^k)]^\prime\mathbf{P_{\bar{M}}}^\prime\mathbf{P_{\bar{M}}}\nabla f(x^k)=-\|\mathbf{P_{\bar{M}}}\nabla f(x^k)\|^2<0$$

即$\bar{s^k}$是$f(x)$在$x^k$处的下降方向。由于$\bar{s^k}=-\mathbf{P_{\bar{M}}}\nabla f(x^k)$且 $\mathbf{\bar{M}}\mathbf{P_{\bar{M}}}=0$，故$\mathbf{\bar{M}}\bar{s^k}=0$，即

$$\begin{equation}\bar{\mathbf{A}_11}\bar{s^k}=0\quad\mathbf{A}_2\bar{s^k}=0\end{equation}$$

所以$\mathbf{A}_{11}\bar{s^k}=\left[

$$\begin{array}&\alpha_{i0}^\prime\\\bar{\mathbf{A}_{11}}\end{array}$$ \right]\bar{s^k}=\left[ $$\begin{array}&\alpha_{i0}^\prime\bar{s^k}\\0\end{array}$$ \right]$，故只需证$\alpha_{i0}^\prime\bar{s^k}<0$即可。

    由式子 $\ref{equ:3}$ 可知：

$$\begin{align*}\alpha_{i0}^\prime\bar{s^k}&=\frac{-\nabla f(x^k)-\bar{\mathbf{M}}^\prime \bar{w}}{u_{i0}}\bar{s^k}\\&=\frac{-[\nabla f(x^k)]^\prime\bar{s^k}-\bar{w}^\prime\bar{\mathbf{M}}\bar{s^k}}{u_{i0}}\\&=\frac{-[\nabla f(x^k)]^\prime\bar{s^k}}{u_{i0}}<0\end{align*}$$

即$\mathbf{A}_{11}\bar{s^k}<0,\mathbf{A}_2\bar{s^k}=0$，故$\bar{s^k}$为可行下降方向。

Jordan Lecture Note-3: 梯度投影法

原文：http://www.cnblogs.com/boostable/p/lec_gradient_projection_method.html