Extremize $\| \mathrm A \mathrm x \|_2$ subject to $\| \mathrm B \mathrm x \|_2 = 1$

Question

Problem:

Suppose $A, B \in \mathbb{R}^{n \times n}$. Formulate a condition for vectors $\vec{x} \in \mathbb{R}^n$ to be critical points of $\|A\vec{x}\|_2$ subject to $\|B\vec{x}\|_2 = 1$. Also, give an alternative expression for the value of $\|A\vec{x}\|_2$ at these critical points, in terms of a Lagrange multiplier for this optimization problem.

Thoughts:

Set up Lagrange: $$\Lambda(\vec{x},\lambda) = \|A\vec{x}\|_2 - \lambda(\|B\vec{x}\|_2 -1)$$ Take the partial of $x_i$ $$\frac{\delta\Lambda}{\delta x_i} \Lambda= \frac{\sum_jA_{ji}x_i}{\|A\vec{x}\|_2} - \lambda\frac{\sum_jB_{ji}x_i}{\|B\vec{x}\|_2}$$

Assuming I did the differentiation correctly, which I'm not sure about.

Also:

$$\frac{\delta\Lambda}{\delta \lambda} \Lambda \implies \|B\vec{x}\|_2 = 1$$

But I'm not sure what to do at this point.

Answer 1

We have

$$\begin{array}{ll} \text{extremize} & \| \mathrm A \mathrm x \|_2\\ \text{subject to} & \| \mathrm B \mathrm x \|_2 = 1\end{array}$$

Let $\mathrm y := \mathrm B \mathrm x$. Assuming that $\mathrm B$ is invertible, then we have an optimization problem in $\mathrm y \in \mathbb R^n$

$$\begin{array}{ll} \text{extremize} & \| \mathrm A \mathrm B^{-1} \mathrm y \|_2\\ \text{subject to} & \| \mathrm y \|_2 = 1\end{array}$$

The maximum is

$$\| \mathrm A \mathrm B^{-1} \mathrm y \|_2 \leq \| \mathrm A \mathrm B^{-1} \|_2 \underbrace{\| \mathrm y \|_2}_{=1} = \| \mathrm A \mathrm B^{-1} \|_2 = \sqrt{\lambda_{\max} (\mathrm B^{-T} \mathrm A^T \mathrm A \mathrm B^{-1})}$$

The maximizer, $\mathrm y_{\max}$, is found at the intersection of the eigenspace associated with the maximum eigenvalue of $\mathrm B^{-T} \mathrm A^T \mathrm A \mathrm B^{-1}$ with the unit Euclidean sphere. Note that $\mathrm x_{\max} = \mathrm B^{-1} \mathrm y_{\max}$.

The minimum and the minimizer are now easy to find.

Answer 2

Squaring the $2$-norms, we obtain the quadratically constrained quadratic program (QCQP)

$$\begin{array}{ll} \text{extremize} & \| \mathrm A \mathrm x \|_2^2\\ \text{subject to} & \| \mathrm B \mathrm x \|_2^2 = 1\end{array}$$

We define the Lagrangian as follows

$$\mathcal L (\mathrm x, \lambda) := \| \mathrm A \mathrm x \|_2^2 - \lambda ( \| \mathrm B \mathrm x \|_2^2 - 1 ) = \mathrm x^T \mathrm A^T \mathrm A \mathrm x - \lambda ( \mathrm x^T \mathrm B^T \mathrm B \mathrm x - 1)$$

Taking the partial derivatives and finding where they vanish, we obtain

$$(\mathrm A^T \mathrm A - \lambda \, \mathrm B^T \mathrm B) \, \mathrm x = \mathrm 0_n \qquad \qquad \qquad \mathrm x^T \mathrm B^T \mathrm B \mathrm x = 1$$

Note that the former is a homogeneous linear system. As we are interested in non-zero solutions,

$$\det (\mathrm A^T \mathrm A - \lambda \, \mathrm B^T \mathrm B) = 0$$

Hence, we find the spectrum of the linear matrix pencil $\mathrm A^T \mathrm A - \lambda \, \mathrm B^T \mathrm B$, which gives us at most $n$ critical points on the ellipsoid $\mathrm x^T \mathrm B^T \mathrm B \mathrm x = 1$.