Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres

Question

For $X = (x_1^T,\ldots,x_N^T)^T \in \mathbb{R}^{Nm \times 1}$, where $x_i \in \mathbb{R}^{m \times 1}$ for $i \in \{1,\ldots,N\}$, $A \in \mathbb{R}^{r \times Nm}$, and $r \geq Nm$, I want to obtain a closed form solution of

$$\max_{X \in \mathbb{R}^{Nm}}\{\|AX\|: \|x_i\|^2=1\}$$

where $\|\cdot\|$ denotes the Euclidean norm. I know how to find a closed form solution of

$$\max_{X \in \mathbb{R}^{Nm}}\{\|AX\|: \|X\|^2=1\}$$

that is, when $\|X\|^2=1$. However, I do not see how to solve it when we have $\|x_i\|^2=1$.

Answer 1

You cannot hope for anything like a closed form solution, or even an exact efficient algorithm for this problem, because it is NP-hard. The reduction is from the max-cut problem. Let's look at the special case $m=1$. Let $G = (V, E)$ be a graph, and orient the edges in some arbitrary way. Let $A$ be the edge-by-vertex incidence matrix of $G$, i.e. the rows of $A$ are indexed by edges and the columns by vertices, and $a_{e, v}$ is $1$ if $v$ is the tail of $e$, $-1$ if $v$ is the head of $e$, and $0$ otherwise. Then it's easy to check that for any $x \in \mathbb{R}^V$, $\|Ax\|^2 = \sum_{(u,v) \in E}{(x_u - x_v)^2}$. If $x \in \{-1, 1\}^V$ as in the $m=1$ case of your problem, then $\|Ax\|^2 = 4e(S, \bar{S})$, where $e(S, \bar{S})$ is the number of edges cut by the set $S = \{v: x_v = 1\}$.

You can find a constant factor approximation algorithm (due to Nesterov) in Chapter 6.3. of the Williamson and Shmoys book.

Answer 2

You can write $AX=\sum_{i=1}^N A_i x_i$ with $A_i\in \mathbb{R}^{r\times m}$. Then we have $$ \|AX\|^2=(AX)^TAX=\sum_{i,j} x^T_i A_i^TA_jx_j. $$ The condition for a critical point is $$ A_i^TAX=\alpha_ix_i $$ for some $\alpha_1,\dots,\alpha_N \in \mathbb{R}$. One possibility to find the maximizer is to do the fixpointiteration $$ x_i=\frac{A_i^TAX}{\|A_i^TAX\|}. $$

Answer 3

$$\mathrm A \mathrm x = \begin{bmatrix} \mathrm A_1 & \mathrm A_2 & \cdots & \mathrm A_n\end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}$$

where $\mathrm x_1, \mathrm x_2, \dots, \mathrm x_n \in \mathbb R^m$ are the optimization variables. Hence,

$$\| \mathrm A \mathrm x \|_2^2 = \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}^\top \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n\\ \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}$$

Thus, we have the following (non-convex) quadratically constrained quadratic program (QCQP)

$$\begin{array}{ll} \text{maximize} & \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}^\top \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n\\ \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}\\ \text{subject to} & \| \mathrm x_1 \|_2^2 = 1\\ & \| \mathrm x_2 \|_2^2 = 1\\ & \qquad\vdots \\ & \| \mathrm x_n \|_2^2 = 1 \end{array}$$

Let the Lagrangian be

$$\mathcal L (\mathrm x_1, \dots, \mathrm x_n, \mu_1, \dots, \mu_n) := \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix}^\top \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n\\ \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix} -\\- \sum_{k=1}^n \mu_k \left( \| \mathrm x_k \|_2^2 - 1 \right)$$

Taking all the partial derivatives of the Lagrangian and finding where they vanish, we then obtain the following homogeneous linear system

$$\begin{bmatrix} \mathrm A_1^\top \mathrm A_1 - \mu_1 \mathrm I_m & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 - \mu_2 \mathrm I_m & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n - \mu_n \mathrm I_m \end{bmatrix} \begin{bmatrix} \mathrm x_1\\ \mathrm x_2\\ \vdots \\ \mathrm x_n\end{bmatrix} = \begin{bmatrix} 0_m\\ 0_m\\ \vdots \\ 0_m\end{bmatrix}$$

and the equality constraints $\| \mathrm x_1 \|_2^2 = \| \mathrm x_2 \|_2^2 = \cdots = \| \mathrm x_n \|_2^2 = 1$. To satisfy these $n$ equality constraints, we cannot have just the solution $\mathrm x = 0_{mn}$. Thus, the matrix must be singular, i.e.,

$$\det \begin{bmatrix} \mathrm A_1^\top \mathrm A_1 - \mu_1 \mathrm I_m & \mathrm A_1^\top \mathrm A_2 & \cdots & \mathrm A_1^\top \mathrm A_n\\ \mathrm A_2^\top \mathrm A_1 & \mathrm A_2^\top \mathrm A_2 - \mu_2 \mathrm I_m & \cdots & \mathrm A_2^\top \mathrm A_n\\ \vdots & \vdots & \ddots & \vdots\\\mathrm A_n^\top \mathrm A_1 & \mathrm A_n^\top \mathrm A_2 & \cdots & \mathrm A_n^\top \mathrm A_n - \mu_n \mathrm I_m \end{bmatrix} = 0$$

which produces a polynomial equation of degree $m n$ in the $n$ Lagrange multipliers $\mu_1, \mu_2, \dots, \mu_n$.