function [x,lam] = conls_lagrange(A,b,B,d)
% CONLS_LAGRANGE Equality Constrained Least Squares via Lagrange Multipliers
%
% x = conls(A,b,B,d) solves
%
%   minimize     ||b - Ax||_2
%   subject to   Bx = d
%
% when B is p-by-n, p < n, and rank(B) = p, by solving for a stationary 
% point of the Lagrangian:
%
%   [ A'*A  B' ] [  x  ] = [ A'*b]
%   [ B     0  ] [ lam ] = [  d  ]
%
% [x,lam] = conls_lagrange(...) also returns the Lagrange multipliers lam.
% 
% See also \ (backslash)

% David F. Gleich
% Purdue University
% CS 59000-OPT, Spring 2012
% Computational Methods in Optimization

[m,n] = size(A);
p = size(B,1);

assert(size(B,2) == n, 'incompatible dimensions for A and B');

% Step 1, form the block system
M = [A'*A B'; B zeros(p,p) ];

% Step 2, solve
z = M\[A'*b; d];

% Step 3, extract 
x = z(1:n);
lam = z(n+1:end);
    

