2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The unit Euclidean sphere is not convex, of course. Hence, one can immediately conclude that the problem is non-convex. $\endgroup$ – Rodrigo de Azevedo Jan 31 '19 at 20:53
  • $\begingroup$ Also, is $x$ a column vector or a row vector? $x M_i x^T$ implies it is a row vector. $\endgroup$ – Rodrigo de Azevedo Jan 31 '19 at 20:54
  • $\begingroup$ @RodrigodeAzevedo: but trivially, changing the sphere to the ball does not change the problem, but now the domain is convex $\endgroup$ – Anthony Quas Feb 1 '19 at 3:13
  • $\begingroup$ 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]...$ $\endgroup$ – Mickybo Yakari Feb 1 '19 at 9:32
  • 2
    $\begingroup$ 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). $\endgroup$ – Nathaniel Johnston Feb 1 '19 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.