1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ On one hand I'm happy that the answer is so simple but on the other hand im mad that I didn't think of it. Much obliged. $\endgroup$ – Tim Sears Oct 11 '16 at 18:38
  • $\begingroup$ Very Nice! +1. Those tricks are so great. $\endgroup$ – Royi Aug 21 '17 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.