0
$\begingroup$

Let's say I define the following function in SAGE

$$ f(x,y,z,w)=|x+y-\lfloor x+y\rceil|+|y-z-\lfloor y-z \rceil|+|z+w-\lfloor z+w \rceil | + |w-x-\lfloor w-x \rceil | - |x|-|y|-|z|-|w|, $$ and want to find the maximum of $f$ for $x \in I_x, y \in I_y, z \in I_z, w \in I_w$, some predefined intervals. I am aware of the function

minimize_constrained,

which can be used to minimise multivariate differentiable functions, but since the rounding function is non-differentiable, SAGE returns an error. Is there any way to get SAGE to maximise such a function (or any linear function involving rounding) without having to consider each interval piecewise?

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't think you should be using optimizers that depend on gradients here. For example, in Python you could so something like that using a global optimizer like differential evolution:

import numpy as np
from scipy.optimize import rosen, differential_evolution
def f(theta):
    x = theta[0]
    y = theta[1]
    z = theta[2]
    w = theta[3]
    return abs(x+y - round(x+y)) + abs(y-z - round(y-z)) + abs(z+w - round(z+w)) + abs(w-x - round(w-x)) - abs(x) - abs(y) - abs(z)  -abs(w)

bounds = [(-100,100) for i in range(4)]



result = differential_evolution(f, bounds)
print(result)

Which gives the results:

     fun: -400.0
     jac: array([-2.99999858,  2.99999858,  2.99999858, -3.00000426])
 message: 'Optimization terminated successfully.'
    nfev: 3345
     nit: 54
 success: True
       x: array([ 100., -100., -100.,  100.])

So your problem comes probably from the solver you used. I don't know what types of solvers are available in sagemath, though.

$\endgroup$
2
  • $\begingroup$ I see - thank you! the package seems to be available for SAGE too, since copying your code also worked in my notebook. Quick question about "differential_evolution" - how do I retrieve the numbers from the array returned in "result"? $\endgroup$
    – Chris
    Jul 26, 2021 at 18:27
  • 1
    $\begingroup$ You can use result[x] to return the optimal solution. Other optional parameters are available in the link in my answer. I also suggests looking at the scipy.optimize page for the other solvers available, since maybe there are others more suitable to your problem. $\endgroup$ Jul 26, 2021 at 18:32

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.