solving an iterated optimization problem

asked 2018-09-27 16:20:24 +0100

CEL gravatar image

I have the following problem, which I intend to solve using SAGE.

Given $m^2$ non-linear (smooth) functions $f_{ij}(x,y):[0,1]^2\rightarrow \mathbb{R}$, for $1\leq i,j \leq m$ I want to solve

$$ \min_{x\in[0,1]} \max ( F_1(x), \ldots, F_m(x) )$$ where for any $1\leq i \leq m$: $$ F_i(x) = \min_{y\in [0,1]} \max ( f_{i1}(x,y), \ldots, f_{im}(x,y) )$$

I had thought of solving the inner Minimax problem $F_i(x)$ as a non-linear optimization problem with inequality constraints as

$$\min z$$ $$ f_{ij}(x,y)-z \leq 0, \qquad 1\leq j \leq m$$ $$ y-1\leq 0 \qquad \mathrm{and} \qquad -y\leq 0$$ using the SAGE function sage.numerical.optimize.minimize_constrained. This works fine for a fixed value of $x$, but not in case $x$ is a free parameter. What I get is a TypeError: unable to simplify to float approximation

For instance the following code

x,y,z =var('x,y,z')

f = lambda (x,y,z): z

c_1 = lambda (x,y,z): z-0.25*(x+y+sqrt(x^2+1)+sqrt(y^2+4)+1)

c_2 = lambda (x,y,z): z-0.2150407*(x+sqrt((y-1)^2)+sqrt(2)+sqrt(x^2+1)+sqrt(y^2+4))

c_3 = lambda (x,y,z): 1-y

c_4 = lambda (x,y,z): y

minimize_constrained(f,[c_1,c_2,c_3,c_4],[x,0.5,0], algorithm='l-bfgs-b');

produces the error:

File "sage/symbolic/expression.pyx", line 1410, in sage.symbolic.expression.Expression.__float__ (/build/sagemath-zWcbUi/sagemath-7.4/sage/src/build/cythonized/sage/symbolic/expression.cpp:11031) TypeError: unable to simplify to float approximation

Does someone have an idea how to use minimize_constrained for functions with a free parameter? Are there other alternatives (except doing everything from scratch)?

edit retag flag offensive close merge delete


minimize_constrained expects [x,0.5,0] to be the initial point for finding the minimum, but the 1st entry, x, is a symbolic expression. Perhaps you can let min_fx = lambda x: minimize_constrained(f, [c_1,c_2,c_3,c_4], [x, 0.5, 0], algorithm='l-bfgs-b') and then operate on min_fx?

mforets gravatar imagemforets ( 2018-09-30 00:49:46 +0100 )edit