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

How to use CVXQUAD’s better performing and more reliable Pade Approximant instead of CVX’s unreliable Successive Approximation method:

Update as of the release of CVX 2.2 in January 2020: Except for use of Quantum (Matrix) Entropy and Matrix Logarithm related functions addressed later in this post, none of the following, to include reformulation, is necessary if CVX 2.2 is used with Mosek 9.x or higher as solver, in which case CVX will utilize Mosek’s native exponential cone capability, thereby avoiding CVX"s Successive Approximation method and obviating the benefit of using CVXQUAD (note that in such case, CVX 2.2 still issues a warning about the Successive Approximation method being used, but issuance of the warning is a bug, because the Successive Approximation method is not actually used). If CVX2.2 + Mosek 9.x is used, I recommend not installing CVXQUAD’s exponential.m replacement, except if you wish to compare performance with and without CVXQUAD.

A) Install CVXQUAD and its exponential.m replacement for CVX’s version per the directions at https://github.com/hfawzi/cvxquad . Be sure to add the cvxquad-master directory to the MATLAB path. If you have already invoked CVX’s Successive Approximation method prior to installing CVXQUAD;s exponential.m replacement, I recommend you start a new MATLAB session before running a problem for which CVXQUAD will be invoked, although I am not sure that is necessary.

B) If your CVX program is

GP mode

or uses only

log_sum_exp(cvx_expression)
entr(cvx_expression)
rel_entr(cvx_expression)
kl_div(cvx_expression)
det_rootn(cvx_expression)
{x,y,z} == exponential(1) % explicit exponential cone construct

and none of

log(cvx_expression)
exp(cvx_expression) or a^cvx_expression , where a > 0
sum_log(cvx_expression)
log_prod(cvx_expression)
log_det(cvx_expression)

then no modifications are needed to your program, and CVXQUAD’s Pade Approxiimant will be used instead of CVX’s Successive Approximation method:

Otherwise, modify your CVX program as follows in order for CVXQUAD’s Pade Approxiimant to be used instead of CVX’s Successive Approximation method for log, exp, a^cvx_expression, sum_log, log_prod, log_det.

Replace
log(cvx_expression)
with
-rel_entr(1,cvx_expresion)

++++++++++++++++++++

Replace
exp(cvx_expression) <= z
with either
{cvx_expression,1,z} == exponential(1)
or
cvx_expression + rel_entr(1,z) <= 0

++++++

Replace
exp(cvx_expression)
with
z
and add either:

variable z % this line must be before z is used
{cvx_expression,1,z} == exponential(1)

or

variable z % this line must be before z is used
cvx_expression + rel_entr(1,z) <= 0

++++++

Re-write a^cvx_expression , where a > 0, as exp(log(a)*cvx_expression)., then use the above.

++++++++++++++++++++

Replace
sum_log(cvx_expression)
with
sum(-rel_entr(1,cvx_expression))

++++++++++++++++++++

Replace
log_prod(cvx_expression)
with
sum(-rel_entr(1,cvx_expression))

++++++++++++++++++++

Replace
log_det(cvx_expression) >= t where cvx_expression is an n by n matrix
with

    variable u     
    -rel_entr(1,u) >= t/n
    det_rootn(cvx_expression) >= u

++++++

Replace
log_det(cvx_expression) , where cvx_expression is an n by n matrix
with
z
and add

    variables u  z % this line must be before u or z are used
    -rel_entr(1,u) >= z/n
    det_rootn(cvx_expression) >= u

++++++

Note: A simpler to write reformulation (NOT RECOMMENDED) can be used:
Replace
log_det(cvx_expression)
with
-quantum_rel_entr(eye(size(cvx_expression)),cvx_expression)

However, as discussed below, use of quantum_rel_entr is computationally demanding. Formulation using quantum_rel_entr consumes much more computational resources than that used by preceding formulations.

==========================

If after installing CVXQUAD and its exponential.m replacement, and making modifications, if required, to your program as described above, it turns out that CVX’ Successive Approximation method is still invoked, as evidenced by

  Cones | Errors |
Mov/Act | Centering Exp cone Poly cone | Status

output, that means either a) CVXQUAD and its exponential.m replacement are not installed correctly, b) you did not make the CVX program modifications correctly, c) I made a mistake in the above, or d) there is some other exponential cone item in your CVX code which I did not include in the list (please post to this thread in that case).

==========================

What CVXQUAD does:
CVXQUAD creates several 2 by 2 LMIs to replace the exponential cones in the original formulation. CVX will reformulate these LMIs into Second Order Cone constraints before passing to the solver. Therefore any SOCP solver which can be called by CVX can be used, unless the problem also has semidefinite or binary or integer constraints:

Solvers which can be used (cvx_solver):
The following applies to CVX programs in which CVXQUAD’s Pade Approiimant is invoked:

