Let $A \in \mathbb{R}^{n \times n}$, $A = A^\top$, $B \in \mathbb{R}^{m \times n}$, and $\mathcal{C} \subset \mathbb{R}^n$ be a compact, convex set.
For $A$ not negative semidefinite, how to globally solve the following optimization problem?
$$\displaystyle \max_{ x \in \mathcal{C}} \ x^\top A x - || B x||_1$$
So we're assuming that $A$ is symmetric, but $A$ may have some positive and some negative eigenvalues? –  littleO Nov 9 '12 at 20:38
Yes, $A$ is not defined. If $A \preccurlyeq 0$ then we can get the global optimal because it would be a convex optimization problem (by changing the sign). –  Adam Nov 9 '12 at 20:40
Does $C$ have a characterization other than just compact? Also, do you mean $A$ to have at least one positive eigenvalue? –  copper.hat Nov 9 '12 at 20:46
Is $C$ convex? (You have the convex-optimization tag.) –  copper.hat Nov 9 '12 at 21:03
Oh, yes, I forgot: $\mathcal{C}$ is convex! –  Adam Nov 9 '12 at 21:10