Redundant variables / constraints change the optimal value?!


(Chen Chen) #1

I find a really wield thing. See the cvx code below. The objective is to minimize ‘vsub’ (‘num_sub’ is just a positive constant here). The optimal value returned is 0.25.

But note, in the optimization problem the decision variables ‘vhub’ and ‘VADPMatrix1’ and thus the first four inequality constraints are totally unrelated and redundant. But deleting them change the optimal value to be 0.328378! It should return the same thing. You guys can test it. Who can tell what is wrong here?

        num_sub = 1000;
        m = 2000;
        Lambda = [0, -0.4532 * 1.0e-08]';
        Pb1 = [1/2; 1/2];
        Pb2 = [1/(2*num_sub); 1/(2*num_sub); 1 - 1/num_sub];

        cvx_begin
            variables VADPMatrix1(m+1,2) VADPMatrix2(m+1,3) 
            variables vhub vsub
            variable tmp1(m,2) nonnegative
            variable tmp2(m,2) nonnegative
            variable Z(m,2)
            minimize ( num_sub * vsub )
            subject to 
                vhub + VADPMatrix1(:,1) >= VADPMatrix1 * Pb1;
                vhub + VADPMatrix1(2:m+1,1) >= VADPMatrix1(1:m,:) * Pb1 + Lambda(1);
                vhub + VADPMatrix1(:,2) >= VADPMatrix1 * Pb1;
                vhub + VADPMatrix1(1:m,2) >= VADPMatrix1(2:m+1,:) * Pb1 - Lambda(2);


                Z(:,1) == VADPMatrix2(1:m,:) * Pb2 - VADPMatrix2(2:m+1,:) * Pb2 + Lambda(2);
                vsub + VADPMatrix2(2:m+1,1) >= (1 + tmp1(:,1) - tmp2(:,1) + Z(:,1)).^2/4 + tmp2(:,1) + VADPMatrix2(2:m+1,:) * Pb2;
                vsub + VADPMatrix2(1,1) >= VADPMatrix2(1,:) * Pb2;

                Z(:,2) == VADPMatrix2(2:m+1,:) * Pb2 - VADPMatrix2(1:m,:) * Pb2 - Lambda(1);
                vsub + VADPMatrix2(1:m,2) >= (1 + tmp1(:,2) - tmp2(:,2) + Z(:,2)).^2/4 + tmp2(:,2) + VADPMatrix2(1:m,:) * Pb2;
                vsub + VADPMatrix2(m+1,2) >= VADPMatrix2(m+1,:) * Pb2;

                vsub + VADPMatrix2(:,3) >= VADPMatrix2 * Pb2;
        cvx_end

        value = cvx_optval;

(Mark L. Stone) #2

What solver did you use? What was the status reported by CVX?

I tried sedumi, sdpt3, and ecos with and without the “redundant” constraints. In all cases, cvx_optval was close to 0.25, but in some cases, the result was reported as inaccurate/solved/


(Chen Chen) #3

Thanks so much, Mark! I used the the Mosek solver.

Here is the report with the redundant constraints.

	  Calling Mosek 7.1.0.12: 34005 variables, 22007 equality constraints
	   For improved efficiency, Mosek is solving the dual problem.
	------------------------------------------------------------

	MOSEK Version 7.1.0.60 (Build date: 2016-10-7 14:10:42)
	Copyright (c) 1998-2016 MOSEK ApS, Denmark. WWW: http://mosek.com
	Platform: Windows/64-X86

	Computer
	  Platform               : Windows/64-X86  

	Problem
	  Name                   :                 
	  Objective sense        : min             
	  Type                   : CONIC (conic optimization problem)
	  Constraints            : 22007           
	  Cones                  : 4000            
	  Scalar variables       : 34005           
	  Matrix variables       : 0               
	  Integer variables      : 0               

	Optimizer started.
	Conic interior-point optimizer started.
	Presolve started.
	Linear dependency checker started.
	Linear dependency checker terminated.
	Eliminator - tries                  : 0                 time                   : 0.00            
	Eliminator - elim's                 : 2               
	Lin. dep.  - tries                  : 1                 time                   : 0.13            
	Lin. dep.  - number                 : 1               
	Presolve terminated. Time: 0.17    
	Optimizer  - threads                : 2               
	Optimizer  - solved problem         : the primal      
	Optimizer  - Constraints            : 10003
	Optimizer  - Cones                  : 4000
	Optimizer  - Scalar variables       : 18003             conic                  : 12000           
	Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
	Factor     - setup time             : 0.03              dense det. time        : 0.00            
	Factor     - ML order time          : 0.01              GP order time          : 0.00            
	Factor     - nonzeros before factor : 6.80e+004         after factor           : 7.00e+004       
	Factor     - dense dim.             : 0                 flops                  : 1.66e+006       
	ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
	0   2.2e+003 1.0e+000 2.0e+003 0.00e+000  5.120000000e+005  0.000000000e+000  1.0e+000 0.25  
	1   3.9e+002 1.8e-001 3.5e+002 -7.19e-001 1.930167366e+005  -3.611088889e+003 1.8e-001 0.27  
	2   5.8e+001 2.6e-002 5.2e+001 1.26e+000  2.051726749e+004  -3.431496584e+003 2.6e-002 0.28  
	3   6.4e+000 2.8e-003 5.7e+000 1.16e+000  -3.395684974e+002 -2.641154192e+003 2.8e-003 0.30  
	4   4.6e-001 2.1e-004 4.1e-001 1.88e+000  -3.137287671e+000 -1.066460865e+002 2.1e-004 0.31  
	5   2.7e-002 1.2e-005 2.4e-002 1.06e+000  -6.962987983e-001 -6.479068374e+000 1.2e-005 0.33  
	6   3.6e-003 1.6e-006 3.2e-003 1.11e+000  -5.353374952e-001 -1.239332602e+000 1.6e-006 0.34  
	7   1.0e-003 4.5e-007 9.0e-004 1.93e+000  -3.469548325e-001 -4.649191111e-001 4.5e-007 0.36  
	8   1.7e-004 7.5e-008 1.5e-004 2.25e+000  -2.554620262e-001 -2.669713517e-001 7.5e-008 0.38  
	9   2.1e-005 9.2e-009 1.8e-005 1.10e+000  -2.506294322e-001 -2.519798264e-001 9.2e-009 0.39  
	10  4.7e-006 2.1e-009 4.2e-006 1.01e+000  -2.501414103e-001 -2.504472369e-001 2.1e-009 0.41  
	11  1.2e-006 5.2e-010 1.0e-006 1.00e+000  -2.500345734e-001 -2.501110088e-001 5.2e-010 0.42  
	12  2.8e-007 1.2e-010 2.5e-007 1.00e+000  -2.500072184e-001 -2.500254543e-001 1.2e-010 0.44  
	13  6.6e-008 2.9e-011 5.8e-008 1.00e+000  -2.500009923e-001 -2.500052672e-001 2.9e-011 0.45  
	14  1.6e-008 7.3e-012 1.5e-008 1.00e+000  -2.499998204e-001 -2.500008857e-001 7.3e-012 0.47  
	Interior-point optimizer terminated. Time: 0.47. 

	Optimizer terminated. Time: 0.48    

	Interior-point solution summary
	  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
	  Solution status : OPTIMAL
	  Primal.  obj: -2.4999982038e-001  Viol.  con: 5e-006   var: 0e+000   cones: 0e+000 
	  Dual.    obj: -2.5000088567e-001  Viol.  con: 0e+000   var: 4e-012   cones: 0e+000 
	Optimizer summary
	  Optimizer                 -                        time: 0.48    
		Interior-point          - iterations : 14        time: 0.47    
		  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    
			Clean primal-dual   - iterations : 0         time: 0.00    
		Simplex                 -                        time: 0.00    
		  Primal simplex        - iterations : 0         time: 0.00    
		  Dual simplex          - iterations : 0         time: 0.00    
		  Primal-dual simplex   - iterations : 0         time: 0.00    
		Mixed integer           - relaxations: 0         time: 0.00    

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

