Set membership constraint in CVX

1

I have the following SDP where I optimize over positive semidefinite G

maximize \langle G, W\rangle
subject to
\ \ \ \ G\in C
\ \ \ \ G\geq 0

where W is given and C is a convex set. A similar problem is defined here. The set C in my case involves quantum entropies and the concavity of those entropies is what guarantees that C is convex.

For simplicity, let us consider the easiest of my cases. Let C = \{ X\, \vert\, S(X) \geq v\}, where S(X) = - \text{Tr}(X\log X). The concavity of S() guarantees that the set is convex.

How do I enforce such a constraint? I am currently using CVXPY but am happy to switch to MATLAB as well.

2

Please be more specific and write out the constraints defining the set C.

The crucial thing is not whether the author of a book or paper uses set membership to denote constraints, rather than writing them out, it is what the constraints are. So the similarity to the link to the book may be superficial and irrelevant.

Given that you mention quantum entropies and Tr(X logX), it sounds like CVXQUAD https://github.com/hfawzi/cvxquad might suit your needs. it adds several functions to CVX, including
quantum_entr(X) = -trace(X*logm(X)) , concave in X

So you could have quantum_entr(X) >= v
But your constraint is -quantum_entr(X) >= v, which is a non-convex constraint. So hopefully you just have a typo in your post.

There are other functions such as
quantum_rel_entr(X,Y) = trace(X*(logm(X)-logm(Y))) ,convex in (X,Y) . Beware though, the dimensions of the (several) matrices constrained to be semidefinite for quantum_rel_entr are each of the order 2n^2 by 2n^2 when X and Y are n by n; whereas the several are “only” of order 2n by 2n for quantum_entr. See the table on the top of p. 3 of https://arxiv.org/pdf/1705.00812.pdf

See my post Perspective of log det function, and CVX formulations of related log det problems using Quantum Relative Entropy from CVXQUAD for examples of how to formulate and solve various matrix perspective and log_det related functions using CVXQUAD in CVX.

You may also be interested in the latter sections of CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions . Note, there is no need for you to use CVXQUAD’s exponential.m replacement if you are trying to use the “quantum” related functions in CVXQUAD.

1 Like
3

Thanks Mark, yes I had a typo with the minus sign in my question. It’s fixed now. Thank you for these resources - I’ll try to put them to work and see if I am able to proceed and if not, I’ll repost the exact problem here.

4

Please report your results, one way or another, using the quantum-related functions in CVXQUAD. Beware of runtime and memory utilization.

1 Like
5

Thanks for the help so far. I’m having trouble running even the basic examples copy pasted from CVXQUAD. For example, the code below

na = 2; nb = 2;
rho = eye(4)/4; 

cvx_begin sdp
    variable tau(na*nb,na*nb) hermitian;
    minimize (quantum_rel_entr(rho,tau)/log(2));
    tau >= 0; trace(tau) == 1;
    Tx(tau,2,[na nb]) >= 0; % Positive partial transpose constraint
cvx_end

is copied from here with a minor tweak to replace randRho with the identity matrix. I receive the error

Array indices must be positive integers or logical values.

Error in cvx_extract (line 552)
    Pd(Pr) = false;

Error in cvx_solve (line 26)
[ At, cones, sgn, Q, P, exps, dualized ] = cvx_extract( shim.config, shim.name );

Error in cvx_finish

Error in cvx_end (line 11)
    evalin( 'caller', 'cvx_finish' );

Error in example (line 9)
cvx_end
6

Please show the results of cvx_version. Use CVX 2.2, not CVX 3.0beta.

Can you run this example in the CVXQUAD main page?

n = 4;
M = randn(n,n);
M = M*M';
cvx_begin
  variable X(n,n) symmetric
  minimize quantum_rel_entr(M,X)
  subject to
diag(X) == ones(n,1)
cvx_end
8

Ah I see - yes I had 3.0beta running. I am able to run that example with 3.0beta with Mosek though.

9

I did include this in my CVXQUAD post linked earlier

Note: CVX 3.0beta is not really recommended to anyone due to its numerous bugs. Do NOT use CVXQUAD with CVX 3.0beta. .

1 Like
10

Thank you for your help Mark - I’ll continue with Version 2.2 :slight_smile: