Appendix B - Optimization

Summary

Optimization problems arise in many different applications. They include the following elements:

• a mathematical model that describes the problem of interest over some set of variables. This may be discrete or continuous;

• a cost or revenue function of these variables that must be optimized according to some measure or norm;

• a set of constraints on the variables that defines their allowed range.

For example, the problem might be to determine the position of a source observed by several sensors. The model may include a stochastic description of the sources, noise, and propagation conditions. The optimization may be cast as a least squares problem, in which the expected variance of the position estimate is minimized. The constraints may include involvement of some maximum number of sensors or some maximum number of bits exchanged among the sensor nodes to conserve energy.

Optimization is a very broad and deep subject. In this appendix, a brief exposition of the basic tools of numerical analysis is presented, followed by a characterization of some classes of optimization problems and an outline of some classic approaches.

Basic tools of numerical analysis

A basic fact of numerical methods is that linear problems are much easier to solve than non-linear ones. Consider, e.g., the problem of finding the roots (zeros) of the equation f(x) = 0. Now if the function were a line one could readily compute the point of intersection with the x-axis. Otherwise, the problem is typically approached by linearizing it and proceeding in a sequence of iterations.