🚀 go-pugleaf

In article <1992Nov20.182350.8925@midway.uchicago.edu> ngo1@midway.uchicago.edu writes:
>I have a problem:  minimize (Y - Xb)'(Y - Xb) with respect to b
> subject to Cb = d.  b  is a px1 vector and C is a qxp matrix.
> The matrix X may not be full rank (i.e., rank(X) = r < p).
> 
> A solution is given in Kennedy and Gentle, the solution is
>
>  b = (X'X + C'C)^{-1} X'Y.
>
> Can anyone show me other methods/solutions to this constrained
> LS problem?  Thanks in advance.
>
> H.Y. Ngo
> ngo1@midway.uchicago.edu 

The formula you have written down seems to be wrong. In particular,
it does not include the vector d.

There are two general approaches to constraints of this type.
The first is to determine a (preferably orthogonal) transformation
Q such that CQ = (R 0), where R is square.  Then with Q'b = (s', t')'
we have (R 0)(s', t')' = Rs = d, so that s is uniquely determined
(I am assuming R is nonsingular).  Setting XQ = (V W), we obtain
a reduced least squares problem of minimizing the norm of
(Y - Vs) - Wt, which can be solved for t in the usual way.

This algorithm is somewhat difficult to code.  An alternative, which
uses off-the-shelf software is to solve the least squares problem
of minimizing

                            |mu d|   |mu C|
                            |    | - |    |b
                            | Y  |   | X  |

for some suitably large mu.  In this approach, it is essential that
you *not* use the normal equations, since C will swamp X in the cross
product matrix (X'X + mu C'C).  Instead use a QR factorization with
column pivoting (from, say, LINPACK or LAPACK).  The order of things,
constraints first, is important.  I am appending a dump on the subject
from my personal bibliography.  For the second method, see the paper
by Van Loan.

Pete Stewart

\begin{thebibliography}{10}

\bibitem{barl:88}
J.~L. Barlow.
\newblock Error analysis and implementation aspects of deferred correction for
  equality constrained least squares problems.
\newblock {\em SIAM Journal on Numerical Analysis}, 25:1340--1358, 1988.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{baha:88}
J.~L. Barlow and S.~L. Handy.
\newblock The direct solution of weighted and equality constrained
  least-squares problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  9:704--716, 1988.

