<p><strong>Correlated Minima in Non-Convex Optimization Problems</strong></p>
<p>Yes, there are several families of non-convex optimization problems that exhibit correlated minima. Here are a few examples:</p>
<ol>
<li><p><strong>Symmetric Functions</strong>
Symmetric functions are a class of functions that remain unchanged under certain symmetry transformations. For example, consider the function:</p>
<p>f(x) = ∑[i=1 to n] (x_i - x_j)^2</p>
</li>
</ol>
<p>This function is symmetric under permutation of the variables <code>x_i</code>. If a local minimum is found at <code>x = x*</code>, then any permutation of <code>x*</code> is also a local minimum.</p>
<ol start="2">
<li><p><strong>Periodic Functions</strong>
Periodic functions are functions that repeat themselves at regular intervals. For example, consider the function:</p>
<p>f(x) = sin(x)</p>
</li>
</ol>
<p>This function has local minima at <code>x = -π/2 + 2πk</code>, where k is an integer. If a local minimum is found at <code>x = x*</code>, then other local minima can be found at <code>x = x* + 2πk</code>.</p>
<ol start="3">
<li><p><strong>Gaussian Mixtures</strong>
Gaussian mixtures are a class of functions that are composed of multiple Gaussian distributions. For example, consider the function:</p>
<p>f(x) = ∑[i=1 to n] (1/σ_i) * exp(-((x - μ_i)^2) / (2σ_i^2))</p>
</li>
</ol>
<p>This function has local minima at <code>x = μ_i</code>, where <code>μ_i</code> are the means of the Gaussian distributions. If a local minimum is found at <code>x = x*</code>, then other local minima can be found at <code>x = μ_i</code> for i ≠ j.</p>
<ol start="4">
<li><strong>Discrete Optimization Problems</strong>
The Traveling Salesman Problem (TSP) is a classic discrete optimization problem that involves finding the shortest possible tour that visits a set of cities and returns to the starting city. The problem is defined as follows:</li>
</ol>
<ul>
<li>Given a set of <code>n</code> cities, each with a location <code>(x_i, y_i)</code></li>
<li>Each city has a distance <code>d_ij</code> to every other city <code>j</code></li>
<li>Find the shortest possible tour that visits each city exactly once and returns to the starting city.</li>
</ul>
<p>In the TSP, local minima are correlated due to the following reasons:</p>
<p><strong>Symmetry</strong>: The TSP is symmetric under cyclic tour of the cities. This means that if a local minimum is found for a particular tour, then any cyclic path of that tour is also a local minimum.</p>
<p><strong>Reversibility</strong>: The TSP is reversible, meaning that if a local minimum is found for a particular tour, then the reverse tour is also a local minimum.</p>
<p>Consider a TSP instance with 5 cities:</p>
<pre><code>  City 1: (0, 0)
  City 2: (1, 0)
  City 3: (1, 1)
  City 4: (0, 1)
  City 5: (0.5, 0.5)
</code></pre>
<p>Suppose a local minimum is found for the tour: <code>1 -&gt; 2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 1.</code> Then, the following tours are also local minima:</p>
<ul>
<li><code>2 -&gt; 3 -&gt; 4 -&gt; 5 -&gt; 1 -&gt; 2</code> (cyclic tour of the original tour)</li>
<li><code>1 -&gt; 5 -&gt; 4 -&gt; 3 -&gt; 2 -&gt; 1</code> (reverse tour)</li>
<li><code>2 -&gt; 1 -&gt; 5 -&gt; 4 -&gt; 3 -&gt; 2</code> (cyclic tour of the reverse tour)</li>
</ul>
<ol start="5">
<li><strong>Manifold Optimization</strong>
The Synchronization Problem is a classic manifold optimization problem that involves synchronizing a set of oscillators on a graph. The problem is defined as follows:</li>
</ol>
<ul>
<li><p>Given a graph <code>G = (V, E)</code> with <code>n</code> nodes and <code>m</code> edges</p>
</li>
<li><p>Each node <code>i</code> has a phase <code>θ_i</code></p>
</li>
<li><p>Each edge <code>(i, j)</code> has a coupling strength <code>K_ij</code></p>
</li>
<li><p>Find the phases <code>θ_i</code> that minimize the following energy function:</p>
<p>E(θ) = ∑[i=1 to n] (θ_i - θ_j)^2 * K_ij</p>
</li>
</ul>
<p>In the Synchronization Problem, local minima are correlated due to the following reasons:</p>
<p><strong>Symmetry</strong>: The Synchronization Problem is symmetric under rotation of the phases. This means that if a local minimum is found for a particular set of phases, then a rotation of those phases is also a local minimum.</p>
<p><strong>Periodicity</strong>: The Synchronization Problem is periodic, meaning that if a local minimum is found for a particular set of phases, then a periodic shift of those phases is also a local minimum.</p>
<p>Consider a Synchronization Problem instance with 3 nodes:</p>
<pre><code>  Node 1: K_12 = 1, K_13 = 0.5
  Node 2: K_21 = 1, K_23 = 0.5
  Node 3: K_31 = 0.5, K_32 = 0.5
