Optimisation Geometry

In an invited book chapter (downloadable from arXiv), I made a first attempt at understanding how the geometry of a family of cost functions influences the computational complexity of the resulting optimisation problem.  Importantly, real-time optimisation problems were studied rather than classical “once-off” optimisation problems.

Real-time optimisation problems differ from classical optimisation problems in that the class of cost functions is known beforehand and (considerable) time can be expended beforehand studying this class prior to developing a tailor-made algorithm for solving the particular real-time optimisation problem at hand.  Real-time optimisation problems deserve closer attention because there is no reason for classical optimisation methods to perform particularly well for real-time problems.

In addition to demonstrating how an algorithm with guaranteed performance can, in principle, be constructed for any real-time optimisation problem, a geometric framework was given which is hoped will yield, in future work, insight into the computational complexity of real-time optimisation problems.

An embryonic concept is that overall complexity divides into intrinsic complexity and extrinsic complexity.  The intrinsic complexity is the unavoidable complexity of the real-time optimisation problem, the best that can be done with infinite resources allocated to simplifying the problem beforehand.  The extrinsic complexity is the additional complexity coming from how the optimisation problem is posed; for example, if a quadratic cost function is composed with a complicated diffeomorphism then the resulting optimisation problem is “difficult” whereas the underlying optimisation problem, that of minimising a quadratic function, is “easy”.  (This distinction makes less sense for “once-off” optimisation because there is no opportunity to determine beforehand, “free of charge”, whether or not the original problem can be simplified by a suitable change of coordinates.) The coordinate-independent nature of geometry suggests differential topology/geometry is an appropriate tool to be using in this investigation.