2
$\begingroup$

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.

Does anyone know 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.

Improve this question
$\endgroup$
4
  • $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$
    – Julian Kuelshammer
    Commented Jun 26, 2013 at 6:16
  • $\begingroup$ Is there a chance the $M_{i}$s are copositive? $\endgroup$
    – Felix Goldberg
    Commented Jun 26, 2013 at 9:14
  • $\begingroup$ 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. $\endgroup$
    – David Ketcheson
    Commented Oct 7, 2013 at 10:02
  • $\begingroup$ It is not a QCQP because the objective is linear. Positive definiteness has to do with the QCQP's convexity (or lack thereof). $\endgroup$
    – Rodrigo de Azevedo
    Commented Nov 13, 2017 at 8:33

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .