Nonnegative constraint not honoured when solving LP problem with Mosek


(Nikita Popov) #1

When solving the following linear feasibility problem using Mosek, the problem is considered solved, but the vector eta ends up containing negative values. The peculiar thing is that if nonnegative is replaced with an explicit eta >= 0 this does not happen and the problem is considered infeasible. When using SDPT3 or Gurobi this problem does not occur.

function repro()
    % Complete code: https://gist.github.com/nikic/ab445c2ebaf1f2938297989e51c07cf1
    mat = ...;
    vec = ...;
    
    cvx_begin
        cvx_solver mosek

        variable eta(40, 1) nonnegative
        %variable eta(40, 1)

        mat * eta <= -vec;
        eta <= 1;
        %eta >= 0;
    cvx_end
    eta
end

Here is the output from Mosek:

Calling Mosek 8.0.0.60: 120 variables, 40 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 8.0.0.60 (Build date: 2017-3-1 13:09:33)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 40              
  Cones                  : 0               
  Scalar variables       : 120             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 9               
Presolve terminated. Time: 0.01    
Optimizer  - threads                : 4               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 3
Optimizer  - Cones                  : 0
Optimizer  - Scalar variables       : 17                conic                  : 0               
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 : 6                 after factor           : 6               
Factor     - dense dim.             : 0                 flops                  : 3.78e+002       
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   1.2e+000 1.0e+000 1.0e+000 1.00e+000  -1.612022072e-006 0.000000000e+000  1.0e+000 0.03  
1   1.2e+000 1.1e+000 1.0e+000 0.00e+000  -8.587046430e-007 0.000000000e+000  3.0e+000 0.11  
2   8.1e-002 7.4e-002 6.7e-002 1.00e+000  -3.225717889e-007 0.000000000e+000  2.1e-001 0.11  
3   3.2e-003 3.0e-003 2.7e-003 1.00e+000  -3.161178013e-008 0.000000000e+000  8.2e-003 0.11  
4   4.6e-006 4.2e-006 3.8e-006 1.00e+000  -1.241655548e-011 0.000000000e+000  1.2e-005 0.13  
5   4.6e-010 4.2e-010 3.8e-010 1.00e+000  -1.241704793e-015 0.000000000e+000  1.2e-009 0.13  
Basis identification started.
Primal basis identification phase started.
ITER      TIME
0         0.02    
Primal basis identification phase terminated. Time: 0.02
Dual basis identification phase started.
ITER      TIME
3         0.00    
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.05
Interior-point optimizer terminated. Time: 0.20. 

Optimizer terminated. Time: 0.28    

Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -1.2417047930e-015  nrm: 2e-007   Viol.  con: 4e-015   var: 5e-014 
  Dual.    obj: 0.0000000000e+000   nrm: 4e+005   Viol.  con: 0e+000   var: 4e+005 

Basic solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 0.0000000000e+000   nrm: 0e+000   Viol.  con: 0e+000   var: 0e+000 
  Dual.    obj: 0.0000000000e+000   nrm: 7e+000   Viol.  con: 0e+000   var: 6e+000 
Optimizer summary
  Optimizer                 -                        time: 0.28    
    Interior-point          - iterations : 5         time: 0.20    
      Basis identification  -                        time: 0.05    
        Primal              - iterations : 0         time: 0.02    
        Dual                - iterations : 3         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
 

eta =

         0
   -2.5504
         0
         0
         0
         0
   -5.7589
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0
         0

(Erling D.Andersen) #2

The solution summary illustrates there is bug in MOSEK. The last number in the

Dual

line should be close to zero. I suggest you upgrade to the latest MOSEK v8.0.0.81. If that does not solve the problem, then email a task file to MOSEK support. See

https://mosek.com/support/faq#how-do-i-dump-a-mosek-task-file-in-cvx

and

https://mosek.com/support/technical-support