% Figure 7.4
% Boyd & Vandenberghe "Convex Optimization"
% Original version by Lieven Vandenberghe
% Updated for CVX by Michael Grant, 2005-12-19

% Generate the data
P = [0.70  0.10
     0.20  0.10
     0.05  0.70
     0.05  0.10];
[n,m] = size(P);

% Construct the tradeoff curve by finding the
% the Pareto optimal deterministic detectors,
% which are the curve's vertices

nopts   = 1000;
weights = logspace(-5,5,nopts);
obj     = [0;1];
inds    = ones(n,1);

% minimize  -t1'*q1 - w*t2'*q2
% s.t.      t1+t2 = 1,  t1,t2 \geq 0

next = 2;
for i = 1 : nopts,
   PW = P * diag( [ 1 ; weights(i) ] );
   [ maxvals, maxinds ] = max( PW' );  % max elt in each row
   if (~isequal(maxinds', inds(:,next-1)))
       inds(:,next) = maxinds';
       T = zeros(m,n);
       for j=1:n
          T(maxinds(1,j),j) = 1;
       end;
       obj(:,next) = 1-diag(T*P);
       next = next+1;
   end;
end;
plot(obj(1,:), obj(2,:),[0 1], [0 1],'--');
grid on
for i=2:size(obj,2)-1
   text(obj(1,i),obj(2,i),['a', num2str(i-1)]);
end;

% Minimax detector: not deterministic

cvx_begin
    variables T( m, n ) D( m, m )
    minimize max( D(1,2), D(2,1) )
    subject to
        D == T * P;
        sum( T, 1 ) == 1;
        T >= 0;
cvx_end

objmp = 1 - diag( D );
text( objmp(1), objmp(2), 'b' );
xlabel('P_{fp}'); ylabel('P_{fn}');

%print -deps roc.eps
 
Calling Mosek 9.1.9: 10 variables, 5 equality constraints
------------------------------------------------------------

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

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 5               
  Cones                  : 0               
  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 : 4
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.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 5               
  Cones                  : 0               
  Scalar variables       : 10              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 1
Optimizer  - Cones                  : 0
Optimizer  - Scalar variables       : 6                 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 : 1                 after factor           : 1               
Factor     - dense dim.             : 0                 flops                  : 1.30e+01        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  2.0e+00  6.0e+00  0.00e+00   2.000000000e+00   0.000000000e+00   4.0e+00  0.00  
1   4.1e-01  4.1e-01  1.2e+00  2.33e+00   5.271701753e-01   4.421583667e-01   8.1e-01  0.01  
2   4.8e-02  4.8e-02  1.4e-01  1.01e+00   2.187626321e-01   2.057396942e-01   9.6e-02  0.01  
3   5.4e-03  5.4e-03  1.6e-02  9.95e-01   1.722986032e-01   1.704628420e-01   1.1e-02  0.01  
4   6.9e-05  6.9e-05  2.1e-04  1.00e+00   1.666975808e-01   1.666681082e-01   1.4e-04  0.01  
5   7.0e-09  7.0e-09  2.1e-08  1.00e+00   1.666666698e-01   1.666666668e-01   1.4e-08  0.01  
Basis identification started.
Primal basis identification phase started.
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Optimizer terminated. Time: 0.01    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 1.6666666981e-01    nrm: 1e+00    Viol.  con: 2e-09    var: 2e-09  
  Dual.    obj: 1.6666666684e-01    nrm: 7e-01    Viol.  con: 0e+00    var: 2e-09  

Basic solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 1.6666666667e-01    nrm: 1e+00    Viol.  con: 0e+00    var: 3e-17  
  Dual.    obj: 1.6666666251e-01    nrm: 7e-01    Viol.  con: 0e+00    var: 7e-18  
Optimizer summary
  Optimizer                 -                        time: 0.01    
    Interior-point          - iterations : 5         time: 0.01    
      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.166667