% From Boyd & Vandenberghe, "Convex Optimization"
% Joëlle Skaf - 08/17/05
%
% Shows the equivalence of the following 3 problems:
% 1) Robust least-squares problem
%           minimize    sum_{i=1}^{m} phi(a_i'*x - bi)
%    where phi(u) = u^2             for |u| <= M
%                   M(2|u| - M)     for |u| >  M
% 2) Least-squares with variable weights
%           minimize    sum_{i=1}^{m} (a_i'*x - bi)^2/(w_i+1) + M^2*1'*w
%               s.t.    w >= 0
% 3) Quadratic program
%           minimize    sum_{i=1}^{m} (u_i^2 + 2*M*v_i)
%               s.t.    -u - v <= Ax - b <= u + v
%                       0 <= u <= M*1
%                       v >= 0

% Generate input data
randn('state',0);
m = 16; n = 8;
A = randn(m,n);
b = randn(m,1);
M = 2;

% (a) robust least-squares problem
disp('Computing the solution of the robust least-squares problem...');
cvx_begin
    variable x1(n)
    minimize( sum(huber(A*x1-b,M)) )
cvx_end

% (b)least-squares problem with variable weights
disp('Computing the solution of the least-squares problem with variable weights...');
cvx_begin
    variable x2(n)
    variable w(m)
    minimize( sum(quad_over_lin(diag(A*x2-b),w'+1)) + M^2*ones(1,m)*w)
    w >= 0;
cvx_end

% (c) quadratic program
disp('Computing the solution of the quadratic program...');
cvx_begin
    variable x3(n)
    variable u(m)
    variable v(m)
    minimize( sum(square(u) +  2*M*v) )
    A*x3 - b <= u + v;
    A*x3 - b >= -u - v;
    u >= 0;
    u <= M;
    v >= 0;
cvx_end

% Display results
disp('------------------------------------------------------------------------');
disp('The optimal solutions for problem formulations 1, 2 and 3 are given');
disp('respectively as follows (per column): ');
[x1 x2 x3]
Computing the solution of the robust least-squares problem...
 
Calling Mosek 9.1.9: 152 variables, 64 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                   : CONIC (conic optimization problem)
  Constraints            : 64              
  Cones                  : 32              
  Scalar variables       : 152             
  Matrix variables       : 0               
  Integer variables      : 0               

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                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 64              
  Cones                  : 32              
  Scalar variables       : 152             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the dual        
Optimizer  - Constraints            : 24
Optimizer  - Cones                  : 32
Optimizer  - Scalar variables       : 96                conic                  : 80              
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 : 180               after factor           : 180             
Factor     - dense dim.             : 0                 flops                  : 5.64e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  2.0e+00  2.5e+01  0.00e+00   1.600000000e+01   -8.000000000e+00  1.0e+00  0.00  
1   4.1e-01  4.1e-01  3.9e+00  5.26e-02   1.772761786e+00   -5.760426069e+00  2.1e-01  0.01  
2   8.9e-02  8.9e-02  4.1e-01  7.48e-01   4.160217895e+00   2.359199320e+00   4.5e-02  0.01  
3   2.3e-02  2.3e-02  5.2e-02  9.67e-01   4.210999257e+00   3.748912815e+00   1.1e-02  0.01  
4   7.6e-03  7.6e-03  1.0e-02  1.00e+00   4.222835207e+00   4.069222755e+00   3.8e-03  0.01  
5   2.4e-03  2.4e-03  1.8e-03  1.00e+00   4.209102647e+00   4.160168718e+00   1.2e-03  0.01  
6   3.4e-04  3.4e-04  9.6e-05  1.00e+00   4.209726646e+00   4.202854232e+00   1.7e-04  0.01  
7   5.0e-06  5.0e-06  1.7e-07  1.00e+00   4.209707372e+00   4.209605489e+00   2.5e-06  0.01  
8   5.1e-08  5.1e-08  1.7e-10  1.00e+00   4.209705258e+00   4.209704232e+00   2.5e-08  0.01  
9   2.6e-09  2.7e-09  2.1e-12  1.00e+00   4.209705215e+00   4.209705162e+00   1.3e-09  0.01  
Optimizer terminated. Time: 0.02    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 4.2097052151e+00    nrm: 2e+00    Viol.  con: 2e-16    var: 1e-09    cones: 3e-09  
  Dual.    obj: 4.2097051615e+00    nrm: 4e+00    Viol.  con: 0e+00    var: 4e-09    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.02    
    Interior-point          - iterations : 9         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): +4.20971
 
Computing the solution of the least-squares problem with variable weights...
 
Calling Mosek 9.1.9: 304 variables, 40 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

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                   : CONIC (conic optimization problem)
  Constraints            : 40              
  Cones                  : 16              
  Scalar variables       : 304             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 16
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                   : CONIC (conic optimization problem)
  Constraints            : 40              
  Cones                  : 16              
  Scalar variables       : 304             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 24
Optimizer  - Cones                  : 16
Optimizer  - Scalar variables       : 48                conic                  : 48              
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 : 180               after factor           : 180             
Factor     - dense dim.             : 0                 flops                  : 5.60e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  1.5e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.00  
1   2.9e-01  2.2e-01  1.5e-01  -2.40e-01  -7.426102505e+00  -6.708055895e+00  1.4e-01  0.01  
2   2.2e-02  1.6e-02  4.3e-03  5.64e-01   -1.916059676e+01  -1.903705542e+01  1.1e-02  0.01  
3   2.1e-04  1.6e-04  4.1e-06  9.60e-01   -2.019946035e+01  -2.019820045e+01  1.1e-04  0.01  
4   5.4e-06  4.1e-06  1.7e-08  1.00e+00   -2.020942828e+01  -2.020939573e+01  2.7e-06  0.01  
5   4.5e-07  3.3e-07  4.0e-10  1.00e+00   -2.020968252e+01  -2.020967986e+01  2.2e-07  0.01  
6   4.8e-08  3.6e-08  1.4e-11  1.00e+00   -2.020970278e+01  -2.020970249e+01  2.4e-08  0.01  
7   1.3e-08  4.9e-09  7.2e-13  1.00e+00   -2.020970488e+01  -2.020970484e+01  3.3e-09  0.01  
Optimizer terminated. Time: 0.02    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -2.0209704882e+01   nrm: 4e+00    Viol.  con: 4e-08    var: 0e+00    cones: 0e+00  
  Dual.    obj: -2.0209704843e+01   nrm: 1e+00    Viol.  con: 0e+00    var: 1e-08    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.02    
    Interior-point          - iterations : 7         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): +4.2097
 
Computing the solution of the quadratic program...
 
Calling Mosek 9.1.9: 128 variables, 56 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

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                   : CONIC (conic optimization problem)
  Constraints            : 56              
  Cones                  : 16              
  Scalar variables       : 128             
  Matrix variables       : 0               
  Integer variables      : 0               

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                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 56              
  Cones                  : 16              
  Scalar variables       : 128             
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 40
Optimizer  - Cones                  : 16
Optimizer  - Scalar variables       : 128               conic                  : 48              
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 : 340               after factor           : 340             
Factor     - dense dim.             : 0                 flops                  : 6.76e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   4.0e+00  8.0e+00  2.5e+01  0.00e+00   1.600000000e+01   -8.000000000e+00  1.0e+00  0.00  
1   6.8e-01  1.4e+00  4.6e+00  -3.93e-01  -1.940066974e+01  -2.754748703e+01  1.7e-01  0.01  
2   1.3e-01  2.7e-01  4.2e-01  6.76e-01   -5.357917364e+00  -7.159690897e+00  3.3e-02  0.01  
3   4.3e-02  8.6e-02  7.5e-02  9.85e-01   -4.471826379e+00  -5.054170932e+00  1.1e-02  0.01  
4   1.7e-02  3.4e-02  1.8e-02  1.00e+00   -4.360094607e+00  -4.589807682e+00  4.2e-03  0.01  
5   6.6e-03  1.3e-02  4.3e-03  1.01e+00   -4.240156456e+00  -4.330398655e+00  1.7e-03  0.01  
6   1.8e-03  3.5e-03  5.8e-04  1.00e+00   -4.220572075e+00  -4.244669924e+00  4.4e-04  0.01  
7   2.1e-04  4.3e-04  2.4e-05  1.00e+00   -4.210448264e+00  -4.213375005e+00  5.3e-05  0.01  
8   2.8e-06  5.5e-06  3.6e-08  1.00e+00   -4.209715109e+00  -4.209753126e+00  6.9e-07  0.01  
9   6.2e-08  1.2e-07  1.2e-10  1.00e+00   -4.209705505e+00  -4.209706361e+00  1.6e-08  0.01  
10  6.1e-09  1.2e-08  3.7e-12  1.00e+00   -4.209705243e+00  -4.209705326e+00  1.5e-09  0.01  
11  6.7e-10  1.3e-09  1.3e-13  1.00e+00   -4.209705215e+00  -4.209705225e+00  1.7e-10  0.01  
Optimizer terminated. Time: 0.02    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: -4.2097052154e+00   nrm: 4e+00    Viol.  con: 2e-09    var: 1e-09    cones: 0e+00  
  Dual.    obj: -4.2097052245e+00   nrm: 2e+00    Viol.  con: 0e+00    var: 8e-10    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.02    
    Interior-point          - iterations : 11        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): +4.20971
 
------------------------------------------------------------------------
The optimal solutions for problem formulations 1, 2 and 3 are given
respectively as follows (per column): 

ans =

    0.3888    0.3888    0.3888
    0.1262    0.1262    0.1262
   -0.3337   -0.3337   -0.3337
    0.1326    0.1326    0.1326
    0.5500    0.5500    0.5500
    0.3526    0.3526    0.3526
   -0.6562   -0.6562   -0.6562
    0.8309    0.8309    0.8309