Maximising a multivariate linear function that includes the rounding in SAGE

Question

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?

Answer 1

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.