Here is the report without the redundant constraints.

	Calling Mosek 7.1.0.12: 36010 variables, 14003 equality constraints
	------------------------------------------------------------

	MOSEK Version 7.1.0.60 (Build date: 2016-10-7 14:10:42)
	Copyright (c) 1998-2016 MOSEK ApS, Denmark. WWW: http://mosek.com
	Platform: Windows/64-X86

	Computer
	  Platform               : Windows/64-X86  

	Problem
	  Name                   :                 
	  Objective sense        : min             
	  Type                   : CONIC (conic optimization problem)
	  Constraints            : 14003           
	  Cones                  : 4000            
	  Scalar variables       : 36010           
	  Matrix variables       : 0               
	  Integer variables      : 0               

	Optimizer started.
	Conic interior-point optimizer started.
	Presolve started.
	Linear dependency checker started.
	Linear dependency checker terminated.
	Eliminator started.
	Total number of eliminations : 6002
	Eliminator terminated.
	Eliminator - tries                  : 1                 time                   : 0.00            
	Eliminator - elim's                 : 6002            
	Lin. dep.  - tries                  : 1                 time                   : 0.02            
	Lin. dep.  - number                 : 0               
	Presolve terminated. Time: 0.08    
	Optimizer  - threads                : 2               
	Optimizer  - solved problem         : the primal      
	Optimizer  - Constraints            : 4001
	Optimizer  - Cones                  : 4000
	Optimizer  - Scalar variables       : 20003             conic                  : 12000           
	Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
	Factor     - setup time             : 0.02              dense det. time        : 0.00            
	Factor     - ML order time          : 0.00              GP order time          : 0.00            
	Factor     - nonzeros before factor : 1.20e+004         after factor           : 1.60e+004       
	Factor     - dense dim.             : 2                 flops                  : 2.44e+005       
	ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
	0   1.0e+000 1.0e+000 1.0e+000 0.00e+000  0.000000000e+000  0.000000000e+000  1.0e+000 0.17  
	1   8.3e-002 8.0e-002 8.0e-002 2.11e+000  3.936702415e+001  3.799276976e+002  8.0e-002 0.19  
	2   4.2e-003 4.0e-003 4.0e-003 1.07e+000  4.119882742e+001  5.802763321e+001  4.0e-003 0.19  
	3   2.3e-004 2.2e-004 2.2e-004 1.01e+000  4.048164168e+001  4.129814570e+001  2.2e-004 0.20  
	4   2.6e-005 2.5e-005 2.5e-005 1.16e+000  2.906646055e+001  2.909044085e+001  2.5e-005 0.20  
	5   2.3e-006 2.2e-006 2.2e-006 1.73e+000  2.238997695e+000  2.239115385e+000  2.2e-006 0.22  
	6   5.9e-007 5.7e-007 5.7e-007 1.53e+000  8.105009466e-001  8.103460373e-001  5.7e-007 0.22  
	7   1.6e-007 1.5e-007 1.5e-007 1.74e+000  3.283784095e-001  3.283489275e-001  1.5e-007 0.23  
	Interior-point optimizer terminated. Time: 0.23. 

	Optimizer terminated. Time: 0.25    

	Interior-point solution summary
	  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
	  Solution status : OPTIMAL
	  Primal.  obj: 3.2837840951e-001   Viol.  con: 4e-006   var: 0e+000   cones: 0e+000 
	  Dual.    obj: 3.2834892751e-001   Viol.  con: 0e+000   var: 3e-005   cones: 8e-006 
	Optimizer summary
	  Optimizer                 -                        time: 0.25    
		Interior-point          - iterations : 7         time: 0.23    
		  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    
			Clean primal-dual   - iterations : 0         time: 0.00    
		Simplex                 -                        time: 0.00    
		  Primal simplex        - iterations : 0         time: 0.00    
		  Dual simplex          - iterations : 0         time: 0.00    
		  Primal-dual simplex   - iterations : 0         time: 0.00    
		Mixed integer           - relaxations: 0         time: 0.00    

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

