BCLS

Michael P. Friedlander
May 2007

BCLS is a software package for solving bound-constrained least-squares problems of the form

$$ \begin{array}{ll} \displaystyle\mathop{\hbox{minimize}}_x & \frac12\Vert Ax-b\Vert _2^2 + \mu\frac12\Vert x\Vert _2^2 + c^T x\ \\ \hbox{subject to} & \ell \le x \le u. \end{array} $$

The m-by-n matrix \(A\) can be any shape. The regularization and linear terms are optional. The vectors \(\ell\) and \(u\) define upper and lower bounds on the variables \(x\). Free and fixed variables are easily accomodated by setting corresponding components of \(\ell\) and \(u\) to be \(-\infty\) and \(+\infty\), or by setting them equal to each other.

BCLS implements a two-metric projected-descent method. At each iteration, a search direction is computed that is a combination of a Newton and a scaled steepest-descent step.

Some notable features of the implementation:

• The matrix \(A\) is used only as an operator. The user needs only to provide a routine to compute the matrix-vector produts \(Ax\) and \(A^T y.\)
• The algorithm can take advantage of good starting points, and is capable of making very large changes to the “active-set” at each iteration.
• The normal equations are never formed.
• The user may provide perconditioners in order to accelerate the solution of the subproblems.

BCLS is written in ISO C and should compile on most systems (thanks for the Autoconf/Automake tools). No additional software is required, though there should be a significant speedup if it is compiled against a tuned BLAS library such as ATLAS. It has been tested using GCC on GNU/Linux, Mac OS X, and Windows XP (under MinGW). License BCLS is open-source software released under the lGPL license. Feel free to use it in any way you wish. If you find it at all useful, I’d like to hear from you, please send email.