Linear Least Squares with Monotonicity Constraint

least squareslinear regression

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?

Many thanks in advance!

Best Answer

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

Related Solutions

Solve Linear Least Squares with Matrix Inequality Constraint

Use a linearly constrained linear least squares solver.

For example: lsqlin in MATLAB https://www.mathworks.com/help/optim/ug/lsqlin.html

lsei in R https://rdrr.io/rforge/limSolve/man/lsei.html

The easiest way might be using CVX https://cvxr.com/cvx under MATLAB. CVXR https://cvxr.rbind.io/ under R, or CVXPY https://www.cvxpy.org/ under Python.

Here is the code for CVX:

cvx_begin
variable x(n)
minimize(norm(A*x-b))
A*x >= 0
cvx_end

which will transform the problem into a Second Order Cone Problem, send it to a solver, and transform the solver results back to the original problem as entered. You can include the factor of 1/2 (harmless) and square the norm, which doesn't affect the solution but needlessly makes the problem solution less numerically robust.

Edit: Extra details as requested in chat:

CVX calls a numerical optimization solver to solve the optimization problem. The solver enforces the specified constraints (within solver tolerance).

As mentioned above, CVX actually transforms this into an SOCP (Second Order Cone Problem) by converting the problem into epigraph formulation. It does this by introducing a new variable, t, and in effect moving the original objective to the constraints. Thus produce the problem.

minimize(t)
subject to
  norm((A*x-b) <= t
  A*x >= 0

There might also be a slight rearrangement of the constraint A*x >= 0. CVX calls a Second Order Cone solver optimization solver such as SeDuMi, SDPT3, Gurobi, or Mosek to solve this problem. It then transforms the results back to the original problem formulation as entered by the user.

Equality Constrained Non Negative Linear Least Squares (Unit Simplex Constraint)

Your problem can be formulated as convex quadratic programming problem with a linear equality constraint and nonnegativity constraints on $x$.

$\min \frac{1}{2}\left( x^{T}(A^{T}A)x - 2(b^{T}A)x + b^{T}b \right)$

subject to

$\sum_{i=1}^{n} x_{i}=1$

$x \geq 0$.

As a practical matter, you're probably best off using a well-written library routine for linearly constrained quadratic programming. There are many of them available in a variety of programming languages. If you need to implement this yourself, then implementing an active set QP solver is relatively straight forward.

Best Answer

Related Solutions

Solve Linear Least Squares with Matrix Inequality Constraint

Equality Constrained Non Negative Linear Least Squares (Unit Simplex Constraint)

Related Question