Session 5: Optimization

Mathematica provides the functions Maximize and Minimize that can solve all kinds of optimization problems. Further, there are functions like LinearProgramming to use specified solution methods.

Optimization using Maximize/Minimize

Optimizing functions

The function Maximize (or Minimize) takes in general two arguments, an expression that should be optimized, and the optimization variable. It returns in general a list with two entries: the first one is the optimal value, the second one is a (list of) rule(s) specifying the optimal solution. 
Maximize/Minimize return in general some optimal solution, not all optimal solutions.

(* Maximize a parabola *)
Maximize[-x^2-2x+1,x]
(* Maximize a constant function -- Returns an arbitrary optimal solution *)
Maximize[1,x]
(* Maximize a parametrized function *)
Unset[a];Unset[b];Unset[c];Unset[d];
solution = Maximize[-c*(x-a)^2-d*(x-d)^2,x]
(* Simplify the solution *)
Simplify[solution]
(* Maximize a function depending on two varialbes *)
Maximize[Sin[x]*Cos[y],{x,y}]

Optimization with constraints

When the expression in Maximize[ expr, var ] is a list, then the first entry in the list is interpreted as the objective function, all further entries can be side-constraints (Equalitities, Inequalities)

(* Multivariate optimization with an equality constraint *)
Maximize[{x+y,x^2+y^2==1},{x,y}]
(* A quadratic program of the form x.Q.x + p.x with side constraints *)
Q = {{2,-1},{-1,2}};
p={2,3}
Maximize[{{x1,x2}.Q.{x1,x2}+p.{x1,x2},x1+x2≥2,x1-2x2≤42, x1≥0,x2≤0},{x1,x2}]

Integer Programs

The functions Maximize/Minimize take as third parameter a domain restriction, in particular this domain can be integers

Maximize[{2x+3y-z,1≤x+y+z≤2,1≤x-y+z≤2,x-y-z==3},{x,y,z}, Integers]

Linear Programming

Mathematica provides the function LinearProgramming[ c, A , b ] to solve linear programs of the form 
min (c^T)x
     s.t. A x ≥ b
                  x ≥ 0
LinearProgramming[ ] returns the optimal solution as a vector.

(* Solves minimize x + y s.t. x + 2y ≥ 3 *)
x=LinearProgramming[{1,1},{{1,2}},{3}]
(* Compute the optmal value *)
{1,1}.x
Unset[x]

Numerical Optimization

The functions NMaximize and NMinimize apply numerical optimization whenever analytical solutions is are not possible.

NMaximize[{E^(Sin[50 x])+Sin[60 E^y]+Sin[70 Sin[x]]+Sin[Sin[80 y]]-Sin[10 (x+y)]+1/4 (x^2+y^2),x^2+y^2≤1},{x,y}]