The status is “solved” in both cases.


(Mark L. Stone) #4

Can you try with a current version (8.1.0.56) of Mosek?

When things are going well and the problem is not ill-posed, then I believe PRSTATUS should converge to 1.0 Note that it does in the version with the redundant constraints (which gets the “correct” answer), but not in the version without them (which doesn’t) . it would be interesting to see whether Mosek 8.1 (which incorporates various numerical improvements) performs better. Even though Mosekl reports Problem status : PRIMAL_AND_DUAL_FEASIBLE, Solution status : OPTIMAL, in both cases, I think that not having PRSTATUS of 1.0 imbues a lesser confidence in the result.

I will defer to Mosek personnel for any further discussion on that.

I don’t have any insight as to why the formulations with and without redundant constraints vary in apparent difficulty for the various solvers, and how that may or may not be related to pre-processing and transformation by CVX, pre-solve by the solver, etc.


(Michal Adamaszek) #5

Try with Mosek 8.1, and in any case you are welcome to do cvx_solver_settings('write', 'dump.task.gz') and send the task files to Mosek support.


(Chen Chen) #6

Thanks Mark and Michal, quite helpful! I installed Mosek 8.1.056 and the problem almost resolves, but there is still a difference of 10^-4.

Here is the report with the redundant constraints.

        Calling Mosek unknown: 34005 variables, 22007 equality constraints
	   For improved efficiency, Mosek is solving the dual problem.
	------------------------------------------------------------
	Problem
	  Name                   :                 
	  Objective sense        : min             
	  Type                   : CONIC (conic optimization problem)
	  Constraints            : 22007           
	  Cones                  : 4000            
	  Scalar variables       : 34005           
	  Matrix variables       : 0               
	  Integer variables      : 0               

	Optimizer started.
	Presolve started.
	Linear dependency checker started.
	Linear dependency checker terminated.
	Eliminator - tries                  : 0                 time                   : 0.00            
	Lin. dep.  - tries                  : 1                 time                   : 0.36            
	Lin. dep.  - number                 : 1               
	Presolve terminated. Time: 0.39    
	Problem
	  Name                   :                 
	  Objective sense        : min             
	  Type                   : CONIC (conic optimization problem)
	  Constraints            : 22007           
	  Cones                  : 4000            
	  Scalar variables       : 34005           
	  Matrix variables       : 0               
	  Integer variables      : 0               

	Optimizer  - threads                : 2               
	Optimizer  - solved problem         : the primal      
	Optimizer  - Constraints            : 10003
	Optimizer  - Cones                  : 4000
	Optimizer  - Scalar variables       : 18003             conic                  : 12000           
	Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
	Factor     - setup time             : 0.05              dense det. time        : 0.00            
	Factor     - ML order time          : 0.00              GP order time          : 0.00            
	Factor     - nonzeros before factor : 6.80e+04          after factor           : 7.00e+04        
	Factor     - dense dim.             : 0                 flops                  : 1.48e+06        
	ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
	0   2.0e+03  7.1e-01  1.0e+03  0.00e+00   1.600000000e+04   0.000000000e+00   1.0e+00  0.45  
	1   3.5e+02  1.3e-01  3.2e+02  -3.82e-01  3.223107444e+03   -5.299697334e+02  1.8e-01  0.48  
	2   5.3e+01  1.9e-02  1.7e+02  1.99e+00   2.695516717e+01   -3.094199611e+02  2.7e-02  0.50  
	3   4.6e+00  1.7e-03  9.8e+01  1.78e+00   -1.001151002e+01  -2.895951278e+01  2.3e-03  0.52  
	4   3.0e-01  1.1e-04  2.9e+01  1.15e+00   -9.440432038e-01  -2.084949153e+00  1.5e-04  0.53  
	5   7.1e-02  2.6e-05  3.6e+01  1.60e+00   -4.067993728e-01  -5.871639659e-01  3.6e-05  0.55  
	6   2.0e-02  7.1e-06  1.4e+01  2.71e+00   -2.624704665e-01  -2.881357143e-01  1.0e-05  0.56  
	7   2.0e-03  7.3e-07  5.0e+00  1.17e+00   -2.512536810e-01  -2.536792205e-01  1.0e-06  0.58  
	8   5.2e-04  1.9e-07  2.6e+00  1.02e+00   -2.503181059e-01  -2.509332776e-01  2.6e-07  0.59  
	9   1.6e-04  5.7e-08  1.5e+00  1.01e+00   -2.501001463e-01  -2.502874182e-01  8.0e-08  0.61  
	10  4.2e-05  1.5e-08  8.1e-01  1.00e+00   -2.500258536e-01  -2.500753805e-01  2.1e-08  0.63  
	11  9.9e-06  3.6e-09  4.1e-01  1.00e+00   -2.500050802e-01  -2.500167959e-01  5.0e-09  0.64  
	12  2.3e-06  9.5e-10  2.0e-01  1.00e+00   -2.500005360e-01  -2.500032692e-01  1.2e-09  0.66  
	13  6.0e-07  9.9e-10  1.1e-01  1.00e+00   -2.499997360e-01  -2.500004451e-01  3.1e-10  0.67  
	14  1.9e-07  3.0e-09  5.9e-02  1.00e+00   -2.499995167e-01  -2.499997259e-01  9.0e-11  0.69  
	Optimizer terminated. Time: 0.70    


	Interior-point solution summary
	  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
	  Solution status : OPTIMAL
	  Primal.  obj: -2.4999951669e-01   nrm: 1e+03    Viol.  con: 9e-07    var: 0e+00    cones: 0e+00  
	  Dual.    obj: -2.4999972590e-01   nrm: 4e+00    Viol.  con: 0e+00    var: 2e-09    cones: 0e+00  
	Optimizer summary
	  Optimizer                 -                        time: 0.70    
		Interior-point          - iterations : 14        time: 0.69    
		  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): +0.25

