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.
