# Quartic optimization problem over the unit Euclidean sphere

I want to solve following optimization problem in $$x \in \mathbb R^n$$.

$$\begin{array}{ll} \text{maximize} & \displaystyle\sum_i(x M_i x^T)^2\\ \text{subject to} & \|x\|_2 = 1\end{array}$$

where matrices $$M_i$$ are not positive semidefinite.

Is it even convex problem and is there a solution in closed form?

• The unit Euclidean sphere is not convex, of course. Hence, one can immediately conclude that the problem is non-convex. – Rodrigo de Azevedo Jan 31 '19 at 20:53
• Also, is $x$ a column vector or a row vector? $x M_i x^T$ implies it is a row vector. – Rodrigo de Azevedo Jan 31 '19 at 20:54
• @RodrigodeAzevedo: but trivially, changing the sphere to the ball does not change the problem, but now the domain is convex – Anthony Quas Feb 1 '19 at 3:13
• Indeed, $x$ has to be a row vector in the original notation. Has the OP tried to use the method of Lagrange multipliers? Here is what I just scribbled down for $l\in\{1,...,n\}$, $\frac{\partial}{\partial x_{l}}\big(\sum_{i=1}^{m}\big(x^{T}M^{(i)}x\big)^{2}\big)=2\sum_{i=1}^{m}\big(x^{T}M^{(i)}x\big)\times\sum_{k=1}^{m}\Bigg[x_{l}^{2}M_{ll}^{(k)}+2\sum_{j\neq l}^{n}M_{lj}^{(k)}x_{j}\Bigg]...$ – Mickybo Yakari Feb 1 '19 at 9:32
• I forget the details, but I believe this is NP-hard even if each $M_i$ is a symmetric 0-1 matrix. You can spot this optimization in arxiv.org/pdf/0810.4507.pdf for example (and then likely trace back the references to the proper original source). – Nathaniel Johnston Feb 1 '19 at 12:11