# 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 and more reliable 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

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)

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

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

    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).

# ==========================

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 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.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.

8 Likes
CVX solve failure with log function
How to express the following function in cvxQUAD
Successive convex approximation is used in my algorithm
When frd=sqrt(x) is used in cvx, the values of frd and sqrt(x) are very different.
SDPT3 status: Failed Optimal value (cvx_optval): NaN
When I used CVXQUAD,I still get Failed
'cvx_bound' is 'Inf' but 'cvx_optval' is caculated as '9.667'
Why I get this when using rel_entr?
CVX failed after some iteration
Successive convex approximation ralways return NaN
CVX 3.0 beta interesting features
Cannot perform the operation: {log-affine} .* {real affine}
Semidefinite programming with rank 1 Hermitian semidefinite matric variable
ERROR! Invalid operation: {real affine} / {real affine}
Cvx never returns
How to write the following objective function about Exponential function in CVX?
What is causing the final Status: Inaccurate/Solved? and how can I modify my code to get it Solved?
The Optimization problem is convex. But sometimes CVX failed to find the optimal solution
CVX return NaN in most runs,and sometimes it works
L1/2 regularized logistic regression
Sum Log fuction optimisation error with CVX
Adding SCS Solver to CVX's solvers list
How can i solve this optimisation function
How can I write this kind of constraint in cvx
How to speed up run time?
The Optimization problem is convex. But sometimes CVX failed to find the optimal solution
Optimal value (cvx_optval) is NaN
CVX 3.0beta can not find the license of Mosek 9.0
How to speed up run time?
Illegal operation: rel_entr( {positive constant}, {log-convex} )
HELP：How to solve this problem
The optimization process is unbounded and then solved when using SCA
The status is solved, but the result is wrong
How to write this optimization problem in CVX form?
The problem shows that it has been resolved, but there is a constraint that is not satisfied
How to handle the constraint involving perspective functions $\left( \exp\left(\beta y \oslash x \right) - 1 \right)$
What's wrong about successive approximation algorithm by CVX?
(Mark L. Stone) split this topic #9

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

Interpolation error