Constrained Least Square

Linearly Constrained least square:

• Minimize $||Ax-b|{|}^2$ subject to $Cx=d$, equality constraints
• $\hat{x}$ is a solution of CLS if $C\hat{x}=d$ and $||A\hat{x}-b|{|}^2\le ||Ax-b|{|}^2$ holds for any $n$-vector $x$ that satisfies $Cx=d$
  • how many row of $C$ is dimension of $\lambda$
• Piecewise-polynomial fitting:
  • In the case of splitting the graph into 2 in $x$-axis, the use $p(x)$ to estimate points on the left graph and $q(x)$ for the right
  • Piecewise-polynomial $\hat{f}$ has the form:
    • $\hat{f}(x)=\{\begin{array}{ll}p(x)={\theta }_1+{\theta }_{2}x+{\theta }_3{x}^2+{\theta }_4{x}^3& x\le a\\ q(x)={\theta }_5+{\theta }_{6}x+{\theta }_7{x}^2+{\theta }_8{x}^3& x>a\end{array}$
  • To connect the graph, we need $p(a)=q(a)$ and $p^{\prime }(a)=q^{\prime }(a)$ as constraints
    • ${\theta }_1+{\theta }_{2}a+{\theta }_3{a}^2+{\theta }_4{a}^3-{\theta }_5-{\theta }_{6}a-{\theta }_7{a}^2-{\theta }_8{a}^3=0$
    • ${\theta }_2+2{\theta }_{3}a+3{\theta }_4{a}^2-{\theta }_6-2{\theta }_{7}a-3{\theta }_8{a}^2=0$
  • Then fitting is minizing ${\sum }_{i=1}^N(\hat{f}(x_i)-y_i{)}^2$ with constraints
  • Prediction error on$(x_i,y_i)$ is $a_i^{⊺}\theta -y_i$
  • Sum square error is $||A\theta -y|{|}^2$ where $a_i^{⊺}$ are the rows of $A$
• Solving CLS problem:
  • The constrants are $c_i^{⊺}x=d_i,i=1,...,p$
  • Use Lagrange Multipliers $z_1,...z_p$
    1. $L(x,z)=f(x)+z_1(c_1^{⊺}x-d_1)+...+z_p(c_p^{⊺}x-d_p)$ where $z$ is the $p$ vector of Larange
    2. Optimal conditions are: $\frac{\partial L}{\partial x_i}(\hat{x},z)=0,i=1,...,n$ and$\frac{\partial L}{\partial z_i}(\hat{x},z)=0,i=1,...,p$
  • $\frac{\partial L}{\partial z_i}(\hat{x},z)=c_i^{⊺}\hat{x}-d_i=0$ which we knew
  • first $n$ equations have form: $\frac{\partial L}{\partial x_i}(\hat{x},z)=2\sum _{j=1}^n(A^{⊺}A{)}_{ij}{\hat{x}}_j-2(A^{⊺}B{)}_i+\sum _{j=1}^p{z}_j{c}_i=0$
    • $2(A^{⊺}A)\hat{x}-2A^{⊺}b+C^{⊺}z=0$
  • Togethe with $C\hat{x}=d$ to get KKT conditions: $\left[\begin{array}{cc}2A^{⊺}A& C^{⊺}\\ C& 0\end{array}\right]\left[\begin{array}{c}\hat{x}\\ z\end{array}\right]=\left[\begin{array}{c}2A^{⊺}b\\ d\end{array}\right]$
    • a square set of $n+p$ linear equations in variable $\hat{x},$
  • Assumming KKT matrix is invertible: $\left[\begin{array}{c}\hat{x}\\ z\end{array}\right]={\left[\begin{array}{cc}2A^{⊺}A& C^{⊺}\\ C& 0\end{array}\right]}^{-1}\left[\begin{array}{c}2A^{⊺}b\\ d\end{array}\right]$
    • KKT matrix is invertible if and only if $C$ has linearly independent rows and $\left[\begin{array}{c}A\\ C\end{array}\right]$ has linearly independent columns
  • implies $m+p\ge n,p\le n$
  • Compute $\hat{x}$ in $2m{n}^2+2(n+p{)}^3$ flops, order is $n^3$ flops
  • Vertification of solution:
    • For every $x$ satisfies $Cx=d$
    • $||Ax-b|{|}^2=||(Ax-A\hat{x})+(A\hat{x}-b)|{|}^2$
      • $=||A(x-\hat{x})|{|}^2+||A\hat{x}-b|{|}^2+2(Ax-A\hat{x}{)}^{⊺}(A\hat{x}-b)$
    • expand last term, using $2A^{⊺}(A\hat{x}-b)=-C^{⊺}z,Cx=C\hat{x}=d$:
      • $2(Ax-A\hat{x}{)}^{⊺}(A\hat{x}-b)=2(x-\hat{x}{)}^{⊺}{A}^{⊺}(A\hat{x}-b)=-(x-\hat{x}{)}^{⊺}{C}^{⊺}z=-(C(x-\hat{x}){)}^{⊺}z=0$
    • so $||Ax-b|{|}^2=||A(x-\hat{x})|{|}^2+||A\hat{x}-b|{|}^2\ge ||A\hat{x}-b|{|}^2$ so $\hat{x}$ is the solution

Least-norm Problem:

• A simple case of CLS, to minimize $||x|{|}^2$
  • with $A=I,b=0$
  • subject to $Cx=d$
• Solving Least norm problem:
  • matrix $\left[\begin{array}{c}I\\ C\end{array}\right]$ always have independent columns
  • Assume that $C$ has indepent rows
  • Optimal condition reduce to $\left[\begin{array}{cc}2I& C^{⊺}\\ C& 0\end{array}\right]\left[\begin{array}{c}\hat{x}\\ z\end{array}\right]=\left[\begin{array}{c}0\\ d\end{array}\right]$
  • then $\hat{x}=-(1/2)C^{⊺}z$ and $-(1/2)C{C}^{⊺}z=d$
  • Plug $z=-2(C{C}^{⊺}{)}^{-1}d$ int the first equation to get $\hat{x}=C^{⊺}(C{C}^{⊺}{)}^{-1}d=C^{†}d$
  • so when $C$ has linearly independent rows:
    • $C^{†}$ is a right inverse of $C$
    • so for any $D,\hat{x}=C^{†}d$ satisfies $C\hat{x}=d$
    • ans we now know $\hat{x}$ is the smallest solution of $Cx=d$

Constrained least square applications:

Portfolio allocation:

• Allocate investment in a vector of $n$ different assets, $w$
  • $w_j$ is the fraction of portfolio allocated in asset $j$
  • $w_j$ can be negative, meaning short position
  • one of $w_j$ is the liquid, so $1^{⊺}w=1$
  • $w=e_n=[00...1]$ means the portfolio is all cash
• Leverage $L=|w_1|+...+|w_n|$
  • $L=1$ means all long position
  • $L>1$ means atleast 1 short position
• Return over a period
  • ${\hat{r}}_j$ is the return of asset $j$ over the period, in fractional increase or decrease in value
  • full portfolio return is $\frac{V^{+}-V}{V}={\hat{r}}^{⊺}w$
  • for $t$-period, with return $r_1,...,r_t$; then $V_{t+1}=V_1(1+r_1)(1+r_2)...(1+r_t)$
• Return matrix:
  • Hold portfolio with weights $w$ over $T$ periods
  • define $T\times n$ (assets) return matrix, with $R_{tj}$ is return of asset $j$ in period $t$
    • 1 row is return vector of 1 period, ${\tilde{r}}_t^{⊺}$
    • 1 column is the time series of 1 asset
  • if last asset is risk-free, the last column of $R$ is ${\mu }^{rf}1$ where ${\mu }^{rf}$ is the risk-free per-period interest rate
• Portfolio return and risk:
  • porfolio return vector (1 entry is return of 1 asset), $r=Rw$
  • average return is $\mathbf{avg}(r)$ and risk is $\mathbf{std}(r)$
  • for small per-period returns, we have $V_{T+1}=V_1(1+r_1)...(1+r_T)\approx V_1+V_1(r_1+...+r_T)=V_1+T\mathbf{avg}(r)V_1$
    • so return approximates the avg per-period increase of portfolio value
• Annualized return and risk:
  • Mean return and risk are often expressed in annualized form
  • If there are $P$ trading periods per year:
    • annualized return $=P\mathbf{avg}(r)$
    • annualized risk $=\sqrt{P}\mathbf{std}(r)$
• Portfolio optimization:
  • minize the risk: $\mathbf{std}(Rw{)}^2=(1/T)||Rw-\rho 1|{|}^2$
    • with constrains $1^{⊺}w=1$ and $\mathbf{avg}(Rw)=\rho$, meaning mean of past return is $\rho$
  • solution $w$ are Pareto Optimal
  • Convert to contrained least squares:
    • minize $||Rw-\rho 1|{|}^2$
    • subject to $\left[\begin{array}{c}{1}^{⊺}\\ {\mu }^{⊺}\end{array}\right]w=\left[\begin{array}{c}1\\ \rho \end{array}\right]$
  • $\mu =R^{⊺}1/T$ is $n$-vector of past asset returns
  • solution: $\left[\begin{array}{c}w\\ z_1\\ z_2\end{array}\right]={\left[\begin{array}{ccc}2R^{⊺}R& 1& \mu \\ 1^{⊺}& 0& 0\\ {\mu }^{⊺}& 0& 0\end{array}\right]}^{-1}\left[\begin{array}{c}2\rho T\mu \\ 1\\ \rho \end{array}\right]$