Constrained least squares

In constrained least squares one solves a <a href="/facts/Linear_least_squares_(mathematics)/dKctFUCV">linear least squares</a> problem with an additional <a href="/facts/Constraint_(mathematics)/QLFIFlFX">constraint</a> on the solution. 
This means, the unconstrained equation 
 
 
 
 
 X
 
 
 β
 
 =
 
 y
 
 
 
 {\displaystyle \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 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 is maintained.
There are often special-purpose algorithms for solving such problems efficiently. Some examples of constraints are given below:

<ul><li><a href="/facts/Constrained_generalized_inverse/pzyRe6Mq">Equality constrained</a> least squares: the elements of 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must exactly satisfy 
 
 
 
 
 L
 
 
 β
 
 =
 
 d
 
 
 
 {\displaystyle \mathbf {L} {\boldsymbol {\beta }}=\mathbf {d} }
 
 (see <a href="/facts/Ordinary_least_squares/q7H9k5vM">Ordinary least squares</a>).</li>
<li>Stochastic (linearly) constrained least squares: the elements of 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must satisfy 
 
 
 
 
 L
 
 
 β
 
 =
 
 d
 
 +
 
 ν
 
 
 
 {\displaystyle \mathbf {L} {\boldsymbol {\beta }}=\mathbf {d} +\mathbf {\nu } }
 
, where 
 
 
 
 
 ν
 
 
 
 {\displaystyle \mathbf {\nu } }
 
 is a vector of random variables such that 
 
 
 
 E
 ⁡
 (
 
 ν
 
 )
 =
 
 0
 
 
 
 {\displaystyle \operatorname {E} (\mathbf {\nu } )=\mathbf {0} }
 
 and 
 
 
 
 E
 ⁡
 (
 
 ν
 
 
 
 ν
 
 
 
 T
 
 
 
 )
 =
 
 τ
 
 2
 
 
 
 I
 
 
 
 {\displaystyle \operatorname {E} (\mathbf {\nu } \mathbf {\nu } ^{\rm {T}})=\tau ^{2}\mathbf {I} }
 
. This effectively imposes a <a href="/facts/Prior_distribution/JQKAD4o0">prior distribution</a> for 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 and is therefore equivalent to <a href="/facts/Bayesian_linear_regression/7Dj2c1PQ">Bayesian linear regression</a>.</li>
<li><a href="/facts/Tikhonov_regularization/eq6kH8PX">Regularized</a> least squares: the elements of 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must satisfy 
 
 
 
 ‖
 
 L
 
 
 β
 
 −
 
 y
 
 ‖
 ≤
 α
 
 
 {\displaystyle \|\mathbf {L} {\boldsymbol {\beta }}-\mathbf {y} \|\leq \alpha }
 
 (choosing 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 in proportion to the noise standard deviation of y prevents over-fitting).</li>
<li><a href="/facts/Non-negative_least_squares/eryWp2Xu">Non-negative least squares</a> (NNLS): The vector 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must satisfy the <a href="/facts/Ordered_vector_space/yN9VfKMa">vector inequality</a> 
 
 
 
 
 β
 
 ≥
 
 0
 
 
 
 {\displaystyle {\boldsymbol {\beta }}\geq {\boldsymbol {0}}}
 
 defined componentwise—that is, each component must be either positive or zero.</li>
<li>Box-constrained least squares: The vector 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must satisfy the <a href="/facts/Ordered_vector_space/yN9VfKMa">vector inequalities</a> 
 
 
 
 
 
 b
 
 
 ℓ
 
 
 ≤
 
 β
 
 ≤
 
 
 b
 
 
 u
 
 
 
 
 {\displaystyle {\boldsymbol {b}}_{\ell }\leq {\boldsymbol {\beta }}\leq {\boldsymbol {b}}_{u}}
 
, each of which is defined componentwise.</li>
<li>Integer-constrained least squares: all elements of 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must be <a href="/facts/Integer/PUwwrawx">integers</a> (instead of <a href="/facts/Real_number/R02gw5Pb">real numbers</a>).</li>
<li>Phase-constrained least squares: all elements of 
 
 
 
 
 β
 
 
 
 {\displaystyle {\boldsymbol {\beta }}}
 
 must be real numbers, or multiplied by the same complex number of unit modulus.</li></ul>
If the constraint only applies to some of the variables, the mixed problem may be solved using separable least squares by letting 
 
 
 
 
 X
 
 =
 [
 
 
 X
 
 1
 
 
 
 
 
 X
 
 2
 
 
 
 ]
 
 
 {\displaystyle \mathbf {X} =[\mathbf {X_{1}} \mathbf {X_{2}} ]}
 
 and 
 
 
 
 
 
 β
 
 
 
 T
 
 
 
 =
 [
 
 
 
 β
 
 1
 
 
 
 
 
 T
 
 
 
 
 
 
 β
 
 2
 
 
 
 
 
 T
 
 
 
 ]
 
 
 {\displaystyle \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 
 
 
 
 
 
 β
 
 1
 
 
 
 
 
 {\displaystyle \mathbf {\beta _{1}} }
 
, i.e.

β
                ^
              
            
          
          
            1
          
        
        =
        
          
            X
          
          
            1
          
          
            +
          
        
        (
        
          y
        
        −
        
          
            X
          
          
            2
          
        
        
          
            β
          
          
            2
          
        
        )
      
    
    {\displaystyle {\hat {\boldsymbol {\beta }}}_{1}=\mathbf {X} _{1}^{+}(\mathbf {y} -\mathbf {X} _{2}{\boldsymbol {\beta }}_{2})}

(where + indicates the <a href="/facts/Moore%25E2%2580%2593Penrose_pseudoinverse/CU73tntq">Moore–Penrose pseudoinverse</a>) back into the original expression gives (following some rearrangement) an equation that can be solved as a purely constrained problem in 
 
 
 
 
 
 β
 
 
 2
 
 
 
 
 {\displaystyle \mathbf {\beta } _{2}}
 
.

P
        
        
          
            X
          
          
            2
          
        
        
          
            β
          
          
            2
          
        
        =
        
          P
        
        
          y
        
        ,
      
    
    {\displaystyle \mathbf {P} \mathbf {X} _{2}{\boldsymbol {\beta }}_{2}=\mathbf {P} \mathbf {y} ,}

where 
 
 
 
 
 P
 
 :=
 
 I
 
 −
 
 
 X
 
 
 1
 
 
 
 
 X
 
 
 1
 
 
 +
 
 
 
 
 {\displaystyle \mathbf {P} :=\mathbf {I} -\mathbf {X} _{1}\mathbf {X} _{1}^{+}}
 
 is a <a href="/facts/Projection_matrix/5bLbzjy9">projection matrix</a>. Following the constrained estimation of 
 
 
 
 
 
 
 
 β
 ^
 
 
 
 
 2
 
 
 
 
 {\displaystyle {\hat {\boldsymbol {\beta }}}_{2}}
 
 the vector 
 
 
 
 
 
 
 
 β
 ^
 
 
 
 
 1
 
 
 
 
 {\displaystyle {\hat {\boldsymbol {\beta }}}_{1}}
 
 is obtained from the expression above.

Constrained least squares open-in-new

Constrained least squares