3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If $A A^*$ is to be invertible, you need $A$ to have full rank (that is $M$). $\endgroup$ – copper.hat Jun 9 '15 at 15:32
  • $\begingroup$ Yes, sir. I edited the question... $\endgroup$ – CViteri Jun 9 '15 at 16:27
  • $\begingroup$ Note that what you have above is not the dual problem. $\endgroup$ – copper.hat Jun 9 '15 at 16:55
  • $\begingroup$ You are right. When I take the correct dual problem $$ \text{minimize}_{\{x,\lambda\}} \Vert z-x \vert^2 + \lambda^H A x + x^H A^H \lambda, $$ with $\lambda \in \mathbb{C}^M$, the solution in Bertsekas is derived easily. $\endgroup$ – CViteri Jun 9 '15 at 17:58
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Thank you, your answer is very clear... $\endgroup$ – CViteri May 18 at 22:32
4
$\begingroup$

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 $.

$\endgroup$
  • $\begingroup$ Thank you very much for your answer. $\endgroup$ – CViteri Jun 9 '15 at 17:52
  • $\begingroup$ Note that showing $z-\hat{x} \bot \ker A$ is not as immediate as the above would indicate. Let $z-\hat{x} = w + k$ where $k \in \ker A$ and $w \bot \ker A$, and choose $x = \hat{x} + {1 \over 2}k$. This will show that $k=0$. $\endgroup$ – copper.hat Jan 26 '18 at 21:34
  • $\begingroup$ Curious why you unaccepted my answer after 4 years? $\endgroup$ – copper.hat May 19 at 7:43
  • $\begingroup$ Hello, I read this post yesterday after a few years and the most recent answer is more clear to me $\endgroup$ – CViteri May 19 at 16:12
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

\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}

$\endgroup$
0
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.