\bibitem{banp:88}
J.~L. Barlow, N.~K. Nichols, and R.~J. Plemmons.
\newblock Iterative methods for equality-constrained least squares problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  9:892--906, 1988.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{bjor:84}
{\AA}.~Bj{\"o}rck.
\newblock A general updating algorithm for constrained linear least squares
  problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  5:394--402., 1984.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{eila:75}
E.~L. Eichhorn and C.~L. Lawson.
\newblock An {ALGOL} procedure for solution of constrained least squares
  problems.
\newblock Computing Memorandum No. 374, JPL, Pasadena, California, 1975.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{elde:77a}
L.~Eld{\`e}n.
\newblock {\em Numerical Analysis of Regularization and Constrained Least
  Square Methods}.
\newblock PhD thesis, Linkoping Studies in Science and Technology, Linkoping,
  Sweden, 1977.
\newblock Cited in \cite{govl:89}.

\bibitem{elde:80}
L.~Eld\'en.
\newblock Perturbation theory for the least squares problem with linear
  equality constraints.
\newblock {\em SIAM Journal on Numerical Analysis}, 17:338--350, 1980.

\bibitem{elde:83}
L.~Eld\'en.
\newblock A weighted pseudoinverse, generalized singular values, and
  constrained least squares problems.
\newblock {\em BIT}, 22:487--502, 1983.

\bibitem{govl:89}
G.~H. Golub and C.~F. Van~Loan.
\newblock {\em Matrix Computations}.
\newblock Johns Hopkins University Press, Baltimore, Maryland, 2nd edition,
  1989.

\bibitem{hans:86}
R.~J. Hanson.
\newblock Linear least squares with bounds and linear constraints.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  7:826--834, 1986.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{haha:81}
K.~H. Haskell and R.~J. Hanson.
\newblock An algorithm for linear least squares problems with equality and
  nonnegativity constraints.
\newblock {\em Mathematical Programming}, 21:98--118, 1981.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{kopa:81}
S.~Kourouklis and C.~C. Paige.
\newblock A constrained approach to the general {Gauss-Markov} linear model.
\newblock {\em Journal of the American Statistical Association}, 76:620--625,
  1981.

\bibitem{lewe:70}
{\"O.}~Leringe and P.-\AA. Wedin.
\newblock A comparison between different methods to compute a vector $x$ which
  minimizes {$\|Ax-b\|_2$} when {$Gx=h$}.
\newblock Technical report, Department of Computer Science, Lund University,
  1970.

\bibitem{mova:91}
M.~Moonen and J.~Vandewalle.
\newblock A square root covariance algorithm for constrained recursive least
  squares estimation.
\newblock {\em Journal of VLSI Signal Processing}, 3:163--172, 1991.

\bibitem{schi:83}
K.~Schittkowski.
\newblock The numerical solution of constrained linear least-squares problems.
\newblock {\em IMA J. Numer. Anal.}, 3:11--36, 1983.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{scst:79}
K.~Schittkowski and J.~Stoer.
\newblock A factorization method for the solution of constrained linear least
  squares problems allowing subsequent data changes.
\newblock {\em Numerische Mathematik}, 31:431--463, 1979.

\bibitem{shmw:87}
T.~J. Shepherd and J.~G. McWhirter.
\newblock A pipelined array for linearly constrained least squares
  optimization.
\newblock In T.~S. Durrani, J.~B. Abbiss, J.~E. Hudson, R.~W. Madan, J.~G.
  McWhirter, and T.~A. Moore, editors, {\em Mathematics in Signal Processing},
  pages 607--635, Oxford, 1987. Clarendon Press.
\newblock Cited in \cite{mova:91}.

\bibitem{stoe:71}
J.~Stoer.
\newblock On the numerical solution of constrained least-squares problems.
\newblock {\em SIAM Journal on Numerical Analysis}, 8:382--411, 1971.

\bibitem{vloa:85}
C.~F. Van~Loan.
\newblock On the method of weighting for equality constrained least squares.
\newblock {\em SIAM Journal on Numerical Analysis}, 22:851--864, 1985.

\bibitem{wedi:79}
P.-{\AA}. Wedin.
\newblock Notes on the constrained linear least squares problem. a new approach
  based on generalized inverses.
\newblock Technical Report UMINF--75.79, Institute of Information Processing,
  University of Ume\aa, 1979.

\bibitem{wedi:85}
P.-{\AA}. Wedin.
\newblock Perturbation theory and condition numbers for generalized and
  constrained linear least squares problems.
\newblock Technical Report UMINF--125.85, Institute of Information Processing,
  University of Ume\aa, 1985.

\bibitem{wedi:87}
P.-{\AA}. Wedin.
\newblock Perturbation theory and condition numbers for generalized and
  constrained least squares problems.
\newblock Technical Report S-901-87, Institute of Information Processing,
  University of Ume\aa, 1987.

\bibitem{wei:92}
M.~Wei.
\newblock Pertrubation theory for the rank-deficient equality constrained least
  squares problem.
\newblock {\em SIAM Journal on Numerical Analysis}, 29:1462--1481, 1992.

\end{thebibliography}

ngo1@quads.uchicago.edu (hang-yue  ngo) writes:

>I have a problem:  minimize (Y - Xb)'(Y - Xb) with respect to b
> subject to Cb = d.  b  is a px1 vector and C is a qxp matrix.
> The matrix X may not be full rank (i.e., rank(X) = r < p).
> 
> A solution is given in Kennedy and Gentle, the solution is

>  b = (X'X + C'C)^{-1} X'Y.

> Can anyone show me other methods/solutions to this constrained
> LS problem?  Thanks in advance.

If you look in Kennedy and Gentle again you will see that this
"solution" is in fact a solution only for the case where d = 0.

One intuitive solution to the general problem can be obtained by
noting that Cb = d if and only if b = Az + e for some z in R^(p-q),
where A is any px(p-q) matrix of rank p-q for which CA = 0, and e is
any particular solution to the equation Ce = d.  So the constrained
problem is equivalent to the unconstrained problem:

	min (Y - Xe - XAz)'(Y - Xe - XAz)
	 z

which has solution

	z = (A'X'XA)^(-1)A'X'(Y - Xe)

assuming that the inverse exists.  (If not, then there is no unique
solution to the original problem, and you need some additional
criteria, minimum norm, perhaps, to pin down a unique solution.)

Substituting into the identity b = Az + e gives a final solution:

	b = A(A'X'XA)^(-1)A'X'(Y - Xe) + e

The choice of the matrix A and the vector e does not affect the
theoretical solution but may influence numerical stability of this
approach.  Someone else has already posted numerous references to
articles on the numerical aspects of the problem.

The problem is also fairly easy to solve using a vector of LaGrange
multipliers to handle the constraints.
--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209