According to Solving Non Negative Constrained Least Squares by Analogy with Least Squares (MATLAB)
and all resources I have looked up regarding this topic, the non-negative least squares problem
$$
\min \frac 1 2 || \Phi w – y ||^2, \\
\text{s.t} \, w_i \ge 0
$$
has no closed form solution. But what if we naively do Lagrangian constraint optimization?
The Lagrangian is given by
$$
L(w, \lambda) = \frac 1 2 (\Phi w – y)^T(\Phi w – y) – \lambda^T w
$$
Taking the derivative w.r.t $w$ and setting it to $0$, we get the optimal primal solution
$$
w^* = (\Phi^T \Phi)^{-1} (\Phi^T y + \lambda).
$$
Looking at the dual function $g(\lambda) = L(w^*, \lambda)$, its derivative is given by
$$
\frac {\text{d}g} {\text d \lambda} = – (\Phi^T \Phi)^{-1} (\Phi^T y + \lambda).
$$
Setting it to zero yields
$$
\lambda = – \Phi^T y.
$$
However, we have the constraint that all multipliers need to be non-negative. This results in the dual solution
$$
\lambda^* = \max(- \Phi^T y, 0),
$$
where the $\max$ operator is defined per dimension. This results in the closed form solution
$$
w^* = (\Phi^T \Phi)^{-1} (\Phi^T y + \max(- \Phi^T y, 0)).
$$
Am I going wrong somewhere? If so, where?
Best Answer
Ok thanks to G. Fougeron, I realized that the optimal lambda cannot be obtained by just taking a maximum per dimension with $0$. While this works for a one-dimensional objective, with a multi-dimensional objective this leads to a wrong solution.