[Solved]: Hardness of a constrained quadratic maximization

Problem Detail: 

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.

Asked By : megas

Answered By : megas

(I have found the answer to my question, so I am sharing a sketch here).

The quadratic maximization can be shown to be NP-hard by a reduction from the following problem:

• Given $k$-partite graph $G=(V_{1}, \dots, V_{k}, E)$, does $G$ contain a $k$-clique.

Note that the latter problem is a (seemingly) special case of the max-clique problem restricted to a particular family of graphs. It can however be shown that it is also NP-complete by a reduction from the general max-clique problem itself (See here).

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/38474

3.2K people like this

 Download Related Notes/Documents