Solving box-constrained least-squares

Question

I have a linear least squares problem with linear constraints:

$$\min_x \| A x - b \|^2 \quad\text{subject to}\quad k_1 \leq x_i \leq k_2$$

Should quadratic programming be used here? If so, what would the formulation be?

Answer 1

What should be used may depend on what software you are using. Maple has a command LSSolve in its Optimization package to handle least-squares problems, including linearly-constrained ones. It uses an active-set method.

Answer 2

You can either solve it by a special solver (As noted by other answers) or use Gradient Descent where each iteration you project the solution onto the box of the constraints.

It will be something like that:

$$ \begin{align*} {x}^{k + 1} & = {x}^{k} - \alpha ( {A}^{T} \left( A {x}^{k} - b \right) \\ {x}^{k + 2} & = \max \left\{ \min \left\{ {x}^{k + 1}, {k}_{2} \right\}, {k}_{1} \right\} \end{align*} $$

Where $ \alpha $ is the step size in the Gradient Descent.