</code></pre>
<p>Suppose a local minimum is found for the phases: <code>θ_1 = 0, θ_2 = π/2, θ_3 = π</code>. Then, the following phases are also local minima:</p>
<ul>
<li><code>θ_1 = π, θ_2 = 3π/2, θ_3 = 2π</code> (rotation of the original phases)</li>
<li><code>θ_1 = 2π, θ_2 = 5π/2, θ_3 = 3π</code> (periodic shift of the original phases)</li>
<li><code>θ_1 = 3π, θ_2 = 7π/2, θ_3 = 4π</code> (rotation and periodic shift of the original phases)</li>
</ul>

CC BY-SA 4.0
2024-12-03T16:54:30.497Z
I don't see that TSP is "symmetric under permutation of the cities". That argument would imply that every possible tour is locally minimal. From the example, I presume that you mean some cyclic shift instead of a permutation.
Christian Komusiewicz
CC BY-SA 4.0
2024-12-04T10:34:52.350Z
@ChristianKomusiewicz yes, it is a cyclic tour and will have same local minima. Edited the answer accordingly.  thx.
Vidyadhar Rao
CC BY-SA 4.0
2024-12-02T17:56:24.890Z
2024-12-05T02:46:46.010Z
2024-12-05T02:46:46.010Z
Vidyadhar Rao
<p>Other examples for the class of problems that exhibit correlated minima are:</p>
<ol>
<li><strong>Graph Partitioning Problems</strong>
Graph partitioning problems involve dividing a graph into smaller subgraphs, often with certain constraints. Correlated minima arise due to the symmetry of the graph and the fact that many different partitions can have similar costs.</li>
</ol>
<p><strong>Example</strong>: The Graph Bisection Problem, where the goal is to divide a graph into two equal-sized subgraphs with a minimum number of edges between them.
<strong>Correlated Minima</strong>: Different partitions can be obtained by swapping nodes between the two subgraphs or by rotating the subgraphs.</p>
<ol start="2">
<li><strong>Scheduling Problems</strong>
Scheduling problems involve assigning tasks to resources, such as machines or vehicles, subject to certain constraints.</li>
</ol>
<p><strong>Example</strong>: The Job Shop Scheduling Problem, where the goal is to schedule a set of jobs on a set of machines to minimize the makespan. <strong>Correlated Minima</strong>: Different schedules can be obtained by swapping jobs between machines or by shifting the start times of the jobs.</p>
<ol start="3">
<li><strong>Clustering Problems</strong>
Clustering problems involve grouping similar objects into clusters, often subject to certain constraints. Correlated minima arise due to the fact that many different clusterings can have similar costs.</li>
</ol>
<p><strong>Example</strong>: The K-Means Clustering Problem, where the goal is to partition a set of points into K clusters to minimize the sum of squared distances to the cluster centers. <strong>Correlated Minima</strong>: Different clusterings can be obtained by swapping points between clusters or by rotating the cluster centers.</p>
<ol start="4">
<li><strong>Feature Selection Problems</strong>
Feature selection problems involve selecting a subset of features from a larger set to optimize a certain objective function. Correlated minima arise due to the fact that many different subsets of features can have similar costs.</li>
</ol>
<p><strong>Example</strong>: The LASSO Problem, where the goal is to select a subset of features to minimize the sum of squared errors subject to a regularization term. <strong>Correlated Minima</strong>: Different subsets of features can be obtained by adding or removing features or by rotating the feature space.</p>
<ol start="5">
<li><strong>Optimization Problems on Manifolds with Symmetry</strong>
Optimization problems on manifolds with symmetry, such as the sphere or the torus, often exhibit correlated minima due to the symmetry of the manifold.</li>
</ol>
<p><strong>Example</strong>: The Spherical Optimization Problem, where the goal is to minimize a function on the surface of a sphere. <strong>Correlated Minima</strong>: Different minima can be obtained by rotating the sphere or by reflecting the solution across the equator.</p>
<ol start="6">
<li><strong>Discrete-Continuous Optimization Problems</strong>
Discrete-continuous optimization problems involve optimizing both discrete and continuous variables simultaneously. Correlated minima arise due to the interaction between the discrete and continuous variables.</li>
</ol>
<p><strong>Example</strong>: The Mixed-Integer Nonlinear Programming (MINLP) Problem, where the goal is to optimize a nonlinear objective function subject to both integer and continuous constraints. <strong>Correlated Minima</strong>: Different minima can be obtained by changing the integer variables or by rotating the continuous variables.</p>

