3
$\begingroup$

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

Thanks in advance!

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.

$\endgroup$
2
$\begingroup$

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

Your separation constraints become

$k \leq z_{i}$

$\endgroup$
  • 1
    $\begingroup$ ... 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. $\endgroup$ – GoHokies Mar 20 '18 at 18:29
  • $\begingroup$ 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. $\endgroup$ – Costis Mar 21 '18 at 3:44
  • $\begingroup$ The lower bound on the first variable isn't a problem. The constraint that the last variable is less than or equal to an upper bound isn't something you can address with this approach. $\endgroup$ – Brian Borchers Mar 21 '18 at 4:21

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.