If you have just a single nonlinear function, you could measure its nonlinearity by taking its second derivative. For linear functions, it is zero, and any deviation from zero can be considered as a measure of its nonlinearity. For a function f:[a,b]->R, this suggests to define NONLINEARITY(f) := integral( (d^2f/dx^2 (x))^2, x=a..b) as a measure.
When it comes to more complex optimization problems, however, the story is not that easy. For example, consider a binary integer optimization problem, that is, all variables should be 0-1. This discontinuity can be expresses by the constraints x_i = x_i^2 for all variables x_i. If the optimization problem is an easy problem (shortest path, for instance), then despite this nonlinearity, there are still efficient algorithms around to solve it (Dijkstra, Moore-Bellman-Ford, for instance). Here a measure for the nonlinearity of the functions x_i = x_i^2 would be rather meaningless.