# Linear constraints for L-BFGS-B

I know L-BFGS-B only supports simple box constrains of the form: $l_i \leq x_i \leq u_i$, where $l_i$ and $u_i$ are constants. For my specific optimization problem, I need to specify some simple linear constraints of the form:

$x_{i-1} + k \leq x_i \leq x_{i+1}-k$ where $k>0$ is a fixed constant. Essentially, I need each variable $x_i$ to stay in-between (and within a certain distance away from) the two variables at index $i-1$ and $i+1$. Is it possible to achieve this with L-BFGS-B?

Can the $l$ and $u$ constraint vectors be modified after each iteration? One silly idea I have tried (and seems to work, although I have not extensively tested it) is to modify $l$ and $u$ after each iteration with this rule:

$$l_i = x_{i-1} + k$$ $$u_i = x_{i+1} - k$$

EDIT: I forgot to mention that the first variable ($x_0$) is also subject to a constant lower bound and the last variable ($x_{N-1}$) is subject to an constant upper bound:

$$x_0 \geq k$$

$$x_{N-1} \leq k_{max}$$

This makes recasting the problem into a basis where the unknowns are the differences of two $x$ variables not feasible since these two extra bounds (which in the current system are actual box constraints) would then become linear constraints.

One approach to this problem is to reparameterize your problem in terms of

$x_{1}$

and

$z_{i}=x_{i}-x_{i-1}$, $i=2, \ldots, n-1$.

You can then rewrite your objective function in terms of the the $z_{i}$ variables by substituting

$x_{i}=x_{1}+z_{1}+\ldots + z_{i}$, $i=2, 3, \ldots, n$.

$k \leq z_{i}$
• ... and in case your gradient routine is something you'd rather not touch, you can use the chain rule to get the gradient in the new coordinates $\partial f / \partial z = (\partial f / \partial x) (\partial z / \partial x)^{-1}$ then feed that into your LBFGS-B routine. – GoHokies Mar 20 '18 at 18:29
• I actually had this idea originally, except it will not work because I have actual lower and upper bound constraints for the first and last $x$ variables respectively: $k \leq x_0$ and $x_{N-1} \leq k_{max}$. I will update my question to reflect this. – Costis Mar 21 '18 at 3:44