7
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Feb 17 '15 at 7:49
  • $\begingroup$ @D.W., could you just use the laplacian of the adjacency matrix? $L$ is always positive semidefinite. $\endgroup$ – Nicholas Mancuso Feb 17 '15 at 17:50
  • $\begingroup$ @NicholasMancuso, I don't know! Interesting idea. $\endgroup$ – D.W.♦ Feb 17 '15 at 17:53
  • $\begingroup$ 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! $\endgroup$ – megas Feb 17 '15 at 19:59
  • $\begingroup$ 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. $\endgroup$ – megas Feb 17 '15 at 20:37
2
$\begingroup$

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

Improve this answer
$\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.