3
$\begingroup$

I'm not asking for a solution, I just need to know what type of optimization is this problem?. Find $\mathbf{q}$ that minimizes the following: $$\min_\mathbf{q}{|\mathbf{BXq|^2}}$$ $$\, \mbox{s.t}\ q_i^Hq_i=1, i=1,2,...,N$$ $\mathbf{B}$ is given and is $M \times N$, $\mathbf{X}$ is an $N \times N$ diagonal matrix and is given, $\mathbf{q}$ is an $N \times 1$ vector with entries $q_i$ and $|.|$ denotes the absolute

The objective function can be simplified to: $\mathbf{q^HX^HB^HBXq=q^HGq}$ where $\mathbf{G=X^HB^HBX}$. The opimization problem becomes: $$\min_\mathbf{q}({\mathbf{q^HGq}})$$ $$\, \mbox{s.t}\ q_i^Hq_i=1, i=1,2,...,N$$I would be grateful if someone would let me know what kind of optimization is this problem. Any references would help too.

$\endgroup$
2
$\begingroup$

This is a quadratic program with quadratic constraints, although the constraints are fairly simple in this case, since they correspond to the unit sphere.

$\endgroup$
  • $\begingroup$ Thanks for the answer Joe, this is really helpful now I know what type of optimization it is. $\endgroup$ – user63552 Mar 25 '13 at 3:44
  • $\begingroup$ While your classification is correct, I don't agree that they belong to unit sphere which happens only if the norm is one. $\endgroup$ – dineshdileep Mar 25 '13 at 9:09
0
$\begingroup$

As user Joe Turner pointed out in his answer, it is indeed a Quadratic Constrained Quadratic Programming (QCQP) programming. But, it is a non-convex one. I am not sure if you can find a solution via Lagrangian method. If you are inclined towards numerical solutions, one attractive way of solving the problem would be resorting to something known as Semi Definite Relaxation for Quadratic Constrained Quadratic Problems. You can easily find references on it from google.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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