How do you measure, gauge, etc the general non-linearity of a/ your non convex non linear optimization problem?
(How) can one quantify (%, number, measurement, etc) or qualify (scale, category, etc) it?
Are you talking about continuous problems? Smooth problems? Or other kinds of problems?
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.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics