I have a maximization problem, where I replaced some vector variables with their Positive semidefinite matrices. I am solving it using cvx.
For example, if I had in the objective: |n^Hm|^2, I replaced it with the real(trace (NM)). where N=nn^H and M = mm^H, n and m are complex vectors,. I have not added a rank-1 constraint for the two matrices. Then after solving, I used the Cholesky decomposition to get the vectors.
Is it possible that the objective function I get after this process will be higher than the optimal solution of the original problem?
A semidefinite relaxation whose solution is not rank one, provides an optimistic bound (upper bound in the case of maximization) on the optimal objective of the original problem. So yes, the relaxed problem might have a higher optimal objective value than the original. Semidefinite relaxation is not a magic cure-all which transforms non-convex problems 100% of the time into easier to solve convex problems.
If Cholesky decomposition is successful, perhaps that suggests that the matrix is full rank, and therefore not rank one?
Thanks for your answer.
Yes Cholesky decomposition was successful.
So, what is better than semidefinite relaxation to do?
It is better to do this relaxation but with adding a rank one constraint. This constraint can be replaced by adding a penalty to the objective funntion which is the difference between the nuclear and spectral norm of the matrices?
There’s no magic formula to make non-convex problems into easy to solve convex problems. How you deal with non-convexity is up to you.
One option is to use a non-convex solver on the original non-convex problem, for instance, under YALMIP. If the original problem is a non-convex QCQP (quadratically-constrained quadratic program), you can use Gurobi or a general global non-convex solver to try to get a globally optimal solution. Or use a local solver to try to get a local optimum.