how to interpret local minima of combinatorial optimization

Question

I am having a difficult time trying to interpret and visualize the local minima of a combinatorial optimization objective function.

Here's a rough sketch of my problem:

I have $m$ points $x_1,\dots,x_m$ in $\mathbb{R}^d$. My objective function is only a function of any $n$ of these points where $n < m$ and $n$ is fixed. The goal is to find the set of poins $x_{i_1},\dots,x_{i_n}$ which minimizes the objective function. We may denote the solution point to the optimization problem by $(x_{i_1},\dots,x_{i_n}).$ The order of these $n$ points is not important and so there are many local minima, assuming it exists.

Clearly, this is a combinatorial optimization problem with $m$ choose $n$ possible combinations for the solution. Thus the set of possible solution points is finite.

What I'm finding hard to grasp is the meaning of a local minima in this context. Suppose that $x^* =(x_{i_1},\dots,x_{i_n})$ is a "local minima". If we are to use the classical definition of local minima, how do we define the neighborhood of $x^*$? Can we ensure that such a neighborhood belongs to the $m$ points where we started with?

Assume that $n = 1$ and $d=2. $How do you plot the objective function if you have discrete inputs?

any insight appreciated!

Answer 1

The definition of "local minimum" you chose is dependent on your choice of optimization algorithm. Your algorithm will naturally group certain configurations together. For example, if your algorithm starts at one configuration, and explores the configurations which differ from that configuration on only one point, then these configurations are neighbors. A local minimum is then any point whose neighbors have a larger objective function.

This is a useful definition, since then local minima again correspond to configurations the algorithm could get "stuck" on.