Here is the report without the redundant constraints.

	Calling Mosek unknown: 36010 variables, 14003 equality constraints
	------------------------------------------------------------
	Problem
	  Name                   :                 
	  Objective sense        : min             
	  Type                   : CONIC (conic optimization problem)
	  Constraints            : 14003           
	  Cones                  : 4000            
	  Scalar variables       : 36010           
	  Matrix variables       : 0               
	  Integer variables      : 0               

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

	Optimizer  - threads                : 2               
	Optimizer  - solved problem         : the primal      
	Optimizer  - Constraints            : 4004
	Optimizer  - Cones                  : 4001
	Optimizer  - Scalar variables       : 22011             conic                  : 12006           
	Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
	Factor     - setup time             : 0.02              dense det. time        : 0.00            
	Factor     - ML order time          : 0.00              GP order time          : 0.00            
	Factor     - nonzeros before factor : 1.80e+04          after factor           : 2.40e+04        
	Factor     - dense dim.             : 3                 flops                  : 2.84e+05        
	ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
	0   1.1e+00  1.3e+02  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.14  
	1   5.3e-01  5.9e+01  2.4e-01  1.14e+01   1.639371579e+02   4.019239223e+02   4.7e-01  0.17  
	2   5.1e-02  5.6e+00  6.1e-02  2.08e+00   5.125515659e+01   8.601673909e+01   4.5e-02  0.19  
	3   3.5e-03  3.9e-01  1.7e-02  1.11e+00   4.408230807e+00   6.536362711e+00   3.2e-03  0.20  
	4   7.0e-04  7.8e-02  1.6e-02  1.20e+00   1.476488526e+00   1.564239598e+00   6.2e-04  0.22  
	5   2.0e-04  2.2e-02  2.4e-02  1.91e+00   5.594531583e-01   5.619924834e-01   1.7e-04  0.25  
	6   4.3e-05  4.8e-03  1.6e-02  1.58e+00   2.865237863e-01   2.867573412e-01   3.8e-05  0.27  
	7   4.5e-06  5.1e-04  5.6e-03  1.15e+00   2.535793536e-01   2.536005398e-01   4.0e-06  0.28  
	8   7.8e-07  8.7e-05  2.4e-03  1.02e+00   2.506025097e-01   2.506058336e-01   6.9e-07  0.28  
	9   1.6e-07  1.8e-05  1.1e-03  1.00e+00   2.501224587e-01   2.501230207e-01   1.4e-07  0.30  
	Optimizer terminated. Time: 0.33    


	Interior-point solution summary
	  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
	  Solution status : OPTIMAL
	  Primal.  obj: 2.5012245871e-01    nrm: 2e+00    Viol.  con: 2e-06    var: 2e-05    cones: 0e+00  
	  Dual.    obj: 2.5012302069e-01    nrm: 5e-01    Viol.  con: 0e+00    var: 6e-06    cones: 2e-08  
	Optimizer summary
	  Optimizer                 -                        time: 0.33    
		Interior-point          - iterations : 9         time: 0.31    
		  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): +0.250122

