Interior_Point.m solves a linear program with a prototype interior point algorithm.

,where f is a 2×1 vector,while a1,a2 and b are each 16×1 vectors.

This can be rewritten as:

The Cost is:

The Gradient is:

The Hessian is:

Vectors f, a1, a2 and b are loaded from lin_prog149.mat via load_data_lin_prog.m. Given these values, the figure of the constraint region overlaid with the location of the solutions to (*µ) is below:

Travel.m solves a travelling salesman problem using simulated annealing: i.e. it finds a near-optimal shortest route between 40 coordinates (p(i), q(i)) with i=1,...,40. Vectors p and q are loaded from travel_sale149.mat via load_data_travel_sale.m. Given these values, the plot of the 40 coordinates together with the near-optimal route can be seen below:

When implementing simulated annealing it is common to perform more than one search. This program uses a randomized method because the global search for a “spatially” big function is computationally prohibitive. Therefore a different plot will be generated every time - rather than having one optimal route distance, this program provides a range of near-optimal short routes.