A) If CVX program contains no semidefinite, binary or integer constraints,
Mosek, Gurobi, SDPT3, SeDuMi, ECOS, SCS may be used as cvx_solver, i.e., any SOCP solver.

B) If CVX program contains semidefinite constraints, but no binary or integer constraints,
Mosek, SDPT3, SeDuMi, SCS may be used as cvx_solver, i.e., any SDP solver.

C)) If CVX program contains binary or integer constraints, but no semidefinite constraints,
Mosek or Gurobi may be used as cvx_solver, i.e., any MISOCP solver.

Disclaimer, I know of no reason why CVXQUAD’s Pade Approximation should not work correctly if there are integer or binary variables, but this has not been fully verified.

D) If CVX program contains semidefinite constraints and binary or integer constraints,
there is no suitable solver currently available under CVX.

===========================

Quantum (Matrix) Entropy and Matrix Logarithm related functions: As documented at https://github.com/hfawzi/cvxquad CVXQUAD makes several *Quantum (Matrix) Entropy and Matrix Logarithm related functions available. See “Semidefinite Approximations of the Matrix Logarithm” by Hamza Fawzi, James Saunderson, Pablo A. Parrilo, available at https://link.springer.com/article/10.1007/s10208-018-9385-0 , or in free preprint form at https://arxiv.org/abs/1705.00812

Solver requirements: Using CVXQUAD’s Pade Approximation replacement for (scalar) exponential cone functions, as described in preceding sections of this post, corresponds to matrix dimension n = 1, i.e., 1 by 1 matrix, in which case all these quantum (matrix) functions reduce exactly to their scalar counterparts. When the matrix dimension is n >= 2, CVXQUAD formulates 4 by 4 or higher dimension LMIs, which CVX will not be able to convert to Second Order Cone constraints. Therefore, when n >= 2, only an SDP solver (Mosek, SDPT3, SeDuMi, SCS) may be used as cvx_solver for any of the CVXQUAD quantum (matrix) functions. Binary or integer constraints can not be used. Matrices of various dimensions (including n = 1, i.e., scalar) can be included in the same CVX program, in which case the solver requirements for n >= 2 are applicable to the program.

Disclaimer: The function quantum_rel_entr is way cool, but formulates several 2*n^2 by 2*n^2 LMIs. The modell formulation and solver time as well as needed memory can quickly increase with n. Other CVXQUAD quantum (matrix) functions have less severe run-time and memory requirements than quantum_rel_entr - see table 1 of the referenced paper.

CVX formulations of several matrix perspective and log_det related functions using CVXQUAD’s quantum_rel_entr are shown at
Perspective of log det function, and CVX formulations of related log det problems using Quantum Relative Entropy from CVXQUAD . In short, for every CVX formulation which I have looked at of an expression formulated using rel_entr for which there is a natural matrix analog using quantum_rel_entr,, the matrix analog formulation is mathematically correct, and will be accepted by CVX if CVXQUAD is installed (and presuming all CVX’s other rules are satisfied). The only “catch”: is that rum-time and memory requirements can be severe even at modest values of matrix dimension n.

==========================

Note: Please post to this thread in the unlikely (ha, ha) event I have made any errors, typos, or omissions.

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

There are no guarantees or warranties that the material in this post is correct. If your rocket blows up or your weaponized drone attacks you, that’s your tough luck.

14 Likes

A post was merged into an existing topic: Optimal value (cvx_optval) is NaN

If I am using CVX2.2 + Mosek 9.x, do I still need to use-rel_entr(1,cvx_expresion)exp(log(a)*cvx_expression) to replace log(cvx_expression)a^cvx_expression, or are these two expressions have the same effect?

If CVX 2.2 is used with Mosek 9.x or Mosek 10.x, there is no need to perform any of these reformulations.

Okay, thank you very much!

Hi, Mark. I want to inquire a question about the replacement of log() in CVX. The function form of log(vw-w^HG*w) is able to be transformed by rel_entr? where v and w are the vectors, G is the matrix. Thanks!

The argument of log must be concave. if it is, log(x) can be rewritten as -rel_entr(1,x). It is only necessary to use rel_entr if CVXQUAD is being used.

In your case, if v and G are input data, and G is psd, then v'*w - w'*G*w is concave, and so -rel_entr(1,v'*w - w'*G*w) can be used.

However, if you have Mosek available as solver, it is better to use that than CVXQUAD('s exponential.m replacement). And in that case, there is no need or benefit to reformulate log using rel_entr.

微信图片_20230705145358
Thanks for your reply. Yeah, I plan to use the Mosek solver to solve the optimization problem. But when I used the rel_entr() to transform log(vw-w^H G*w) and verified the convexity/concavity of this form in Matlab, Matlab gives this error prompt.

Please show your complete program, preferably complete with all input data. Dies it meet the requirements I listed above?

Given your use of Mosek, there is no need to use rel_entr in place of log. But it shouldn’t make a difference in what CVX does or does not accept.