1
$\begingroup$

I recently encountered the following optimization problem:

$\max \|AX\|_F^2$

subject to: $X\succeq0$ and $Xb_i\leq c_i$ for a collection of $T$ conditions: $i=1,\ldots,T$.

Matrices $A$ and $X$ are square and symmetric, and $c$ is a column vector.

I know from Wikipedia that the general "quadratically constrained quadratic optimization" problem is NP-hard. However, can this special form be solved efficiently?

Thanks a lot!

$\endgroup$
3
  • $\begingroup$ What does $BX \le c$ mean with matrices $B$, $X$ and a vector $c$? $\endgroup$
    – gerw
    Jul 31, 2015 at 20:03
  • $\begingroup$ Sorry, typo corrected. $\endgroup$
    – yuanz07
    Jul 31, 2015 at 20:20
  • 1
    $\begingroup$ The problem is simply not convex. $\endgroup$ Aug 1, 2015 at 7:25

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.