If we remain in R^n, we talk about a local minimum x^* as being a global optimum over a region defined by the original constraints of the problem (so that we remain feasible) and a small enough Euclidean ball with center at x^*, such that x^* is a global minimum in this ball. The crucial point here is that the ball is chosen to be small enough. So local means global over a tiny set with x^* at its center.

If the problem you deal with is a convex one, then this neighborhood can be enlarged by encircle the whole feasible set. If the problem is a rather complex one with many local optima, perhaps with quick oscillations, then the radii around the local minima need to be very small. But the principle definition is not that complicated actually.

In addition to the answers already given, this does then give perspective to the VNS or Variable Neighbourhood Search heuristic which seeks to escape local minima by expanding the neighbourhood, usually via some kind of variable step length.

The question also brings out the nature of the surface being searched, whether it be smooth, convex and well-behaved, or noisy, discontinuous and generally 'difficult'. No Free Lunch indicates that we do need some a-priori 'intuition' about the surface being searched in order to choose not only the MetaHeuristic, but also the algorithm's internal parameters, so consequently you question about the neighbourhood around local optima becomes very important.

.

an answer in the context of machine learning :

http://ronan.collobert.com/pub/matos/2006_tradingconvexity_icml.pdf

(caveat : rather technical paper ; just ignore this if machine learning is not your area of interest !)

.

From a practical application point of view a local optimum helps to choose a "fairly acceptable" candidate among many other candidate solutions with a quick turn-around time.   

From another practical point of view...if you just want a better solution than the current one ...

"In what situation does a local optimum make sense?"

In addition to the previous answers given in this thread, I would say that, sometimes in engineering applications, a local optimum may turn out to be even more interesting than a global one, due to practical implementation issues. The attached figure shows an example of a global maximum (in red) and a competitive local maximum (in green). Clearly, the practical implementation of the ideal "red" solution could require a prohibitively high precision because any small deviation will yield a very poor result. In contrast, the "green" solution is much more robust to implementation errors while remaining competitive.

very interesting answers are presented here and a further point is the local optimum is a point that can be a very efficient point such as what in "Lehtihet"'s answer or it can be a point that is worse than 90% of other regular point. In means regularly we cannot trust to the local optimum if we do not have any idea about global (as a comparison criteria). Roughly, the best way to use local optimum is in convex (pseudo and quasi convex) optimization problems where local optimum can be the global.

In most applications we can't even determine the number of local solutions of a  problem. Sometimes we have no choice other than accepting a local optimum - again from a practical application point of view.

“Why needn't people define the corresponding neighborhood? Without a clear radius of the neighborhood, the local optimum can be either very significant or insignificant.”

In my experience, when one talks about a “local optimum”, the implicit corresponding neighborhood would not be extreme (such as 2- or 3-opt neighborhoods for TSP) and also normally searchable in polynomial time.  

Practical problems usually involve finding optimum of a function of many variables.  Those variables, in turn, have different meaning/origin and are therefore expressed in different units, say meters, kilograms, lumens, and so on.  The idea of distance in this case is neither obvious nor unique.  That is why the radius of the neighborhood in question may be difficult (or tricky)  to determine.

Anyway, the distance to the nearest critical point (from your local optimum), usually the saddle point,  will give you an idea how big is the domain of stability of this local optimum.  For this, however, you need to know all the critical points of your function being optimized, what is usually not the case.

.

related to H.E. Lehtihet answer above is the notion of "informativeness of optimization solutions" ; see Simon Stelling's brilliant master thesis :

http://e-collection.library.ethz.ch/view/eth:6950?q=%28keywords:KNAPSACK%20PROBLEM%29

.

Dear All,

Thank you for your answers and comments!

Dear H.E. Lehtihet,

I agree with your answer. But you are talking about the robust optimization. In fact, the "red point" is the global optimum and "green point" is the robust optimum. In your scenario, you implicitly pose another objective, i.e., robustness, to trade-off the objective quality. Thus, you are not solving the original problem.

Let me put it this way. If the objective quality is the only thing that matters, one is definitely solving the "Global Optimization", i.e., only the global optimum is expected. In this case, the definition of local optima becomes useless. If only the robustness is considered, the objective function then becomes, for example, average analysis or worst analysis. Then the solution that is most robust in the search space is pursued. That is, it just becomes another "global optimization", and local "robust" optima are still not considered.

Then my question is: what additional conditions can be used to trade-off the original objective value, so that the local optima may be considered? Further, what kind of local optima should be pursued in such situations?

Best regards,

Peng

A local optimum can help you to find a good answer which is minimum in the shortest time. You can use a local optimum when you want to observe a Limited Neighborhood(Vicinity) or a Function that has a predictive Changes because if functional changes are high, the local optimum can’t find the minimum answer, so the local optimum find a minimum answer and does not check the rest of the function. so when you want to use a local optimum It's better to know the Functional behavior.

In the case of an analytic function f of one real variable on an open interval, determining the local optimum points and their kind (minimum or maximum) is simple, thanks to Taylor formula. Step 1) One determines all critical (stationary) points of f. Step 2) Let a be a critical point for f and n>=2 the smallest natural number for which (f^(n))(a) is not null. If n is even, then a is a strict local optimum point for f (namely it is a strict local minimum point if (f^(n))(a)>0 and a strict local maximum point if (f^(n))(a)