Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

Here is an approach which may get you good results but for which I have no guarantees.

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.