Equality constrained norm minimization.

% This script constructs a random equality-constrained norm minimization
% problem and solves it using CVX. You can also change p to +2 or +Inf
% to produce different results. Alternatively, you an replace
%     norm( A * x - b, p )
% with
%     norm_largest( A * x - b, 'largest', p )
% for 1 <= p <= 2 * n.

% Generate data
p = 1;
n = 10; m = 2*n; q=0.5*n;
A = randn(m,n);
b = randn(m,1);
C = randn(q,n);
d = randn(q,1);

% Create and solve problem
cvx_begin
   variable x(n)
   dual variable y
   minimize( norm( A * x - b, p ) )
   subject to
        y : C * x == d;
cvx_end

% Display results
disp( sprintf( 'norm(A*x-b,%g):', p ) );
disp( [ '   ans   =   ', sprintf( '%7.4f', norm(A*x-b,p) ) ] );
disp( 'Optimal vector:' );
disp( [ '   x     = [ ', sprintf( '%7.4f ', x ), ']' ] );
disp( 'Residual vector:' );
disp( [ '   A*x-b = [ ', sprintf( '%7.4f ', A*x-b ), ']' ] );
disp( 'Equality constraints:' );
disp( [ '   C*x   = [ ', sprintf( '%7.4f ', C*x ), ']' ] );
disp( [ '   d     = [ ', sprintf( '%7.4f ', d   ), ']' ] );
disp( 'Lagrange multiplier for C*x==d:' );
disp( [ '   y     = [ ', sprintf( '%7.4f ', y ), ']' ] );
 
Calling SDPT3: 50 variables, 25 equality constraints
------------------------------------------------------------

 num. of constraints = 25
 dim. of socp   var  = 40,   num. of socp blk  = 20
 dim. of free   var  = 10 *** convert ublk to lblk
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
    NT      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      mean(obj)   cputime
-------------------------------------------------------------------
 0|0.000|0.000|8.4e-01|2.7e+01|1.3e+04| 3.191300e+01| 0:0:00| chol  1  1 
 1|1.000|0.898|2.8e-06|2.8e+00|6.5e+02| 1.258539e+02| 0:0:00| chol  1  1 
 2|1.000|0.984|7.2e-07|5.4e-02|2.8e+01| 2.647776e+01| 0:0:00| chol  1  1 
 3|0.887|0.880|3.2e-06|7.3e-03|3.7e+00| 2.016862e+01| 0:0:00| chol  1  1 
 4|0.891|0.522|1.3e-06|3.5e-03|9.9e-01| 1.946980e+01| 0:0:00| chol  1  1 
 5|0.975|0.551|1.4e-07|1.6e-03|3.4e-01| 1.950669e+01| 0:0:00| chol  1  1 
 6|0.983|0.943|2.3e-08|9.0e-05|1.8e-02| 1.962957e+01| 0:0:00| chol  1  1 
 7|0.988|0.988|4.5e-09|1.2e-06|2.1e-04| 1.963720e+01| 0:0:00| chol  1  1 
 8|0.989|0.989|6.6e-10|1.5e-06|8.0e-06| 1.963729e+01| 0:0:00| chol  1  1 
 9|0.577|0.945|2.8e-10|5.4e-08|4.1e-07| 1.963729e+01| 0:0:00| chol  1  1 
10|0.533|0.943|1.3e-10|2.8e-09|5.9e-08| 1.963729e+01| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 10
 primal objective value =  1.96372933e+01
 dual   objective value =  1.96372933e+01
 gap := trace(XZ)       = 5.92e-08
 relative gap           = 1.47e-09
 actual relative gap    = 1.12e-09
 rel. primal infeas     = 1.31e-10
 rel. dual   infeas     = 2.85e-09
 norm(X), norm(y), norm(Z) = 8.2e+00, 6.7e+00, 6.0e+00
 norm(A), norm(b), norm(C) = 2.2e+01, 6.2e+00, 5.5e+00
 Total CPU time (secs)  = 0.2  
 CPU time per iteration = 0.0  
 termination code       =  0
 DIMACS: 2.4e-10  0.0e+00  7.8e-09  0.0e+00  1.1e-09  1.5e-09
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +19.6373
norm(A*x-b,1):
   ans   =   19.6373
Optimal vector:
   x     = [  0.0454  0.7771 -0.4288 -0.2071 -0.6081  0.0065 -0.0013  0.0645 -0.3340 -0.6522 ]
Residual vector:
   A*x-b = [ -0.0000 -1.0527 -0.7833  1.6843  0.1257  2.5993  1.2661 -0.0000  0.2758 -1.6365 -0.9791  2.6851  0.8774 -0.8686  0.0000  1.6512 -0.0000  1.5824 -0.0000  1.5699 ]
Equality constraints:
   C*x   = [ -1.0290  0.2431 -1.2566 -0.3472 -0.9414 ]
   d     = [ -1.0290  0.2431 -1.2566 -0.3472 -0.9414 ]
Lagrange multiplier for C*x==d:
   y     = [ -3.6360  3.0466 -2.1301 -1.2477  0.1630 ]