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  must be fit as closely as possible (in the least squares sense) while ensuring that some other property of  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  must exactly satisfy  (see Ordinary least squares). 
 Regularized least squares: the elements of  must satisfy  (choosing  in proportion to the noise standard deviation of y prevents over-fitting). 
 Non-negative least squares (NNLS): The vector  must satisfy the vector inequality  defined componentwise—that is, each component must be either positive or zero. 
 Box-constrained least squares: The vector  must satisfy the vector inequalities , each of which is defined componentwise. 
 Integer-constrained least squares: all elements of  must be integers (instead of real numbers). 
 Phase-constrained least squares: all elements of  must be real numbers, all multiplied by a same complex number of unit modulus. 

When the constraint only applies to some of the variables, the mixed problem may be solved using separable least squares by letting  and  represent the unconstrained (1) and constrained (2) components.  Then substituting the least-squares solution for , i.e.

(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 . 

where  is a projection matrix.  Following the constrained estimation of  the vector  is obtained from the expression above. 

See also
 Constrained optimization
 Integer programming

References

Category:Least squares