So it should be the issue of Mosek 7.1 I use.


(Michal Adamaszek) #7

I missed that before, but I think it has more to do with the fact that in one of the variants CVX dualizes before calling Mosek, and in the other it does not. It sometimes happens that one of the versions solves better.


(Chen Chen) #8

Hi Michal and Mark, I still meet the problem (with Mosek 8.1.0.56) that the status is

 Problem status  : PRIMAL_AND_DUAL_FEASIBLE
 Solution status : OPTIMAL

But PRSTATUS is not 1. As Mark mentioned, this does not render a confidence about the returned solution, even though I guess it is near the optimal.

Here is a report example I get:

	Calling Mosek unknown: 112205 variables, 72609 equality constraints
	   For improved efficiency, Mosek is solving the dual problem.
	------------------------------------------------------------
	Problem
	  Name                   :                 
	  Objective sense        : min             
	  Type                   : CONIC (conic optimization problem)
	  Constraints            : 72609           
	  Cones                  : 13200           
	  Scalar variables       : 112205          
	  Matrix variables       : 0               
	  Integer variables      : 0               

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

	Optimizer  - threads                : 2               
	Optimizer  - solved problem         : the dual        
	Optimizer  - Constraints            : 46201
	Optimizer  - Cones                  : 13201
	Optimizer  - Scalar variables       : 125409            conic                  : 59405           
	Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
	Factor     - setup time             : 0.23              dense det. time        : 0.00            
	Factor     - ML order time          : 0.01              GP order time          : 0.00            
	Factor     - nonzeros before factor : 2.90e+05          after factor           : 3.30e+05        
	Factor     - dense dim.             : 6                 flops                  : 3.93e+06        
	ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
	0   1.4e+02  1.1e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.67  
	1   1.2e+02  9.4e-01  6.5e-01  7.92e+00   -9.927142669e+02  -9.133600954e+02  8.9e-01  0.77  
	2   2.1e+01  1.6e-01  9.0e-02  5.20e+00   -1.555053136e+03  -1.378294531e+03  1.5e-01  0.84  
	3   5.1e+00  3.9e-02  5.9e-02  1.90e+00   -3.291451224e+02  -3.045916528e+02  3.7e-02  0.92  
	4   1.1e-01  8.6e-04  1.1e-02  1.29e+00   -9.098593145e+00  -8.776774409e+00  8.1e-04  1.00  
	5   4.2e-02  3.2e-04  2.8e-02  2.40e+00   -2.633052460e+00  -2.626366272e+00  3.1e-04  1.08  
	6   2.1e-02  1.6e-04  1.9e-02  2.37e+00   -1.151147696e+00  -1.147720872e+00  1.5e-04  1.17  
	7   6.5e-03  5.0e-05  1.1e-02  1.40e+00   -6.221630009e-01  -6.211291941e-01  4.7e-05  1.25  
	8   3.4e-03  2.6e-05  7.3e-03  8.71e-01   -4.384715079e-01  -4.378053711e-01  2.5e-05  1.33  
	9   5.9e-04  4.5e-06  7.8e-03  1.08e+00   -2.827603553e-01  -2.827533756e-01  4.3e-06  1.41  
	10  9.1e-05  7.0e-07  3.2e-03  1.04e+00   -2.549724974e-01  -2.549716705e-01  6.6e-07  1.48  
	Optimizer terminated. Time: 1.58    


	Interior-point solution summary
	  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
	  Solution status : OPTIMAL
	  Primal.  obj: -2.5497249745e-01   nrm: 1e+03    Viol.  con: 3e-05    var: 0e+00    cones: 2e-07  
	  Dual.    obj: -2.5497167052e-01   nrm: 8e+00    Viol.  con: 0e+00    var: 2e-07    cones: 0e+00  
	Optimizer summary
	  Optimizer                 -                        time: 1.58    
		Interior-point          - iterations : 10        time: 1.55    
		  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): +0.254972

