Optimization

Mathematical optimization problems arise in the fields of linear programming, ML, resource allocation, production planning, and so on.

One well-known allocation problem is that of a traveling salesman who has to make a series of calls and wishes to compute the optimal route between calls. The problem is not tractable but clearly can be solved exhaustively; however, by clustering and tree pruning, the number of tests can be markedly reduced.

The generalized aim is to formulate the minimization of some f(x) function for all values of x over a certain interval, subject to a set of gi(x) restrictions.

The problems of local maxima are also included by redefining the domain of x. It is possible to identify three cases:

1. No solution exists.
2. Only a single minimum (or maximum) exists.

   In this case, the problem is said to be convex and is relatively insensitive to the choice of starting value for x.

3. The f(x) function has multiple extremals.

For this...