Constrained least squares: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 01:23, 5 August 2024

In constrained least squares one solves a linear least squares problem with an additional constraint on the solution.^[1]^[2] This means, 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).
Stochastic (linearly) constrained least squares: the elements of ${\boldsymbol {\beta }}$ must satisfy $\mathbf {L} {\boldsymbol {\beta }}=\mathbf {d} +\mathbf {\nu }$ , where $\mathbf {\nu }$ is a vector of random variables such that $\operatorname {E} (\mathbf {\nu } )=\mathbf {0}$ and $\operatorname {E} (\mathbf {\nu } \mathbf {\nu } ^{\rm {T}})=\tau ^{2}\mathbf {I}$ . This effectively imposes a prior distribution for ${\boldsymbol {\beta }}$ and is therefore equivalent to Bayesian linear regression.^[3]
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 {b}}_{\ell }\leq {\boldsymbol {\beta }}\leq {\boldsymbol {b}}_{u}$ , 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 be real numbers, or multiplied by the same complex number of unit modulus.

If the constraint only applies to some of the variables, the mixed problem may be solved using separable least squares^[4] 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.

References

^ Amemiya, Takeshi (1985). "Model 1 with Linear Constraints". Advanced Econometrics. Oxford: Basil Blackwell. pp. 20–26. ISBN 0-631-15583-X.
^ Boyd, Stephen; Vandenberghe, Lieven (2018). Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares. Cambridge University Press. ISBN 978-1-316-51896-0.
^ Fomby, Thomas B.; Hill, R. Carter; Johnson, Stanley R. (1988). "Use of Prior Information". Advanced Econometric Methods (Corrected softcover ed.). New York: Springer-Verlag. pp. 80–121. ISBN 0-387-96868-7.
^ Bjork, Ake (1996). "Separable and Constrained Problems". Numerical Methods for Least Squares Problems. Philadelphia: SIAM. p. 351. ISBN 0898713609.

[1] Amemiya, Takeshi (1985). "Model 1 with Linear Constraints". Advanced Econometrics. Oxford: Basil Blackwell. pp. 20–26. ISBN 0-631-15583-X.

[BoydVandenberghe2018-2] Boyd, Stephen; Vandenberghe, Lieven (2018). Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares. Cambridge University Press. ISBN 978-1-316-51896-0.

[3] Fomby, Thomas B.; Hill, R. Carter; Johnson, Stanley R. (1988). "Use of Prior Information". Advanced Econometric Methods (Corrected softcover ed.). New York: Springer-Verlag. pp. 80–121. ISBN 0-387-96868-7.