CC BY-SA 4.0
2024-12-02T18:01:14.077Z
2024-12-02T19:12:15.557Z
2024-12-02T19:12:15.557Z
Vidyadhar Rao
<p>I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in the solution landscape. Basically, finding one local minimum should drastically increase the probability of finding another minimum.</p>
<p>Is there a known family of problems with such properties?</p>

<optimization><linear-programming><convex-optimization><convex-hull>
Non-convex optimization with correlated minima
Omar Shehab
# Non-convex optimization with correlated minima

(Asked by: username_0 on 2024-05-01)

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in the solution landscape. Basically, finding one local minimum should drastically increase the probability of finding another minimum.

Is there a known family of problems with such properties?

**Tags:** optimization, linear-programming, convex-optimization, convex-hull

---

## 2 answers

### Answer by username_1 on 2024-12-02. Score: 1

Correlated Minima in Non-Convex Optimization Problems
Yes, there are several families of non-convex optimization problems that exhibit correlated minima. Here are a few examples:

Symmetric Functions
Symmetric functions are a class of functions that remain unchanged under certain symmetry transformations. For example, consider the function:
f(x) = ∑[i=1 to n] (x_i - x_j)^2


This function is symmetric under permutation of the variables x_i. If a local minimum is found at x = x*, then any permutation of x* is also a local minimum.

Periodic Functions
Periodic functions are functions that repeat themselves at regular intervals. For example, consider the function:
f(x) = sin(x)


This function has local minima at x = -π/2 + 2πk, where k is an integer. If a local minimum is found at x = x*, then other local minima can be found at x = x* + 2πk.

Gaussian Mixtures
Gaussian mixtures are a class of functions that are composed of multiple Gaussian distributions. For example, consider the function:
f(x) = ∑[i=1 to n] (1/σ_i) * exp(-((x - μ_i)^2) / (2σ_i^2))


This function has local minima at x = μ_i, where μ_i are the means of the Gaussian distributions. If a local minimum is found at x = x*, then other local minima can be found at x = μ_i for i ≠ j.

Discrete Optimization Problems
The Traveling Salesman Problem (TSP) is a classic discrete optimization problem that involves finding the shortest possible tour that visits a set of cities and returns to the starting city. The problem is defined as follows:


Given a set of n cities, each with a location (x_i, y_i)
Each city has a distance d_ij to every other city j
Find the shortest possible tour that visits each city exactly once and returns to the starting city.

In the TSP, local minima are correlated due to the following reasons:
Symmetry: The TSP is symmetric under cyclic tour of the cities. This means that if a local minimum is found for a particular tour, then any cyclic path of that tour is also a local minimum.
Reversibility: The TSP is reversible, meaning that if a local minimum is found for a particular tour, then the reverse tour is also a local minimum.
Consider a TSP instance with 5 cities:
  City 1: (0, 0)
  City 2: (1, 0)
  City 3: (1, 1)
  City 4: (0, 1)
  City 5: (0.5, 0.5)

Suppose a local minimum is found for the tour: 1 -> 2 -> 3 -> 4 -> 5 -> 1. Then, the following tours are also local minima:

2 -> 3 -> 4 -> 5 -> 1 -> 2 (cyclic tour of the original tour)
1 -> 5 -> 4 -> 3 -> 2 -> 1 (reverse tour)
2 -> 1 -> 5 -> 4 -> 3 -> 2 (cyclic tour of the reverse tour)


Manifold Optimization
The Synchronization Problem is a classic manifold optimization problem that involves synchronizing a set of oscillators on a graph. The problem is defined as follows:


Given a graph G = (V, E) with n nodes and m edges

Each node i has a phase θ_i

Each edge (i, j) has a coupling strength K_ij

Find the phases θ_i that minimize the following energy function:
E(θ) = ∑[i=1 to n] (θ_i - θ_j)^2 * K_ij


In the Synchronization Problem, local minima are correlated due to the following reasons:
Symmetry: The Synchronization Problem is symmetric under rotation of the phases. This means that if a local minimum is found for a particular set of phases, then a rotation of those phases is also a local minimum.
Periodicity: The Synchronization Problem is periodic, meaning that if a local minimum is found for a particular set of phases, then a periodic shift of those phases is also a local minimum.
Consider a Synchronization Problem instance with 3 nodes:
  Node 1: K_12 = 1, K_13 = 0.5
  Node 2: K_21 = 1, K_23 = 0.5
  Node 3: K_31 = 0.5, K_32 = 0.5

Suppose a local minimum is found for the phases: θ_1 = 0, θ_2 = π/2, θ_3 = π. Then, the following phases are also local minima:

θ_1 = π, θ_2 = 3π/2, θ_3 = 2π (rotation of the original phases)
θ_1 = 2π, θ_2 = 5π/2, θ_3 = 3π (periodic shift of the original phases)
θ_1 = 3π, θ_2 = 7π/2, θ_3 = 4π (rotation and periodic shift of the original phases)

> **Comments:**
> **username_2**: I don't see that TSP is "symmetric under permutation of the cities". That argument would imply that every possible tour is locally minimal. From the example, I presume that you mean some cyclic shift instead of a permutation.  
> **username_1**: @ChristianKomusiewicz yes, it is a cyclic tour and will have same local minima. Edited the answer accordingly.  thx.  

---

### Answer by username_1 on 2024-12-02. Score: 0

Other examples for the class of problems that exhibit correlated minima are:

1. **Graph Partitioning Problems**
   Graph partitioning problems involve dividing a graph into smaller subgraphs, often with certain constraints. Correlated minima arise due to the symmetry of the graph and the fact that many different partitions can have similar costs.

**Example**: The Graph Bisection Problem, where the goal is to divide a graph into two equal-sized subgraphs with a minimum number of edges between them.
**Correlated Minima**: Different partitions can be obtained by swapping nodes between the two subgraphs or by rotating the subgraphs.

2. **Scheduling Problems**
   Scheduling problems involve assigning tasks to resources, such as machines or vehicles, subject to certain constraints.

**Example**: The Job Shop Scheduling Problem, where the goal is to schedule a set of jobs on a set of machines to minimize the makespan. **Correlated Minima**: Different schedules can be obtained by swapping jobs between machines or by shifting the start times of the jobs.

3. **Clustering Problems**
   Clustering problems involve grouping similar objects into clusters, often subject to certain constraints. Correlated minima arise due to the fact that many different clusterings can have similar costs.

**Example**: The K-Means Clustering Problem, where the goal is to partition a set of points into K clusters to minimize the sum of squared distances to the cluster centers. **Correlated Minima**: Different clusterings can be obtained by swapping points between clusters or by rotating the cluster centers.

4. **Feature Selection Problems**
   Feature selection problems involve selecting a subset of features from a larger set to optimize a certain objective function. Correlated minima arise due to the fact that many different subsets of features can have similar costs.

**Example**: The LASSO Problem, where the goal is to select a subset of features to minimize the sum of squared errors subject to a regularization term. **Correlated Minima**: Different subsets of features can be obtained by adding or removing features or by rotating the feature space.

5. **Optimization Problems on Manifolds with Symmetry**
   Optimization problems on manifolds with symmetry, such as the sphere or the torus, often exhibit correlated minima due to the symmetry of the manifold.

**Example**: The Spherical Optimization Problem, where the goal is to minimize a function on the surface of a sphere. **Correlated Minima**: Different minima can be obtained by rotating the sphere or by reflecting the solution across the equator.

6. **Discrete-Continuous Optimization Problems**
   Discrete-continuous optimization problems involve optimizing both discrete and continuous variables simultaneously. Correlated minima arise due to the interaction between the discrete and continuous variables.

**Example**: The Mixed-Integer Nonlinear Programming (MINLP) Problem, where the goal is to optimize a nonlinear objective function subject to both integer and continuous constraints. **Correlated Minima**: Different minima can be obtained by changing the integer variables or by rotating the continuous variables.


---

