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


(Mark L. Stone) #1

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

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

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
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, 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
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_rek_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 as far as I know, no one has attempted to verify that this combination works correctly. I only have the free version of CVX, so I can not try it.

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 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. It is strongly recommended to not use CVXQUAD with CVX 3.0beta. Please use CVX 2.1 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.


CVX solve failure with log function