# Why is this not a closed form solution to non-negative Least squares?

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?

• Do you have a justification for the step "This results in the dual solution" ? Nov 17, 2021 at 13:18
• Ah I see the problem, I generalized from the one-dimensional convex problem that if the optimum is at a negative point, you can simply clamp it to zero. However, in multidimensional problems this might not be the correct solution. Nov 17, 2021 at 13:25
• Happy to help :-) Nov 17, 2021 at 13:39
• @G.Fougeron. Just out of curiosity : may I ask where you are located ? I am in Pau. Cheers :-) Nov 17, 2021 at 13:45
• I'm in the Paris area Nov 17, 2021 at 13:46

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.