Can it be proven that NNLS is a perfectly convex problem?
Myre writes in section 3 of his TNT-NN manuscript:
The NNLS objective function is a convex quadratic function with linear inequalities as constraints. The whole NNLS problem, therefore, is convex and any feasible solution can be found from another feasible point
Wikipedia contributors seem to agree, see Quadratic Programming in NNLS.
This problem is convex, as Q is positive semidefinite and the non-negativity constraints form a convex feasible set.
Indeed, sequential coordinate descent is built on the premise of a perfectly convex solution path, see Franc et al., where it is directly asserted that the distance to the optimal solution may be measured from any point:
We also derive stopping conditions which allow to control the distance of the solution found to the optimal one in terms of the optimized objective function
I've recently been able to show that all NNLS algorithms give the same result (i.e. Lawson-Hanson nnls, multiway fnnls, TNT-NN, and sequential coordinate descent). I owe a bit of credit to this SE question here. Note that all of these methods assume the problem is convex.
However, what if non-negative least squares is not a "perfectly convex" problem?
Here's my reasoning. Given any
ax-b where columns in symmetric positive definite
a are not of singular cardinality (usually the case), there will be "interaction" between variables. By "interaction", I mean that signals are overlapping, and thus mutually informative, and thus may both be used to explain potentially very similar signal. Now imagine interactions between these interactions -- higher-order interactions -- that might divert coordinate descent into a local minima trough. Because these interactions are higher-order, they would require significant alterations to active set membership and thus prevent discovery of the true minima by convex optimization methods.
In other words, coordinate descent (and active set selection methods) will always chase the variables that are immediately most explanatory. Consider that this may lead to a local minima, one that is nearly as good as the global minima but nowhere close in space to the global minima.
Apologies for my naive description, hopefully I've conveyed the thought.
Is NNLS not always convex optimization problem, and if so, how might we find the global minima?
Reprex where NNLS fails to find global minima:
Consider a random
a and random
set.seed(123) A <- matrix(runif(1:1000), 25, 10) b <- runif(1:10)*0.1 a <- t(A) %*% A
Let's solve this problem with non-negative least squares and calculate absolute error:
library(multiway) x_fnnls <- fnnls(a, b) mean(abs(as.vector(a %*% x_fnnls) - b)) #  0.03420076
We can also see what the feasible set of unconstrained variables is for this solution:
which(x_fnnls > 0) #  4 5 7
Now let's consider setting index 2 (and only index 2) to a positive value. No, I didn't pull this out of my hat. I calculated the loss for every possible active set:
new_x <- rep(0, 10) new_x <- b/a[2, 2] mean(abs(as.vector(a %*% new_x) - b)) #  0.02242538
Note that a loss of 0.022 (the solution I pulled out of my hat) is less than a loss of 0.034 (returned by NNLS). Multiway fnnls was not able to find this solution. I have tested NNLS algorithms I listed in the Q and they all give the same solution.
This is not an isolated example. I have seen similar situations in ill- and well-conditioned systems.