# non convex quadratic optimization

Hi I would like to optimize the following system: $$\min_{q,\|q\|=1} \sum_i^n |q^T M_i q|$$

More details:

• the size of the unknown vector q is $4\times 1$,
• M_i is a matrix of size $4\times 4$. It is symmetric but not positive definite,
• $n$ is about $200$ in my case.

Anyone knows how to solve this problem?

It might be related to the following problem: $$\max_{q,\|q\|=1} q^T M q$$ The solution is simply the eigenvector of $M$ associated to the highest eigenvalue.

But in our system, the absolute function and the sum make the problem more complicated.

I also tried reformulating the system as: $$\min_{q,t} \sum_i^n t_i \text{ subject to }|q^T M_i q|\leq t_i\text{ for all }i=1,\dots,n\text{ and }\|q\|=1$$ but it did not really help.

It is not a standard quadratically constrained quadratic program (QCQP) because the matrices are not positive definite.

-
For some basic information about writing math at this site see e.g. here, here, here and here. – Julian Kuelshammer Jun 26 '13 at 6:16
Is there a chance the $M_{i}$s are copositive? – Felix Goldberg Jun 26 '13 at 9:14
I suspect that a good nonlinear programming solver would give you an accurate (floating-point) solution fairly quickly (for instance, try MATLAB's fmincon). This ignores all the structure of the problem, but it will probably work. – David Ketcheson Oct 7 '13 at 10:02

Letting $Q = qq^T$ you can rewrite your constraints as $-t_i \leq \text{Trace}(M_iQ)\leq t_i$. Requiring $Q$ to factor as $qq^T$ for some $q$ of unit norm is the same as saying that $Q$ is positive semidefinite, has unit trace, and rank one. Dropping the rank one constraint gives a semidefinite programming relaxation and hence an efficiently computable lower bound to the objective value.
If you're lucky, the optimal $Q$ may be rank one, in which case you have the optimal solution to the original problem. If not, the eigendecomposition of the optimal $Q$ may suggest decent candidate solutions yielding objective values close to this bound.