# Hardness of a constrained quadratic maximization

Consider the following quadratic maximization: \begin{align} \max_{\mathbf{x} \in \mathcal{X}} &\quad\mathbf{x}^{T}\mathbf{A}\mathbf{x} \end{align} with \begin{align} \mathcal{X} = \lbrace \mathbf{x} \in \mathbb{R}^{n} :~ \|\mathbf{x}\|_{2}=1, \|\mathbf{x}\|_{0}\le k \rbrace, \end{align} where $\mathbf{A}$ is a positive semidefinite matrix and $k \le n$ is a sparsity parameter. This problem is NP-hard, by a reduction from the max-clique problem.

I am interested in a similar problem obtained by imposing additional structure on $\mathcal{X}$. In particular, assume that the $n$ variables in $\mathbf{x}$ are partitioned into $k$ disjoint groups. We restrict the feasible set to unit-length vectors $\mathbf{x}$ with one active variable per group. That is, $\mathcal{X}$ contains again $k$-sparse vectors, but the support cannot be arbitrary; it contains (at most) one nonzero entry for each of the $k$ groups.

Note that the feasible set in the modified problem is a subset of the previous maximization, but the number of feasible supports can still be exponential in the number of variables $n$ (for appropriately chosen $k$).

I suspect that the modified problem is also NP-hard. Any ideas on how to show that (or disprove)? Feel free to share your intuition.

• Without the semidefiniteness requirement, this should be NP-hard by reduction from independent set. Say $G$ is a graph with $N$ vertices. Build an instance of your problem with $2N$ variables and $N$ groups, one group per vertex $v$ of $G$. Setting the first variable in $v$'s group to 1 is like adding $v$ to the independent set; setting the 2nd variable is like not adding $v$ to the set. Now you can form a matrix $A$ that minimizes the number of edges $(v,w) \in E$ such that both $v,w$ are in the set. But will this $A$ be semidefinite? I don't know. – D.W. Feb 17 '15 at 7:49
• @D.W., could you just use the laplacian of the adjacency matrix? $L$ is always positive semidefinite. – Nicholas Mancuso Feb 17 '15 at 17:50
• @NicholasMancuso, I don't know! Interesting idea. – D.W. Feb 17 '15 at 17:53
• If the only problem is that the argument $\mathbf{A}$ is not positive semidefinite (PSD) ($\mathbf{A}$ is only symmetric), then it should be fine: we can always solve the maximization on $\mathbf{A}+|\lambda_{min}(\mathbf{A})| \cdot \mathbf{I}$. I will take a look at the proposed approach and let you know! – megas Feb 17 '15 at 19:59
• I have some trouble seeing how to adapt this approach to my problem. For me, $\mathbf{x}$ is not binary; it is a unit-norm real vector, allowed to have negative entries as well, which introduces some difficulty in designing $\mathbf{A}$. Unless, am I missing something obvious? But I did like the idea of the $2N$ variables. I will keep thinking whether I can figure something out building on it. – megas Feb 17 '15 at 20:37

• Given $k$-partite graph $G=(V_{1}, \dots, V_{k}, E)$, does $G$ contain a $k$-clique.
Let $\mathbf{A}$ denote the adjacency matrix of $G$. Let $S$ be an arbitrary set of $k$ vertices and $\mathbf{A}_{S}$ denote the principal submatrix corresponding to $S$, i.e. $\mathbf{A}_{S}$ is the $k\times k$ adjacency of the graph induced by $S$. If the vertices in $S$ form a $k$-clique in $G$, then all off-diagonal entries of $\mathbf{A}_{S}$ are equal to $1$, and its principal eigenvalue $\lambda_{1}(\mathbf{A}_{S}) = k-1$. In any other case, that is, if $S$ is not a $k$-clique, then $\lambda_{1}(\mathbf{A}_{S}) < k-1$. Finally, note that since $G$ is $k$-partite, a $k$-clique (if one exists) will contain a single vertex from each of the sets $V_{i}$, $i=1,\dots,k$.
Let $\mathbf{A}^{\prime} = \mathbf{A} + |\lambda_{n}(\mathbf{A})|\cdot\mathbf{I}$, where $\lambda_{n}(\mathbf{A})$ is the smallest eigenvalue of $\mathbf{A}$; $\mathbf{A}^{\prime}$ is a PSD matrix. Further, consider $k$ disjoint groups of variables corresponding to the sets $V_{1}, \dots, V_{k}$ of $G$. We solve the quadratic maximization with input $\mathbf{A}^{\prime}$ and the specified groups of variables. The maximum objective value will be equal to $k-1 + |\lambda_{n}(\mathbf{A})|$ if and only if $G$ contains a $k$-clique.