[4] Bjork, Ake (1996). "Separable and Constrained Problems". Numerical Methods for Least Squares Problems. Philadelphia: SIAM. p. 351. ISBN 0898713609.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-{{unreferenced|date=July 2018}}
+{{more citations needed|date=July 2018}}
-In '''constrained least squares''' one solves a [[linear least squares (mathematics)|linear least squares]] problem with an additional constraint on the solution.
+In '''constrained least squares''' one solves a [[linear least squares (mathematics)|linear least squares]] problem with an additional [[constraint (mathematics)|constraint]] on the solution.<ref>{{cite book |first=Takeshi |last=Amemiya |authorlink=Takeshi Amemiya |title=Advanced Econometrics |location=Oxford |publisher=Basil Blackwell |year=1985 |isbn=0-631-15583-X |chapter=Model 1 with Linear Constraints |pages=20–26 }}</ref><ref name="BoydVandenberghe2018">{{cite book|first=Stephen |last=Boyd |first2=Lieven |last2=Vandenberghe|title=Introduction to Applied Linear Algebra: Vectors, Matrices, and Least Squares|url=https://books.google.com/books?id=IApaDwAAQBAJ&q=%22Constrained+least+squares%22|year=2018|publisher=Cambridge University Press|isbn=978-1-316-51896-0}}</ref>
-I.e., the unconstrained equation <math>\mathbf {X} \boldsymbol {\beta} = \mathbf {y}</math> must be fit as closely as possible (in the least squares sense) while ensuring that some other property of <math>\boldsymbol {\beta}</math> is maintained.
+This means, the unconstrained equation <math>\mathbf {X} \boldsymbol {\beta} = \mathbf {y}</math> must be fit as closely as possible (in the least squares sense) while ensuring that some other property of <math>\boldsymbol {\beta}</math> is maintained.
 There are often special-purpose algorithms for solving such problems efficiently. Some examples of constraints are given below:
 * [[Constrained generalized inverse|Equality constrained]] least squares: the elements of <math>\boldsymbol {\beta}</math> must exactly satisfy <math>\mathbf {L} \boldsymbol {\beta} = \mathbf {d}</math> (see [[Ordinary least squares#Constrained estimation|Ordinary least squares]]).
+* Stochastic (linearly) constrained least squares: the elements of <math>\boldsymbol {\beta}</math> must satisfy <math>\mathbf {L} \boldsymbol {\beta} = \mathbf {d} + \mathbf {\nu}</math>, where <math>\mathbf {\nu}</math> is a vector of random variables such that <math>\operatorname{E}(\mathbf {\nu}) = \mathbf{0}</math> and <math>\operatorname{E}(\mathbf {\nu} \mathbf {\nu}^{\rm T}) = \tau^{2}\mathbf{I}</math>. This effectively imposes a [[prior distribution]] for <math>\boldsymbol {\beta}</math> and is therefore equivalent to [[Bayesian linear regression]].<ref>{{cite book |first=Thomas B. |last=Fomby |first2=R. Carter |last2=Hill |first3=Stanley R. |last3=Johnson |title=Advanced Econometric Methods |location=New York |publisher=Springer-Verlag |edition=Corrected softcover |year=1988 |isbn=0-387-96868-7 |chapter=Use of Prior Information |pages=80–121 }}</ref>
 * [[Tikhonov regularization|Regularized]] least squares: the elements of <math>\boldsymbol {\beta}</math> must satisfy <math>\| \mathbf {L} \boldsymbol {\beta} - \mathbf {y} \| \le \alpha </math> (choosing <math>\alpha</math> in proportion to the noise standard deviation of '''y''' prevents over-fitting).
 * [[Non-negative least squares]] (NNLS): The vector <math>\boldsymbol {\beta}</math> must satisfy the [[ordered vector space|vector inequality]] <math>\boldsymbol {\beta} \geq \boldsymbol{0}</math> defined componentwise—that is, each component must be either positive or zero.
-* Box-constrained least squares: The vector <math>\boldsymbol {\beta}</math> must satisfy the [[ordered vector space|vector inequalities]] <math> \boldsymbol{lb} \leq \boldsymbol{\beta} \leq \boldsymbol{ub}</math>, each of which is defined componentwise.
+* Box-constrained least squares: The vector <math>\boldsymbol {\beta}</math> must satisfy the [[ordered vector space|vector inequalities]] <math> \boldsymbol{b}_\ell \leq \boldsymbol{\beta} \leq \boldsymbol{b}_u</math>, each of which is defined componentwise.
 * Integer-constrained least squares: all elements of <math>\boldsymbol {\beta}</math> must be [[integer]]s (instead of [[real number]]s).
-* Phase-constrained least squares: all elements of <math>\boldsymbol {\beta}</math> must be real numbers, all multiplied by a same complex number of unit modulus).
+* Phase-constrained least squares: all elements of <math>\boldsymbol {\beta}</math> must be real numbers, or multiplied by the 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 <math>\mathbf {X} = [\mathbf {X_1} \mathbf {X_2} ]</math> and <math>\mathbf {\beta}^{\rm T} = [\mathbf {\beta_1}^{\rm T} \mathbf {\beta_2}^{\rm T}]</math> represent the unconstrained (1) and constrained (2) components. Then substituting the least-squares solution for <math>\mathbf {\beta_1}</math>, i.e.
+If the constraint only applies to some of the variables, the mixed problem may be solved using '''separable least squares'''<ref>{{cite book |first=Ake |last=Bjork |title=Numerical Methods for Least Squares Problems |location=Philadelphia |publisher=SIAM |year=1996 | isbn=0898713609| chapter=Separable and Constrained Problems |pages=351 }}</ref> by letting <math>\mathbf {X} = [\mathbf {X_1} \mathbf {X_2} ]</math> and <math>\mathbf {\beta}^{\rm T} = [\mathbf {\beta_1}^{\rm T} \mathbf {\beta_2}^{\rm T}]</math> represent the unconstrained (1) and constrained (2) components. Then substituting the least-squares solution for <math>\mathbf {\beta_1}</math>, i.e.
-:<math>\hat{\boldsymbol {\beta_1}} = \mathbf {X_1}^+ (\mathbf {y} - \mathbf {X_2} \boldsymbol {\beta_2})</math>
+:<math>\hat{\boldsymbol {\beta}}_1 = \mathbf {X}_1^+ (\mathbf {y} - \mathbf {X}_2 \boldsymbol {\beta}_2)</math>
-(where <sup>+</sup> 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 <math>\mathbf {\beta_2}</math>.
+(where <sup>+</sup> 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 <math>\mathbf {\beta}_2</math>.
-:<math> \mathbf{P} \mathbf {X_2} \boldsymbol {\beta_2} = \mathbf{P}\mathbf {y},</math>
+:<math> \mathbf{P} \mathbf {X}_2 \boldsymbol {\beta}_2 = \mathbf{P}\mathbf {y},</math>
-where <math>\mathbf{P}:=\mathbf{I}-\mathbf {X_1} \mathbf {X_1}^+</math> is a [[projection matrix]]. Following the constrained estimation of <math>\hat{\boldsymbol {\beta_2}}</math> the vector <math>\hat{\boldsymbol {\beta_1}}</math> is obtained from the expression above.
+where <math>\mathbf{P}:=\mathbf{I}-\mathbf {X}_1 \mathbf {X}_1^+</math> is a [[projection matrix]]. Following the constrained estimation of <math>\hat{\boldsymbol \beta}_2</math> the vector <math>\hat{\boldsymbol {\beta}}_1</math> is obtained from the expression above.
 ==See also==
+* [[Bayesian linear regression]]
 * [[Constrained optimization]]
 * [[Integer programming]]
+==References==
+{{Reflist}}
 [[Category:Least squares]]