Maximize the Euclidean norm of a matrix times a vector on unit sub-spheres 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$.
 A: 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.
A: 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\|}.
$$
A: $$\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$.
