Introduction to Constrained Optimization in Mathematica
Optimization Problems
Constrained optimization problems are problems for which a function
f (x) is to be minimized or maximized subject to constraints
(x). Here
f:^{n}→ is called the objective function and
(x) is a Booleanvalued formula. In
Mathematica the constraints
(x) can be an arbitrary Boolean combination of equations
g (x)0, weak inequalities
g (x)≥0, strict inequalities
g (x)>0, and
x statements. The following notation will be used.
stands for "minimize
f (x) subject to constraints
(x)", and
stands for "maximize
f (x) subject to constraints
(x)".
You say a point
u^{n} satisfies the constraints
if
(u) is true.
The following describes constrained optimization problems more precisely, restricting the discussion to minimization problems for brevity.
Global Optimization
A point
u^{n} is said to be a global minimum of
f subject to constraints
if
u satisfies the constraints and for any point
v that satisfies the constraints,
f (u)≤f (v).
A value
a{, } is said to be the global minimum value of
f subject to constraints
if for any point
v that satisfies the constraints,
a≤f (v).
The global minimum value
a exists for any
f and
. The global minimum value
a is attained if there exists a point
u such that
(u) is true and
f (u)=a. Such a point
u is necessarily a global minimum.
If
f is a continuous function and the set of points satisfying the constraints
is compact (closed and bounded) and nonempty, then a global minimum exists. Otherwise a global minimum may or may not exist.
Here the minimum value is not attained. The set of points satisfying the constraints is not closed.
Out[1]=  

Here the set of points satisfying the constraints is closed but unbounded. Again, the minimum value is not attained.
Out[3]=  

The minimum value may be attained even if the set of points satisfying the constraints is neither closed nor bounded.
Out[4]=  

Local Optimization
A point
u^{n} is said to be a local minimum of
f subject to constraints
if
u satisfies the constraints and, for some
r>0, if
v satisfies
vu<r (v), then
f (u)≤f (v).
A local minimum may not be a global minimum. A global minimum is always a local minimum.
Solving Optimization Problems
The methods used to solve local and global optimization problems depend on specific problem types. Optimization problems can be categorized according to several criteria. Depending on the type of functions involved there are linear and nonlinear (polynomial, algebraic, transcendental, ...) optimization problems. If the constraints involve
x, you have integer and mixed integerreal optimization problems. Additionally, optimization algorithms can be divided into numeric and symbolic (exact) algorithms.
Mathematica functions for constrained optimization include
Minimize,
Maximize,
NMinimize and
NMaximize for global constrained optimization,
FindMinimum for local constrained optimization, and
LinearProgramming for efficient and direct access to linear programming methods. The following table briefly summarizes each of the functions.
  
FindMinimum, FindMaximum  numeric local optimization  linear programming methods, nonlinear interior point algorithms, utilize second derivatives 
NMinimize, NMaximize  numeric global optimization  linear programming methods, NelderMead, differential evolution, simulated annealing, random search 
Minimize, Maximize  exact global optimization  linear programming methods, cylindrical algebraic decomposition, Lagrange multipliers and other analytic methods, integer linear programming 
LinearProgramming  linear optimization  linear programming methods (simplex, revised simplex, interior point) 
Summary of constrained optimization functions.
Here is a decision tree to help in deciding which optimization function to use.