15.2.1 Global optimization
minimize
attempts to find, using analytical methods,
the exact smallest value of a differentiable
expression on a compact domain specified by (in)equality
constraints.
-
minimize takes two mandatory arguments and two
optional arguments:
-
obj, a univariate or multivariate expression
- Optionally, constr, list of constraints given by
equalities, inequalities, and/or expressions assumed to be equal to 0.
If there is only one constraint, it does not have to be a list.
- vars, list of variables. If there is only one
variable, it does not have to be a list. A variable can also include
bounds, as in x=a..b.
Variables can also be given as x=x0, y=y0 and so on,
in which case the optimum is computed numerically by performing a local search
from the specified point (x0,y0,…).
- Optionally, location, a keyword which may be
coordinates, locus or point.
- minimize(obj ⟨,constr ⟩,vars ⟨,location ⟩)
returns the minimum value of obj on the domain
specified by constraints and/or bounding variables, or (if
location is specified) a list consisting of the minimum value
and the list of points where the minimum is achieved.
If the domain is not compact, the final result may be incorrect or
meaningless. If the minimal value could not be found, then
undef is returned. In some cases, unboundeness of the
objective function can be detected.
Note that minimize respects the bound constraints set to variables
by the assume command.
The maximize
command takes the same parameters as minimize,
but returns the global maximum of obj on the specified domain.
Examples
Univariate minimization:
minimize(sin(x),[x=0..4]) |
minimize(x^4-x^2,x=-3..3,locus) |
|
| ⎡
⎢
⎢
⎣ | − | | , | ⎡
⎢
⎢
⎣ | | ,− | | ⎤
⎥
⎥
⎦ | ⎤
⎥
⎥
⎦ |
| | | | | | | | | | |
|
minimize and maximize can handle absolute values and piecewise
expressions in one or more variables.
For example, we find global minimum and global maximum of the function
f(x,y)= | |2+xy−y2|+|2x−x2+xy+y2| |
|
1+x2+y2 |
| |
on the square [−1,1]×[−1,1].
f(x,y):=(abs(2+x*y-y^2)+abs(2x-x^2+x*y+y^2))/(1+x^2+y^2):;
minimize(f(x,y),[x=-1..1,y=-1..1]);
maximize(f(x,y),[x=-1..1,y=-1..1]); |
As another example, input:
obj:=piecewise(x<=-2,x+6,x<=1,x^2,3/2-x/2):;
maximize(obj,x=-3..2) |
Each constraint can be either an equality or a non-strict inequality.
obj:=sqrt(x^2+y^2)-z:;
constr:=[x^2+y^2<=16,x+y+z=10]:;
minimize(obj,constr,[x,y,z]) |
minimize(x^2*(y+1)-2y,[y<=2,sqrt(1+x^2)<=y],[x,y]) |
minimize and maximize are aware of implied constraints that
restrict the natural domain of the objective function.
In the following example, the constraint x2+y2≤ 1 is implied, and the
minimum corresponds to any point on the unit circle.
minimize(sqrt(1-x^2-y^2),[x,y],point) |
|
| ⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣ | 0, | ⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣ | | ⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦ |
| ⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦ |
| | | | | | | | | | |
|
As another example, it is known that the natural domain of arc sine is
the segment [−1,1].
Constraints can be built from simpler ones by using
logical conjunction and disjunction.
The latter is suitable for specifying disconnected domains,
as in the following example.
minimize(x*y,[x^2+y^2<=1,x<=-3/4 or x>=5/6],[x,y],point) |
Symbolic constants are allowed in the objective and constraints.
Note that they have to be either implied or assumed real numbers.
assume(a>0):;
maximize(x^2*y^2*z^2,x^2+y^2+z^2=a^2,[x,y,z]) |
In the following example, we use minimize to obtain the formula for
computing the distance d between the point P=(a,b,c) and the plane
π given by the equation Ax+By+Cz+D=0. We accomplish this by finding
a point (x0,y0,z0)∈π which is closest to P.
Since we are going to minimize d2=(x−a)2+(y−b)2+(z−c)2,
the distance is equal to the square root of the minimum.
d:=minimize((x-a)^2+(y-b)^2+(z-c)^2,A*x+B*y+C*z+D=0,[x,y,z]):;
simplify(sqrt(d)) |
Note that the coordinates x0, y0 and z0 can be obtained by
passing point as the fourth argument in minimize.