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 SeDuMi: 50 variables, 25 equality constraints
------------------------------------------------------------------------
SeDuMi 1.1R3 by AdvOL, 2006 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 25, order n = 43, dim = 52, blocks = 22
nnz(A) = 270 + 0, nnz(ADA) = 625, nnz(L) = 325
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            3.80E+001 0.000
  1 :  1.28E+001 1.12E+001 0.000 0.2946 0.9000 0.9000   2.70  1  1  1.1E+000
  2 :  1.48E+001 3.02E+000 0.000 0.2699 0.9000 0.9000   1.26  1  1  3.0E-001
  3 :  1.52E+001 9.88E-001 0.000 0.3272 0.9000 0.9000   1.07  1  1  1.0E-001
  4 :  1.54E+001 3.70E-001 0.000 0.3747 0.9000 0.9000   1.02  1  1  3.8E-002
  5 :  1.55E+001 9.39E-002 0.000 0.2537 0.9000 0.9000   1.01  1  1  9.8E-003
  6 :  1.55E+001 1.84E-002 0.000 0.1956 0.9000 0.9120   1.00  1  1  1.6E-003
  7 :  1.55E+001 2.15E-003 0.000 0.1170 0.9091 0.9000   1.00  1  1  2.1E-004
  8 :  1.55E+001 5.50E-005 0.000 0.0256 0.9905 0.9900   1.00  1  1  7.4E-006
  9 :  1.55E+001 2.49E-009 0.000 0.0000 1.0000 1.0000   1.00  1  1  2.1E-010

iter seconds digits       c*x               b*y
  9      0.1   9.7  1.5491581695e+001  1.5491581692e+001
|Ax-b| =  1.9e-010, [Ay-c]_+ =  1.7E-011, |x|= 8.4e+000, |y|= 7.8e+000

Detailed timing (sec)
   Pre          IPM          Post
3.004E-002    1.202E-001    1.001E-002    
Max-norms: ||b||=2.275599e+000, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 2.32468.
------------------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +15.4916
norm(A*x-b,1):
   ans   =   15.4916
Optimal vector:
   x     = [  0.1140  0.1739 -0.8716 -0.4524 -0.1927  0.3188 -1.2567  0.2236  0.5423  1.0767 ]
Residual vector:
   A*x-b = [ -0.2762 -0.0000 -0.6846 -0.0000  1.7275 -0.0000 -0.0149  0.0480  0.5530  1.0724  0.7873  0.0000  0.0000  0.6145 -0.5936 -1.4800  0.8559  2.3848 -1.6966 -2.7023 ]
Equality constraints:
   C*x   = [ -1.4776  0.7381 -1.0904 -1.7868  1.6391 ]
   d     = [ -1.4776  0.7381 -1.0904 -1.7868  1.6391 ]
Lagrange multiplier for C*x==d:
   y     = [  4.3036  2.2856 -3.2557 -1.3588  2.9295 ]