Finding Lagrange multiplier

Question

Suppose I'm looking for $\mathbf{x} \in \mathbb{C^{M\times 1}}$ such that:

$$\mathbf{x}=\text{arg}\min_\mathbf{x}\|\mathbf{a+Ax}\|_2^2+\lambda\|\mathbf{x}\|_2^2~,$$ where $\mathbf{a}\in \mathbb{C^{N\times 1}}$ and $\mathbf{A}\in \mathbb{C^{N\times M}}$. For $\lambda > 0$ there exists a solution $\mathbf{x=-(A^HA+\lambda I)^{-1}A^Ha}$ that satisfies $\|\mathbf{x}\|_2^2=\alpha$, where $\alpha$ is known.

My question is how do I find the Lagrange multiplier $\lambda$ in the solution above that satisfies $\|\mathbf{x}\|_2^2=\alpha$.

Answer 1

You're trying to solve the following equation: $$a^TA(A^HA+\lambda I)^{-1}A^Ha = \alpha$$ You're going to have to do this numerically; say, using bisection. If you're willing to do an SVD, you can simplify a bit: let $A=U\Sigma V^H$, where $\Sigma = \mathop{diag}(\sigma_1,\sigma_2,\dots,\sigma_n)$, and define $\tilde{a}=A^Ha$. Then $$a^TA(A^HA+\lambda I)^{-1}A^Ha = \tilde{a}^H \Sigma(\Sigma^2+\lambda I)^{-1}\Sigma \tilde{a} = \sum_i \frac{\sigma_i^2|\tilde{a}_i|^2}{\sigma_i^2+\lambda} = \alpha$$ You can apply any root-finding method to this, or you could multiply through to obtain a polynomial equation in $\lambda$ to solve.

Answer 2

Let $x^*$ be a minimizer for the optimization problem \begin{align*} \text{minimize} & \quad \|a + Ax \|_2^2 \\ \text{subject to} & \quad \|x\|_2^2 \leq \alpha. \end{align*} Let $\lambda^*$ be a Lagrange multiplier for the constraint $\| x\|_2^2 \leq \alpha$. (Many numerical solvers such as CVX return $\lambda^*$ as output when solving this optimization problem.)

Then, by the KKT conditions, $x^*$ is a minimizer (with respect to $x$) of the Lagrangian \begin{equation} L(x,\lambda^*) = \| a + Ax \|_2^2 + \lambda^* \|x\|_2^2. \end{equation}