Using CylindricalAlgebraicDecomposition for Optimization

Frank J. Kampas

fkampas@msn.com

The functions ConstrainedMin, ConstrainedMax, and LinearProgramming can find a minimum or maximum of a linear objective function subject to linear constraints. The function Experimental`Minimize can find a minimum of a rational polynomial function subject to rational polynomial constraints, and NumericalMath`NMinimize and NumericalMath`NMaximize can find a minimum or maximum of more general functions subject to more general constraints. None of these functions can find all the minima or maxima of an optimization problem. However, Experimental`CylindricalAlgebraicDecomposition can find all the minima and maxima of rational polynomial objective functions subject to rational polynomial constraints, although the time required may become prohibitively long for more than simple cases.

First, consider the trivial example of maximizing subject to , , and . ConstrainedMax gives one solution. (Note that the linear programming functions ConstrainedMin and ConstrainedMax assume that all variables are greater than or equal to 0. Although LinearProgramming assumes nonnegativity by default, it can work with negative variables in Version 4.2.)

Reformulating this problem as a set of equalities and inequalities and using CylindricalAlgebraicDecomposition gives all the maxima as the line for when the objective function has its maximum value of 1.

Note that putting the objective function first in the list of variables causes the results to be displayed in order of increasing values of the objective function.

Next consider the nonlinear problem of minimizing subject to . Minimize gives one minimum whereas it is clear from symmetry () that there should be two.

CylindricalAlgebraicDecomposition provides the two minima and the two maxima as well as a lot of information (here suppressed) about the function between the minima and the maxima, at the price of taking considerably longer than Minimize.

This problem can be overcome by first using Minimize to find the minimum value of the objective function and then using CylindricalAlgebraicDecompostion to find all the solutions for that value of the objective function. The function multipleMinimize implements this approach.

Note that Experimental`Infimum is likely to be a little faster than Experimental`Minimize when all constraints are strict inequalities.

multipleMinimize also works for linear programming problems.

Finally, here is an example of finding a parametrized minimizing set.