Hi,
I am trying to solve the following problem:
min c’*x
s.t. [I R*z ; z’*R’ v(x)] positive semidefinite
R’R = sum(b_jQ_j)
where z, b_j known and v(x) is known in x, and where it is assumed that all Q_j as well as sum(b_j*Q_j) is positive semidefinite. Ultimately I need to retrieve the Q_j’s, so I can’t just solve the problem in R. But I also cannot figure out how to set the above equality constraint, as cvx constantly rejects it.
How can I do this?
Leaving aside the Inon-convexity of Cholesky factorization, t’s not clear to me what mathematical problem you are trying to solve. Is it well-defined? Id Q_j uniquely determninable (at optimum of problem)? Relations between the variables? If v(x) is not affine in x, the semidefinite constraint will not be allowed.
To use CVX, you need a well-defined problem, and it must be convex.
Thanks for your reply Mark.
The problem is a lot bigger and has many more variables than I’ve written here, as I tried to simplify it. Yes, it is well-defined and v(x) is affine in x. The uniqueness of Q_j, maybe not, but that’s actually ok in the model- it just needs to return a feasible one.
The core problem is that I have a quadratic constraint with quadratic term matrix sum(b_j Q_j), b_j known. With each Q_j and that matrix also PSD (this is part of the model) I then use a cholesky factorisation to rewrite the quadratic constraint with Schurs complement. Hence why I write R’*R = sum(b_j Q_j). I then have a semidefinite constraint in place of it.
However, since this is the only constraint that uses Q_j, if I solve the problem in R, I cannot return Q_j, nor can I enforce the equality constraint R’*R = sum(b_j Q_j) ; and if I solve the problem in Q_j, I cannot write out the matrix via Schurs, as CVX doesn’t support sqrtm.
So how can I solve this problem?
I still don’t understand what your problem is, to include what’s happening with the Schur Complement (that’s to deal with z’R’Rz ?) . This is your first mention of sum(b_j Q_j), b_j , but if b_j are known, as per your first post, then setting this equal to a known quantity is just an affine constraint, not quadratic (in the variables being optimized). Of course you can impose a semidefinite constraint on sum(b_j* Q_j) without use of Cholesky factorization, but then you would not have a connection to the previous (Schur Complement?) constraint.
I will say again, your problem must be convex in order to use CVX - proving it is convex is your responsibility… If it is not, you need another tool which can handle non-convexities, such as maybe PENLAB if there are semidefinite constraints. But again, I don’t understand your problem, and have not reached a determination whether there’s a convex formulation (exact, or perhaps relaxing some constraint(s)).
Please read and take to heart Why isn't CVX accepting my model? READ THIS FIRST! .
I think it might be easiest to ask: how would you solve the following problem in CVX?
Min c’*x
S.t. [I R*z; z’*R’ v(x)]
R’*R = sum(b_j * Q_j)
Where c, b_j, and z all known, v(x) affine in x, and optimisation variables are x and Q_j size NxN?
I have verified the problem is indeed a convex programming problem. R is not an optimisation variable; it is a dummy variable that allows me to write the problem in the above form. And I cannot write it another way.
Thankyou.
It would be easier if you showed the whole problem instead of making us guess what reformulations of the simplified version will work for the complete original. The simplified problem boils down to v(x)\geq z^T(\sum b_jQ_j)z,\ \sum b_jQ_j\succeq 0 by Schur complement, but I guess from one of your posts that is not what you want.