# Non-negative least squares with order constraint

I have a very familiar problem, non-negative least squares (NNLS), with the added constraint that the first element in the solution vector is larger than the second, which is larger than the third, and so on. That is, given $A$ and $d$,

$$\begin{array}{ll} \text{minimize} & \|Ax - d\|_2\\ \text{subject to} & x_1 \geq x_2 \geq \cdots \geq x_n\\ & x_i \geq 0\end{array}$$

Can you think of any way to tweak the active set method for normal NNLS such that the ordering constraint is also satisfied? Presumably a result $x'$ provided by the normal NNLS sits on a manifold of other NNLS solutions, which can be traversed until the order constraint is satisfied?

A simple transformation allows you to apply any standard method to this. Just consider nonnegative variables $y_i$, $i=1,2,\dots, n$, and define $$x_n = y_n, \quad x_{n-1} = x_n + y_{n-1}, \quad \dots \quad x_1 = x_2 + y_1$$ Or, equivalently, $$x_k = \sum_{i=k}^n y_k \quad \Longrightarrow \quad x = E y$$ where $E$ is the upper triangular matrix of all ones. Now we have $$\|Ax-d\|_2 = \|AEy-d\|_2$$ giving you a standard NNLS problem to work with.
I'm sure you can tweak an existing active-state method to consider the monotonicity constraint directly---instead of partitioning $y$ into zero and non-zero values, you partition $x$ in to elements that are equal to the next, and strictly greater than. But it might be better to just use existing machinery on the transformed problem.
One downside is that forming $AE$ would destroy sparsity. But $E$ does have a nice $O(n)$ structure, so algorithms that can exploit more general structure than sparsity will work well with $AE$.