0
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ Do you have a justification for the step "This results in the dual solution" ? $\endgroup$ Nov 17, 2021 at 13:18
  • $\begingroup$ 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. $\endgroup$
    – Philipp D.
    Nov 17, 2021 at 13:25
  • $\begingroup$ Happy to help :-) $\endgroup$ Nov 17, 2021 at 13:39
  • $\begingroup$ @G.Fougeron. Just out of curiosity : may I ask where you are located ? I am in Pau. Cheers :-) $\endgroup$ Nov 17, 2021 at 13:45
  • $\begingroup$ I'm in the Paris area $\endgroup$ Nov 17, 2021 at 13:46

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .