Exact Global Optimization

Introduction	Univariate Optimization
Algorithms	Optimization by Finding Stationary and Singular Points
Optimization by Cylindrical Algebraic Decomposition	Optimization over the Integers
Linear Optimization	Optimization over Regions

Introduction

Global optimization problems can be solved exactly using Minimize, Maximize, MinValue, MaxValue, ArgMin and ArgMax.

This computes the global minimum of

and the value of

for which the minimum is attained:

This computes the radius of the circle, centered at the origin, circumscribed about the set

as a function of the parameters

and

Algorithms

Depending on the type of problem, several different algorithms can be used.

The most general method is based on the cylindrical algebraic decomposition (CAD) algorithm. It applies when the objective function and the constraints are real algebraic functions. The method can always compute global extrema (or extremal values, if the extrema are not attained). If parameters are present, the extrema can be computed as piecewise-algebraic functions of the parameters. A downside of the method is its high, doubly exponential complexity in the number of variables. In certain special cases not involving parameters, faster methods can be used.

When the objective function and all constraints are linear, global extrema can be computed exactly using the simplex algorithm. This approach can also be used for linear-fractional objective functions.

For univariate problems, equation and inequality solving methods are used to find the constraint solution set and discontinuity points and zeros of the derivative of the objective function within the set.

Another approach to finding global extrema is to find all the local extrema, using the Lagrange multipliers or the Karush–Kuhn–Tucker (KKT) conditions, and pick the smallest (or the greatest). However, for a fully automatic method, there are additional complications. In addition to solving the necessary conditions for local extrema, it needs to check smoothness of the objective function and smoothness and nondegeneracy of the constraints. It also needs to check for extrema at the boundary of the set defined by the constraints and at infinity, if the set is unbounded. This in general requires exact solving of systems of equations and inequalities over the reals, which may lead to CAD computations that are harder than in the optimization by CAD algorithm. Currently the Wolfram Language uses Lagrange multipliers only for equational constraints within a bounded box or for a single inequality constraint with a bounded solution set. The method also requires that the number of stationary points and the number of singular points of the constraints be finite. An advantage of this method over the CAD-based algorithm is that it can solve some transcendental problems, as long as they lead to systems of equations that the Wolfram Language can solve.

Optimization by Cylindrical Algebraic Decomposition

Examples

This finds the point on the cubic curve

which is closest to the origin:

This finds the point on the cubic curve

which is closest to the origin, as a function of the parameter

This visualization shows the point on the cubic curve

which is closest to the origin, and the distance

of the point from the origin. The value of parameter

can be modified using the slider. The visualization uses the minimum computed by Minimize:

Customized CAD Algorithm for Optimization

The cylindrical algebraic decomposition (CAD) algorithm is available in the Wolfram Language directly as CylindricalDecomposition. The algorithm is described in more detail in "Real Polynomial Systems". Setting the CAD algorithm options described in "Real Polynomial Systems", in particular the CADConstruction option, may affect the performance of optimization functions. The following describes how to customize the CAD algorithm to solve the global optimization problem.

Reduction to Minimizing a Coordinate Function

Suppose it is required to minimize an algebraic function over the solution sets of algebraic constraints , where is a vector of variables and is a vector of parameters. Let be a new variable. The minimization of over the constraints is equivalent to the minimization of the coordinate function over the semialgebraic set given by .

If happens to be a monotonic function of one variable , a new variable is not needed, as can be minimized instead.

The Projection Phase of CAD

The variables are projected, with first, then the new variable , and then the parameters .

If algebraic functions are present, they are replaced with new variables; equations and inequalities satisfied by the new variables are added. The variables replacing algebraic functions are projected first. They also require special handling in the lifting phase of the algorithm.

Projection operator improvements by Hong, McCallum, and Brown can be used here, including the use of equational constraints. Note that if a new variable needs to be introduced, there is at least one equational constraint, namely .

The Lifting Phase of CAD

The parameters are lifted first, constructing the algebraic function equation and inequality description of the cells. If there are constraints that depend only on parameters and you can determine that is identically false over a parameter cell, you do not need to lift this cell further.

When lifting the minimization variable , you start with the smallest values of , and proceed (lifting the remaining variables in the depth-first manner) until you find the first cell for which the constraints are satisfied. If this cell corresponds to a root of a projection polynomial in , the root is the minimum value of , and the coordinates corresponding to of any point in the cell give a point at which the minimum is attained. If parameters are present, you get a parametric description of a point in the cell in terms of roots of polynomials bounding the cell. If there are no parameters, you can simply give the sample point used by the CAD algorithm. If the first cell satisfying the constraints corresponds to an interval , where is a root of a projection polynomial in , then is the infimum of values of , and the infimum value is not attained. Finally, if the first cell satisfying the constraints corresponds to an interval , is unbounded from below.

Linear Optimization

When the objective function and all constraints are linear, global extrema can be computed exactly using the simplex algorithm.

This solves a random linear minimization problem with 10 variables:

Optimization problems where the objective is a fraction of linear functions and the constraints are linear (linear fractional programs) reduce to linear optimization problems. This solves a random linear fractional minimization problem with 10 variables:

Univariate Optimization

This solves a univariate optimization problem with a transcendental objective function:

Here is a visualization of the minimum found:

Here the Wolfram Language recognizes that the objective functions and the constraints are periodic:

The solution may be given in terms of Root of transcendental functions:

When the input involves special functions, numeric integration may be used to prove completeness of the solution:

Optimization by Finding Stationary and Singular Points

Lagrange multipliers are used when the constraints consist of equations and of inequalities explicitly specifying a bounded box. Here is an example where the minimum is attained at a singular point of the constraints:

The maximum of the same objective function is attained on the boundary of the set defined by the constraints:

There are no stationary points in this example:

Here is a set of 3-dimensional examples with the same constraints. Depending on the objective function, the maximum is attained at a stationary point of the objective function on the solution set of the constraints, at a stationary point of the restriction of the objective function to the boundary of the solution set of the constraints, and at the boundary of the boundary of the solution set of the constraints.

Here the maximum is attained at a stationary point of the objective function on the solution set of the constraints:

Here the maximum is attained at a stationary point of the restriction of the objective function to the boundary of the solution set of the constraints:

Here the maximum is attained at the boundary of the boundary of the solution set of the constraints:

The Lagrange multiplier method works for some optimization problems involving transcendental functions:

The Lagrange multiplier method is also used when the constraints consist of a single equation or inequality with a bounded solution set:

Optimization over the Integers

Integer Linear Optimization

An integer linear optimization problem is an optimization problem in which the objective function is linear, the constraints are linear and bounded, and the variables range over the integers.

To solve an integer linear optimization problem the Wolfram Language first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method.

This solves a randomly generated integer linear optimization problem with 7 variables:

Optimization over the Reals Combined with Integer Solution Finding

Suppose a function needs to be minimized over the integer solution set of constraints . Let be the minimum of over the real solution set of . If there exists an integer point satisfying , then is the minimum of over the integer solution set of . Otherwise you try to find an integer solution of , and so on. This heuristic works if you can solve the real optimization problem and all the integer solution finding problems, and you can find an integer solution within a predefined number of attempts. (By default, the Wolfram Language tries 10 candidate optimum values. This can be changed using the IntegerOptimumCandidates system option.)

This finds a point with integer coordinates maximizing

among the points lying below the cubic

Optimization over Regions

Regions can be used to specify constraints. The method used for solving an optimization problem over a region depends on what type of region description is easier to obtain.

This uses an implicit description of the region:

This substitutes the region parametrization into the objective function:

Top