Projection of a vector onto the null space of a matrix I have the following optimization problem:
$$
\text{minimize}_x \Vert z - x \Vert^2 \\
\text{subject to } Ax = 0,
$$
where $x,z\in \mathbb{C}^N$, and $A\in\mathbb{C}^{M \times N}$. $A$ is a wide matrix, i.e. $M \le N$, with rank $M$. I found a closed-form solution to this problem in "D. Bertsekas, Nonlinear Programming, 1999", which is
$$
x_\star = (I_N - A^H(AA^H)^{-1}A)z,
$$
where $I_N$ is the $N \times N$ identity matrix. However, I'm having problems deriving this solution.
I have tried to use the Lagrange multiplier method as follows. The dual optimization problem is
$$
\text{minimize}_{\{x,\lambda\}} \Vert z - x \Vert^2 + \lambda \Vert Ax \Vert^2,
$$
where $\lambda > 0$ is a Lagrange multiplier. Setting the derivative of the Lagrangian Dual with respect to $x$ to zero gives
$$
x_\star = (I_N - A^HA)^{-1}z,
$$
and,  applying the matrix inversion lemma, I get
$$
x_\star = (I_N - A^H(\tfrac{1}{\lambda}I_M + A A^H)^{-1}A)z.
$$
Thus, the solution in the book and the solution I'm getting are equal when $\lambda \rightarrow \infty$. What does this mean? Any ideas how can I get the $\lambda \rightarrow \infty$ condition?
Thank you very much for your help.
 A: It might be easier to use some (related) facts from linear algebra. Implicit in
Bersekas' solution is the fact that $A$ has full rank, which is equivalent to $A A^*$ being invertible.
The space $\ker A$ is a (closed) subspace, and the problem is to find the nearest point in the subspace to the point $z$. It is straightforward (using a compactness argument) to show that a solution exists.
In the following, I am assuming that $A$ has full rank.
At a solution $\hat{x}$, we have $\|z-x\|^2 \ge \|z-\hat{x}\|$ for all $x \in \ker A$. Writing $\|z-x\|^2 = \|z-\hat{x}\|^2 + \|x-\hat{x}\|^2 - 2 \operatorname{re} \langle z-\hat{x}, x-\hat{x}\rangle $ and combining gives
$\|x-\hat{x}\|^2 \ge 2 \operatorname{re} \langle z-\hat{x}, x-\hat{x}\rangle $, and since
$\ker A$ is a subspace, this shows that $z-\hat{x} \bot \ker A$.
Since $\ker A = ({\cal R}A^T)^\bot$, we can write $z-\hat{x} = A^* \hat{y}$ for some $\hat{y}$, and since $\hat{x} \in \ker A$, we have
$A z= A A ^* \hat{y}$ and since we have assumed full rank, we have
$  \hat{y} = (A A ^*)^{-1} A z$, and so the solution is given by
$\hat{x} = z-A^* \hat{y} = (I-A^*(A A ^*)^{-1} A)z $.
A: You can argue that as $\lambda \to \infty$ you should get the correct solution because that will force $Ax = 0$, at least in the limit, since $Ax = 0$ is possible. The fact that you get a slightly different solution for finite $\lambda$ also shows that in fact it is required to let $\lambda \to \infty$ in order to get $Ax = 0$
A: You are actually not using duality here. What you are doing is called (pure) penalty approach. So that is why you need to take $\lambda$ to $\infty$ (as shown in NLP by bertsekas). Here is the proper way to show this result. We want to solve
$$\min_{Ax=0}\frac{1}{2}\|x-z\|_2^2$$
The Lagrangian for the problem reads
$$\mathcal{L}(x,\lambda)=\frac{1}{2}\|z-x\|_2^2+\lambda^\top Ax$$
Strong duality holds, we can invert max and min and solve
$$\max_{\lambda}\min_x \frac{1}{2}\|z-x\|_2^2+\lambda^\top Ax$$
Let us focus on the inner problem first, given $\lambda$
$$\min_x \frac{1}{2}\|z-x\|_2^2+\lambda^\top Ax$$
The first order optimality condition gives
$$x=z-A^\top \lambda$$
we have that $$\mathcal{L}(z-A^\top \lambda,\lambda)=-\frac{1}{2}\lambda^\top (AA^\top) \lambda+\lambda^\top A z$$
Maximizing this concave function wrt. $\lambda$ gives
$$(AA^\top) \lambda=Az$$
If $AA^\top$ is invertible then there is a unique solution, $\lambda=(AA^\top)^{-1}Az$, otherwise $\{\lambda | (AA^\top) \lambda=Az\}$ is a subspace, for which $(AA^\top)^{\dagger}Az$ is an element (here $\dagger$ denotes the Moonroe Penrose inverse). All in all, a solution to the initial problem reads
$$x=(I-A^\top(AA^\top)^{\dagger}A)z$$
A: \begin{align}
    \min_{\bar{x}}\ ||c-\bar{x}||^2 \\
  s.t.\ A\bar{x} = 0
\end{align}
Objective function can be written as
\begin{align}
  (c-\bar{x})^T(c-\bar{x})\\
  c^Tc - 2 c^T\bar{x} + \bar{x}^T\bar{x}
\end{align}
Given that all constraints are linear, the Karush-Kuhn-Tucker conditions can be applied.
\begin{align}
  -2c + 2x + A^Tv &= 0\\
  Ax &= 0\\
  2x + A^Tv &= 2c\\
  2Ax + AA^Tv &= 2Ac\\
  AA^Tv &= 2Ac\\
  v &= (AA^T)^{-1}2Ac\\
  -2c + 2x + A^Tv &= 0\\
  -2c + 2x + A^T(AA^T)^{-1}2Ac &= 0\\
  -c + x + A^T(AA^T)^{-1}Ac &= 0\\
  x &= c - A^T(AA^T)^{-1}Ac\\
  &= (I - A^T(AA^T)^{-1}A)c
\end{align} 
A: There is a problem with the optimization equation. The correct equation has to be
$$\Vert x-z \Vert^2 + \lambda(Ax)$$
To make the math simpler use the slightly tweaked but similar equation
$$\tfrac12\Vert x-z \Vert^2 + \lambda(Ax)$$
After differentiating the Lagrangian with respect to $x$ and $\lambda$, you get
$$
 \begin{bmatrix}
    I & A^T\\
     A      & 0 \\
 \end{bmatrix}
\begin{bmatrix}
     x\\
     \lambda
 \end{bmatrix}
=
\begin{bmatrix}
    z\\
    0
 \end{bmatrix}
$$
Solving which, gives
$$
x = ( I - A^T(AA^T)^{-1}A)z
$$
