Constrained least squares

In constrained least squares one solves a linear least squares problem with an additional constraint on the solution. I.e., the unconstrained equation $\mathbf {X} {\boldsymbol {\beta }}=\mathbf {y}$ must be fit as closely as possible (in the least squares sense) while ensuring that some other property of ${\boldsymbol {\beta }}$ is maintained.

There are often special-purpose algorithms for solving such problems efficiently. Some examples of constraints are given below:

• Equality constrained least squares: the elements of ${\boldsymbol {\beta }}$ must exactly satisfy $\mathbf {L} {\boldsymbol {\beta }}=\mathbf {d}$ (see Ordinary least squares).
• Regularized least squares: the elements of ${\boldsymbol {\beta }}$ must satisfy $\|\mathbf {L} {\boldsymbol {\beta }}-\mathbf {y} \|\leq \alpha$ (choosing $\alpha$ in proportion to the noise standard deviation of y prevents over-fitting).
• Non-negative least squares (NNLS): The vector ${\boldsymbol {\beta }}$ must satisfy the vector inequality ${\boldsymbol {\beta }}\geq {\boldsymbol {0}}$ defined componentwise—that is, each component must be either positive or zero.
• Box-constrained least squares: The vector ${\boldsymbol {\beta }}$ must satisfy the vector inequalities ${\boldsymbol {lb}}\leq {\boldsymbol {\beta }}\leq {\boldsymbol {ub}}$, each of which is defined componentwise.
• Integer-constrained least squares: all elements of ${\boldsymbol {\beta }}$ must be integers (instead of real numbers).
• Phase-constrained least squares: all elements of ${\boldsymbol {\beta }}$ must have the same phase (or must be real rather than complex numbers, i.e. phase = 0).

When the constraint only applies to some of the variables, the mixed problem may be solved using separable least squares by letting $\mathbf {X} =[\mathbf {X_{1}} \mathbf {X_{2}} ]$ and $\mathbf {\beta } ^{\rm {T}}=[\mathbf {\beta _{1}} ^{\rm {T}}\mathbf {\beta _{2}} ^{\rm {T}}]$ represent the unconstrained (1) and constrained (2) components. Then substituting the least-squares solution for $\mathbf {\beta _{1}}$, i.e.

${\hat {\boldsymbol {\beta _{1}}}}=\mathbf {X_{1}} ^{+}(\mathbf {y} -\mathbf {X_{2}} {\boldsymbol {\beta _{2}}})$

(where ⁺ indicates the Moore-Penrose pseudoinverse) back into the original expression gives (following some rearrangement) an equation that can be solved as a purely constrained problem in $\mathbf {\beta _{2}}$.

$\mathbf {P} \mathbf {X_{2}} {\boldsymbol {\beta _{2}}}=\mathbf {P} \mathbf {y} ,$

where $\mathbf {P} :=\mathbf {I} -\mathbf {X_{1}} \mathbf {X_{1}} ^{+}$ is a projection matrix. Following the constrained estimation of ${\hat {\boldsymbol {\beta _{2}}}}$ the vector ${\hat {\boldsymbol {\beta _{1}}}}$ is obtained from the expression above.

See also

• Constrained optimization
• Integer programming