I’m quite sure the optimal value should be no larger than 0.25. So I was wondering, can I set a termination criteria for Mosek to enforce it to terminate when PRSTATUS is closed to 1 (say, a gap within 1e-6) to guarantee optimality? I searched online but didn’t find such criteria . I was wondering do we have this termination criteria or other similar termination criteria I can use? Thanks so much!

ps: the example I use for the report is

		num_sub = 1100;
		m = 6600;

		VADP = zeros(m+1,2);

		Pb1 = [1/2; 1/2];
		Pb2 = [1/(2*num_sub); 1/(2*num_sub); 1 - 1/num_sub];

		cvx_begin
			variables VADPMatrix1(m+1,2) VADPMatrix2(m+1,3) 
			variables vhub vsub
			variable Lambda(2)
			variable tmp1(m,2) nonnegative
			variable tmp2(m,2) nonnegative
			variable Z(m,2)
			minimize ( vhub + vsub * num_sub )
			subject to 
				vhub + VADPMatrix1(:,1) >= VADPMatrix1 * Pb1;
				vhub + VADPMatrix1(2:m+1,1) >= VADPMatrix1(1:m,:) * Pb1 + Lambda(1);
				vhub + VADPMatrix1(:,2) >= VADPMatrix1 * Pb1;
				vhub + VADPMatrix1(1:m,2) >= VADPMatrix1(2:m+1,:) * Pb1 - Lambda(2);
				
				
				Z(:,1) == VADPMatrix2(1:m,:) * Pb2 - VADPMatrix2(2:m+1,:) * Pb2 + Lambda(2);
				vsub + VADPMatrix2(2:m+1,1) >= (1 + tmp1(:,1) - tmp2(:,1) + Z(:,1)).^2/4 + tmp2(:,1) + VADPMatrix2(2:m+1,:) * Pb2;
				vsub + VADPMatrix2(1,1) >= VADPMatrix2(1,:) * Pb2;
				
				Z(:,2) == VADPMatrix2(2:m+1,:) * Pb2 - VADPMatrix2(1:m,:) * Pb2 - Lambda(1);
				vsub + VADPMatrix2(1:m,2) >= (1 + tmp1(:,2) - tmp2(:,2) + Z(:,2)).^2/4 + tmp2(:,2) + VADPMatrix2(1:m,:) * Pb2;
				vsub + VADPMatrix2(m+1,2) >= VADPMatrix2(m+1,:) * Pb2;
				
				vsub + VADPMatrix2(:,3) >= VADPMatrix2 * Pb2;
		cvx_end

(Mark L. Stone) #9

This is a different, larger problem instance than your previous answer, also using Mosek 8.1.0.56? Perhaps you should follow @Michal_Adamaszek 's suggestion and send task files to Mosek support. I will defer on discussion of the Mosek optimizer to him.


(Chen Chen) #10

Yes, this is a different problem. The (only) difference is that now Lambda is a decision variable (dimension is 2) which couples the two parts of the constraints (one part involving vhub and one involving vsub). And yes, Mosek 8.1.0.56 is used. I guess this problem should be ill-conditioned.

After all, I think it’s the issue of Mosek rather than CVX. Super thankful for your kind help and suggestions these days and I will consider reporting this issue.

Many thanks!