3
$\begingroup$

I have the following quadratic maximization problem

$\max_{\mathbf X} \quad tr(\mathbf A\mathbf X\mathbf B\mathbf X^H)+tr(\mathbf C\mathbf X)+tr(\mathbf C^H\mathbf X^H)$

subject to the quadratic constraint $tr(\mathbf X \mathbf X^H)\leq r$ where $\mathbf A, \mathbf B \succeq \mathbf 0$ (positive semi-definite) and $\mathbf C$ is any matrix (not necessarily hermitian).

I am looking for a closed-form solution/structure for $\mathbf X$ or even a nice upper bound. A simple upper bound of it can be found using inequality results, so we know that the problem has a finite maximum.

I would really appreciate any help/comment/solution :)

Thanks in advance,

Saeed

$\endgroup$
1
  • $\begingroup$ I don't think that there will be a closed-form solution; this problem will demand a numerical solution. $\endgroup$
    – Suvrit
    Jun 22, 2011 at 22:58

1 Answer 1

1
$\begingroup$

Your problem is in the form

$\max_x f(x)$ subject to $g(x) < 0$, where $x$ is the set of components $x_i^j$ of the matrix $X$.

Use one Lagrange multiplier to write $f(x) + \lambda g(x)$. Both nonlinear terms are quadratic, so this is the most favorable case for the purpose of obtaining solutions. To take the derivative of the expression above with respect to the set of unknowns $x$, index notation as in tensor calculus could be helpful. Then you are in the standard form of constrained optimization.

$\endgroup$
3
  • $\begingroup$ By the way, question 6166 may be related. mathoverflow.net/questions/6166/… $\endgroup$
    – Pait
    Jun 23, 2011 at 17:01
  • $\begingroup$ Thanks Pait, What I understood is that solving the KKT conditions gives me the solution and I can obtain it by define the scalar problem. However, the problem is not convex as it is maximization of a convex function, so it is a non-convex problem and solution to Lagrangian function might be local optimum. The question is that does strong duality hold for this problem or not? $\endgroup$
    – Saeed
    Jun 23, 2011 at 17:45
  • $\begingroup$ The strong duality theorem is valid for linear programming problems; it is not obvious that it applies to your quadratic one. Good question! On the other hand after differentiating you do end up with linear equations. The necessary conditions are as explicit as they get. Yes, the conditions give critical points which may or may not be maxima. (I am not sure what you mean by "the scalar problem".) $\endgroup$
    – Pait
    Jun 27, 2011 at 13:22

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.