Speed Problem in CVX solving exponential cone

Salwa_Mostafa · September 1, 2021, 1:58am

I have the following convex optimization problem

\min_{x} {ax}{\left(\exp{\left(\frac{b}{x}\right)} - 1\right)} + {a(1-x)}{\left(\exp{\left(\frac{b}{1-x}\right)} - 1\right)},

subject to

{a_1 x}{\left(\exp{\left(\frac{b_1}{x}\right)} - 1\right)} \leq c_1, \\ {a_2 (1-x)}{\left(\exp{\left(\frac{b_2}{(1-x)}\right)} - 1\right)} \leq c_2, \\ 0 < x < 1,

The problem is variable in x and a,b,a_1,b_1,a_2,b_2 are positive constants.

I used CVX to solve it in Matlab but it takes a long long time. I need to average out over a large number of iterations and for each iteration, I need to run CVX to compute different possibilities. I used Mosek and Pade approximation but still takes a long time. Any suggestions to speed it up more ? OR Any suggestion for numerical methods that I can use to implement specifically for this problem.

Thanks for your help in advance.

Erling · September 1, 2021, 5:43am

What do you mean by long time since you are optimizing over a scalar variable? That can take long.

I bet you can reformulate this problem using the exponential cone and solve it directly with Mosek with using Pade approximation.

This Pade approximation stuff may be a great idea in theory but should be avoided in practice if possible.

Salwa_Mostafa · September 1, 2021, 6:45am

    a1 = 2; a2 = 2; b1 = 1; b2 = 1; a3 = 1; a4 = 1; c1 = 20; c2 = 20 ;
        cvx_solver mosek
        cvx_begin quiet 
                variables  x  Z1 Z2
                minimize( (a1.*Z1  - a1.*x) + (a2.*Z2  - a2.*(1-x)))
             subject to
              {b1,x,Z1} == exponential(1)
              {b2,1-x,Z2} == exponential(1)
              0 <= x <= 1
              ((a3.*Z1)  - (a3.*x)) <= c1
              ((a4.*Z2)  - (a4.*(1-x))) <= c2
       cvx_end

This is my implementation. Any suggestion for other reformulation.

Michal_Adamaszek · September 1, 2021, 8:03am

Use cvx2.2 with Mosek 9.2+ and you will solve exponential cone problems directly without approximation.

Don’t use quiet when debugging.

Salwa_Mostafa · September 1, 2021, 8:55am

Thanks for the suggestion. I was already using it. This is the output without the quiet mode. There is still messages on using Pade approximation but the same messages from Mosek as the post you linked. So I am not sure if it still using Pad approximation or just debug issue.

It still takes days to run.

Michal_Adamaszek · September 1, 2021, 9:13am

Fix your cvx installation. It should not use the Pade approximation. Look at the problem size in Mosek log. I solved it immediately and the log was as follows:

CVX Warning:
   Models involving "exponential" or other functions in the log, exp, and entropy
   family are solved using an experimental successive approximation method.
   This method is slower and less reliable than the method CVX employs for
   other models. Please see the section of the user's guide entitled
       <a href="file:////home/aszek/cvx2.2/doc/advanced.html#the-successive-approximation-method">The successive approximation method</a>
   for more details about the approach, and for instructions on how to
   suppress this warning message in the future.
 
