4
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note: the approximation is for the m=1 case, which is the same as computing the $\ell_\infty$ to $\ell_2$ operator norm, and closely related to Grothendieck's inequality. I haven't thought about an approximation algorithm for the general case, although I am fairly confident that the m=1 case ideas will apply. $\endgroup$ – Sasho Nikolov Aug 3 '17 at 14:05
  • $\begingroup$ Indeed MaxCut problem on any graph $G=(V,E)$ with unit weight at edges is formulated as convex program; it is required to find $\max\|x\|$, subject to $x$ being an extremal point of the polytope $$EP=\{x \in R^V: x(S)\le f(S), S \subset V, x(V)=0\},$$ where $f(S)$ is the submodular cut function defined on subsets of $V$. $\endgroup$ – Sharifov F. A. Mar 4 at 15:06
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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