[Math] Solve a Tikhonov Regularized Least Squares Problem with Non Negative Constraints

convex optimizationinverse-problemsleast squaresoptimizationregularization

For a Tikhonov Regularized Least Squares problem with nonnegative constraints, what are some methods that solve it?

$$\begin{align*}
\arg \min_{w} \quad & \frac{1}{2} {\left\| X w – y \right\|}_{2}^{2} \\
\text{subject to} \quad & w \succeq 0
\end{align*}$$

Are methods solving a Least Squares problem with nonnegative constraints and the solution to a Tikhonov Regularized Least Squares problem helpful to the above question?

I am searching for some references to address my questions, but haven't found one yet.

Thanks in advance!

Best Answer

Let us first agree on the problem you are trying to solve. I assume you are looking at: \begin{align*} \min_{w}~&f(w):=\frac{1}{2} \Vert y-Xw\Vert +\frac{\lambda}{2}w^tw\\ s.t.~& w\geq 0 \end{align*} where $y=\begin{pmatrix}y_1\\ \vdots \\y_n\end{pmatrix}$ contains the observations, $X=\begin{pmatrix} \leftarrow & x_1 & \rightarrow\\ &\vdots&\\ \leftarrow & x_n & \rightarrow \end{pmatrix}$ the feature vectors and $w=\begin{pmatrix}w_1\\ \vdots \\ w_m \end{pmatrix}$ the weights.

The simplest algorithm you could use to solve the problem is a projected gradient method. Consider the gradient of the objective function at a point $w_k$: \begin{equation*} \nabla_w f(w_k)=(X^TX+\lambda I)w_k-X^Ty \end{equation*} and let $\Pi_C$ be the projection onto the set $C:=\{w:~w\geq 0\}$, specifically: $\Pi_C(w)=\begin{pmatrix}\tilde{w}_1\\ \vdots \\ \tilde{w}_m \end{pmatrix}$, where $\tilde{w}_i=\begin{cases} w_i &\text{if }w_i\geq 0\\ 0 &\text{else} \end{cases}$.

The projected gradient algorithm works just like the steepest descent algorithm with the addition of a projection step after the gradient step:

  • Start with a feasible $w_0$ and let $k:=1$,
  • at iteration $k$ let: \begin{align*} y_k&=w_k -\alpha \nabla_wf(w_k)\\ w_{k}&=\Pi_C(y_k)\\ k&=k+1 \end{align*} where $\alpha$ is your step length, found for example using a line search. Repeat this step until you meet your desired stopping criterion.

Look into gradient projection methods to find something more elaborate, but this should do the trick.

Related Question