Multiple of Trace of Variable Matrix and Variable Vector

(ata) #1

I want to minimize sum of multiple y'*W*y*y'*b (depends on current sample’s W and b). This objective can be achieved in a for loop.

y is 5x1 variable vector, W is 5x5 given matrix and b is given constant.

The objective per sample is equal to trace(W*Y)*y'*b where Y =y*y'. Rewriting y as c'*Y_vec where Y_vec is vectorized version of Y, and rewriting trace(W*Y) as z'*Y_vec.

Then objective is = z'*Y_vec*c'*Y_vec or Y_vec'*z*c'*Y_vec, which is = trace(z'*c*YY) where YY = Y_vec*Y_vec'.

This turns the variable space from 5x1 to 25x25. I do not want this, I want my variable space to be 5x5 just like a regular SDP problem would do.

y can be extraxted from Y as Y(some_indices). Then, trace(W*Y)*y’*b = trace(W*Y)*Y(some_indices)'*b has 5x5 variable space of Y. However, this would produce disciplined convex programming error.

How can I solve this problem by optimizing 5x5 matrix?

(ata) #2

YY is 25x25 and I don’t want it to be my variable space. Instead, Y should be optimized…

(Mark L. Stone) #3

I don’t understand what problem you are trying to solve or what you are doing.

How are you dealing with Y = y*y'? That is non-convex and is not allowed by CVX. Are you using an SDP relaxation of that? Or somehow not dealing directly at all with y?

Is your problem convex? If so, how have you proved that? Or are you trying to use a convex (SDP) relaxation of your original problem?

If you have a valid formulation of your problem which CVX accepts, but you want to find a formulation with a smaller number of CVX variable elements, then show us the complete program - then at least we’ll know what problem you are solving.

(ata) #4

I want to solve a non-convex problem by SDP relaxation.

Original problem: minimize (f - x(4)*(A*x(1:3)+b))^2. x is variable vector that is 4x1 and f, A, b are given.

If x(4) is known the problem is of course convex…

(Mark L. Stone) #5

Please show us the complete formulation of the relaxed problem.

As regards dimensions, don’t you have

variable Y(5,5) symmetric
variable y(5,1)
[Y y;y' 1] == semidefinite(6)

But anyhow, why try to solve this using CVX? Why do you think or know the solution of the relaxed problem will solve the original non-convex problem? Have you considered a non-convex nonlinear solver, as you could call, for instance, from YALMIP?

(ata) #6

I can also use YALMIP but I want to practice and learn SDP relaxations. That’s the reason.

I am not sure about my formulation as it minimizes Y_vec'*K*Y_vec+Y_vec'*L. Y_vec here is 25x1 as I described earlier. It should be much easier, I am doing something wrong for sure.

How would you SDP relax the objective function: (f- x(4)*(A*x(1:3) + b))^2

(Mark L. Stone) #7

Johan at the YALMIP forum can give you better afvice on SDP relaxations than I can.