Numerical Optimization

Searching for local minima and maxima.

This finds the value of x which minimizes Γ(x), starting at x==2:

FindMinimum[Gamma[x],{x,2}]

The last element of the list gives the value at which the minimum is achieved:

Gamma[x]/.Last[%]

Like (RefLink[FindRoot, paclet:ref/FindRoot]), (RefLink[FindMinimum, paclet:ref/FindMinimum]) and (RefLink[FindMaximum, paclet:ref/FindMaximum]) work by starting from a point, then progressively searching for a minimum or maximum. But since they return a result as soon as they find anything, they may give only a local minimum or maximum of your function, not a global one.

This curve has two local minima:

Plot[x^4-3x^2+x,{x,-3,2}]

Starting at x==1, you get the local minimum on the right:

FindMinimum[x^4-3 x^2+x,{x,1}]

This gives the local minimum on the left, which in this case is also the global minimum:

FindMinimum[x^4-3 x^2+x,{x,-1}]

You can specify variables without initial values:

FindMinimum[x^4-3 x^2+x,x]

You can specify a constraint:

FindMinimum[{x^4-3 x^2+x,x<0},x]

Finding global minima and maxima.

This immediately finds the global minimum:

NMinimize[x^4-3x^2+x,x]

(RefLink[NMinimize, paclet:ref/NMinimize]) and (RefLink[NMaximize, paclet:ref/NMaximize]) are numerical analogs of (RefLink[Minimize, paclet:ref/Minimize]) and (RefLink[Maximize, paclet:ref/Maximize]). But unlike (RefLink[Minimize, paclet:ref/Minimize]) and (RefLink[Maximize, paclet:ref/Maximize]) they usually cannot guarantee to find absolute global minima and maxima. Nevertheless, they typically work well when the function f is fairly smooth, and has a limited number of local minima and maxima.

Finding global minima and maxima subject to constraints.

With the constraint x>0, (RefLink[NMinimize, paclet:ref/NMinimize]) will give the local minimum on the right:

NMinimize[{x^4-3x^2+x,x>0},x]

This finds the minimum of x+2 y within the unit circle:

NMinimize[{x+2y,x^2+y^2<=1},{x,y}]

In this case (RefLink[Minimize, paclet:ref/Minimize]) can give an exact result:

Minimize[{x+2y,x^2+y^2<=1},{x,y}]

But in this case it cannot:

Minimize[{Cos[x+2y],x^2+y^2<=1},{x,y}]

This gives a numerical approximation, effectively using (RefLink[NMinimize, paclet:ref/NMinimize]):

N[%]

If both the objective function f and the constraints cons are linear in all variables, then minimization and maximization correspond to a linear programming problem. Sometimes it is convenient to state such problems not in terms of explicit equations, but instead in terms of matrices and vectors.

Linear programming in matrix form.

Here is a linear programming problem in equation form:

Minimize[{2x+3y,x+5y>=10,x-y>=2,x>=1},{x,y}]

Here is the corresponding problem in matrix form:

LinearProgramming[{2,3},{{1,5},{1,-1},{1,0}},{10,2,1}]

You can specify a mixture of equality and inequality constraints by making the list b be a sequence of pairs {(Subscript[b, i]),(Subscript[s, i])}. If (Subscript[s, i]) is 1, then the i(^th) constraint is (Subscript[m, i]).x≥(Subscript[b, i]). If (Subscript[s, i]) is 0 then it is (Subscript[m, i]).x==(Subscript[b, i]), and if (Subscript[s, i]) is -1 then it is (Subscript[m, i]).x≤(Subscript[b, i]).

This makes the first inequality use ≤:

LinearProgramming[{2,3},{{1,5},{1,-1},{1,0}},{{10,-1},{2,1},{1,1}}]

In (RefLink[LinearProgramming, paclet:ref/LinearProgramming])[c,m,b,l], you can make l be a list of pairs {{(Subscript[l, 1]),(Subscript[u, 1])},{(Subscript[l, 2]),(Subscript[u, 2])},…} representing lower and upper bounds on the (Subscript[x, i]).

In doing large linear programming problems, it is often convenient to give the matrix m as a (RefLink[SparseArray, paclet:ref/SparseArray]) object.