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.

$\endgroup$
4
  • $\begingroup$ For some basic information about writing math at this site see e.g. here, here, here and here. $\endgroup$ Jun 26, 2013 at 6:16
  • $\begingroup$ Is there a chance the $M_{i}$s are copositive? $\endgroup$ 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$ 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$ Nov 13, 2017 at 8:33

1 Answer 1

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.

$\endgroup$

Your Answer

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

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