# Linear Least Squares with Monotonicity Constraint

I'm interested in the multidimensional linear least squares problem: $$\min_{x}||Ax-b||^2$$ subject to a monotonicity constraint for $$x$$, meaning that the elements of $$x$$ are monotonically increasing: $$x_0 \leq x_1$$, $$x_1 \leq x_2$$, ... , $$x_{n-1} \leq x_n$$.

I basically have two questions regarding this problem:

1.) Is there maybe literature regarding this problem out there? I wasn't able to find anything online so far.

2.) If not, is it maybe possible to rewrite my problem in such a way that i could use already existing methods like Non Negative Least Squares (NNLS) or a Constrained Least Squares (CLS) method?

Regarding the NNLS, I had the idea to formulate my problem in terms of an $$\tilde{x} := (x_0, x_1-x_0,\; ...\;,x_n - x_{n-1})$$ as this would also achieve monotonicity if every term in non negative, but I can't seem to do it, maybe I'm missing something here?

• Take a look at Isotonic regression, maybee it will help. Jun 25, 2020 at 5:46
• Unfortunately Isotonic regression tackles another kind of problem. I'm not trying to fit a monotonic line through data, but rather want my parameters which i solve for in the linear regression to be monotonic. Jun 25, 2020 at 6:01
• Do you want a theoretical-type answer or a practical way to try to compute a solution? I assume it's the second?
– user762914
Jun 25, 2020 at 6:04
• I would be happy with either actually. Jun 25, 2020 at 6:07

Let $$L$$ be an $$n\times n+1$$ matrix such that $$L = \begin{pmatrix} -1 & 1 & 0 & ... &0 \\ 0 & -1 & 1 & ... &0 \\ & & \\ 0 & 0 & ...& -1 &1 \\ \end{pmatrix}$$

Then you can formulate this as a constrained least squares problem$$\min_{x}||Ax-b||^2\ s.t. Lx \geq 0$$

• Thank you for your answer! That would certainly work. I was kinda hoping to avoid such a reformulation as an inequality CLS problem as it might be a little bit numerically unstable with high dimensionality, but I guess to easiest way to solve this kind of problem would be using CVX? Jun 25, 2020 at 7:19
• I am not an expert on numerical optimization but this should be a pretty standard problem. E.g. Matlab has a command lsqlin for CLS.
– fes
Jun 25, 2020 at 8:14

Your idea to reformulate the problem so that the variables are $$x_0$$ and $$y_i = x_i - x_{i-1}$$ for $$i =1, \ldots, n$$ will work. Let $$y$$ be the vector whose components are $$x_0, y_1, \ldots, y_n$$ and define $$M = \underbrace{\begin{bmatrix} 1 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 0 \\ \vdots & & & \vdots \\ 1 & 1 & \cdots & 1 \end{bmatrix}}_{(n+1)\times(n+1)}.$$

Notice that $$M y = x$$. Expressed in terms of $$y$$, your optimization problem is to minimize $$\| AM y - b \|^2$$ subject to the constraint that $$y_i \geq 0$$ for $$i = 1, \ldots, n$$. In this reformulated problem, the optimization variable is the vector $$y$$.

• Thank you for your answer! Maybe you misunderstood my problem a little bit, though your suggestion will still work if i define $y_i=x_i - x_{i-1}$ and then fill the Matrix M with 1s for every element left of the diagonal. Jun 25, 2020 at 7:22
• @Anton Thanks, I think I fixed my answer now. Jun 25, 2020 at 7:30
• Yes you did, that definitely works. Thanks! Jun 25, 2020 at 7:32