Can it be proven that non-negative least squares is a perfectly convex problem?

Question

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 a, b, and x minimizing 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 b:

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))
# [1] 0.03420076    

We can also see what the feasible set of unconstrained variables is for this solution:

which(x_fnnls > 0)
# [1] 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[2] <- b[2]/a[2, 2]
mean(abs(as.vector(a %*% new_x) - b))
# [1] 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.

Answer 1

In the scenario you're thinking of, non-negative least squares is still convex in $x$, though it may or may not be convex in something else.

Let's consider some possibilities.

• There are some supplied input variables, and some derived input variables that are (typically nonlinear) functions of the basic variables, including products $a_1a_2$ and other functions of more than one variable. The matrix $a$ includes both. In this case the optimisation problem may be non-convex in the supplied variables, but it is convex in $x$. There won't be local minima
• The true response as a function of $a$(eg, $E[b|a=a]$ if $b$ is stochastic or $b$ itself if deterministic) is a nonlinear function of $a$, but you still fit a linear model by non-negative least squares. The optimisation problem is still convex in $x$, and there won't be local minima, but (as a result) the optimum may not be a very good fit.

Finding $x$ to minimise $\|ax-b\|^2$ for given $a$ and $b$ is a convex problem for reasons that have little to do with the true relationship between $a$ and $b$. The convexity comes because the objective function is convex in $x$ and the feasible region from the non-negativity constraints is an intersection of half-spaces, and so a convex set, in the $x$ space.