Calling Mosek 9.1.9: 10 variables, 3 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:27:13)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Linux/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 3               
  Cones                  : 2               
  Scalar variables       : 10              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 2
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 2                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.05    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 3               
  Cones                  : 2               
  Scalar variables       : 10              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 20              
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 1
Optimizer  - Cones                  : 2
Optimizer  - Scalar variables       : 8                 conic                  : 6               
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 1                 after factor           : 1               
Factor     - dense dim.             : 0                 flops                  : 1.70e+01        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   5.1e+00  6.4e+00  2.0e+01  0.00e+00   1.868877074e+01   0.000000000e+00   1.0e+00  0.07  
1   6.2e-01  7.8e-01  3.4e+00  -5.24e-01  5.414724018e+01   4.856774075e+01   1.2e-01  0.18  
2   1.4e-01  1.8e-01  6.2e-01  3.48e-01   6.328924677e+01   6.181381188e+01   2.8e-02  0.19  
3   2.2e-02  2.8e-02  4.2e-02  7.04e-01   6.701333099e+01   6.677709526e+01   4.3e-03  0.19  
4   6.5e-03  8.2e-03  8.3e-03  7.03e-01   6.705397373e+01   6.698910993e+01   1.3e-03  0.20  
5   1.3e-04  1.7e-04  2.5e-05  9.75e-01   6.722028944e+01   6.721902218e+01   2.6e-05  0.20  
6   8.5e-06  1.1e-05  4.1e-07  9.88e-01   6.722184509e+01   6.722176686e+01   1.7e-06  0.21  
7   7.5e-06  9.3e-06  3.5e-07  -6.95e-01  6.722187076e+01   6.722180179e+01   1.4e-06  0.21  
8   7.3e-06  9.1e-06  3.4e-07  1.05e+00   6.722186963e+01   6.722180170e+01   1.3e-06  0.22  
9   7.3e-06  9.1e-06  3.4e-07  8.86e-01   6.722186961e+01   6.722180169e+01   1.3e-06  0.22  
10  7.3e-06  9.1e-06  3.4e-07  9.89e-01   6.722186961e+01   6.722180169e+01   1.3e-06  0.23  
11  6.4e-06  8.0e-06  2.7e-07  1.00e+00   6.722186408e+01   6.722180221e+01   1.2e-06  0.23  
12  6.3e-06  7.9e-06  2.7e-07  1.00e+00   6.722186369e+01   6.722180225e+01   1.2e-06  0.24  
13  5.7e-06  7.1e-06  2.3e-07  9.64e-01   6.722186065e+01   6.722180374e+01   1.0e-06  0.24  
14  5.6e-06  7.1e-06  2.3e-07  1.46e+00   6.722186155e+01   6.722180518e+01   1.0e-06  0.25  
15  3.5e-06  4.3e-06  1.1e-07  9.82e-01   6.722185979e+01   6.722182138e+01   6.3e-07  0.25  
16  3.3e-06  4.1e-06  9.8e-08  8.55e-01   6.722185968e+01   6.722182273e+01   5.9e-07  0.26  
17  3.0e-06  3.8e-06  8.6e-08  1.12e+00   6.722186071e+01   6.722182626e+01   5.5e-07  0.26  
18  2.8e-06  3.6e-06  7.8e-08  1.13e+00   6.722186168e+01   6.722182911e+01   5.2e-07  0.27  
19  2.8e-06  3.6e-06  7.8e-08  1.02e+00   6.722186168e+01   6.722182916e+01   5.2e-07  0.28  
20  2.6e-06  3.2e-06  6.7e-08  1.04e+00   6.722186250e+01   6.722183238e+01   4.7e-07  0.28  
21  2.6e-06  3.2e-06  6.6e-08  1.24e+00   6.722186291e+01   6.722183329e+01   4.7e-07  0.29  
22  2.5e-06  3.1e-06  6.4e-08  8.79e-01   6.722186295e+01   6.722183366e+01   4.6e-07  0.29  
23  2.5e-06  3.1e-06  6.3e-08  1.23e+00   6.722186314e+01   6.722183408e+01   4.6e-07  0.30  
24  2.5e-06  3.1e-06  6.3e-08  2.22e+00   6.722186375e+01   6.722183484e+01   4.5e-07  0.30  
25  2.5e-06  3.1e-06  6.2e-08  1.06e+00   6.722186384e+01   6.722183519e+01   4.5e-07  0.31  
26  2.4e-06  3.0e-06  6.1e-08  9.89e-01   6.722186394e+01   6.722183570e+01   4.4e-07  0.31  
27  2.4e-06  3.0e-06  6.0e-08  1.13e+00   6.722186396e+01   6.722183575e+01   4.4e-07  0.32  
28  6.2e-09  7.8e-09  8.0e-12  9.75e-01   6.722188770e+01   6.722188763e+01   1.1e-09  0.32  
Optimizer terminated. Time: 0.39    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 6.7221887701e+01    nrm: 1e+01    Viol.  con: 5e-13    var: 1e-08    cones: 0e+00  
  Dual.    obj: 6.7221887627e+01    nrm: 2e+01    Viol.  con: 0e+00    var: 6e-08    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.39    
    Interior-point          - iterations : 28        time: 0.33    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +12.7781

Salwa_Mostafa · September 1, 2021, 9:20am

Okay. Thanks so much I solved it.

Mark_L_Stone · September 1, 2021, 11:42am

It looks like you were using the exponential.m replacement of CVXQUAD. That is why It was using the Padé approximation, despite having CVX 2.2 and Mosek 9.x.

You should restore CVX’s version of exponential.m. That way CVXQUAD’s Padé approoximation won’t be invoked and the problem will be solved using Mosek’s native exponential cone capability, which is the best way of solving it now.

Salwa_Mostafa · September 1, 2021, 12:07pm

That is exactly what happened. Thanks for your help.