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

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

share|improve this question
    
I don't think that there will be a closed-form solution; this problem will demand a numerical solution. –  Suvrit Jun 22 '11 at 22:58
add comment

1 Answer

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.

share|improve this answer
    
By the way, question 6166 may be related. mathoverflow.net/questions/6166/… –  Pait Jun 23 '11 at 17:01
    
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? –  Saeed Jun 23 '11 at 17:45
    
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".) –  Pait Jun 27 '11 at 13:22
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.