What can be done to the "Unraveling Method" described below to make it work?

Question

I have an idea I like to call the "Unraveling Method" which will—some day—find applications in visualization, and optimization, thereby solving some of the world’s most computationally difficult problems. Here's how it goes...

The Goal: Imagine you have a function with an arbitrary number of variables, f ( x₁, x₂, x₃, ..., x_N ), for which you need to find the minimum or maximum within a set of bounds. What if there’s a way to convert the problem into an equivalent single variable optimization problem, whose transformation can be reversed [after finding the optima] to give you the optimal coordinates in the original coordinate system? That's the goal of the Unraveling Method in a nutshell and—if you’ll allow it—I’m going to tell you how we’re going to do it.

The Intuition: Lets start out by describing the intuition behind the method for a two variable function f ( x₁, x₂ ). For the time being, trust me that the approach can extend to arbitrarily many dimensions.

You wake up in a pitch-black landscape, where you cannot see the contour around you. In your hand, is an altimeter that shows your altitude relative to sea level, and a GPS apparatus with your instantaneous coordinates. You can instantly explore any point in the landscape, but there’s infinitely many coordinates and little information about the shape of the hills and valleys around you.

Let’s say the point you’re seeking is within a certain rectangular area. What do you do?...

Here’s one thing you could conceivably do:

Choose a “satisfactory precision” for the desired solution and plot a corresponding zig-zag path from one corner of the search region to the opposite corner. Assuming this path’s “mesh” is sufficiently tight to meet our precision requirements, then we can search that path instead. When we find the desired optimum along that path, we can easily get the coordinates in terms of our original variables using the definitions of our path.

Mathematically speaking, we can define a path using a new parametric variable “x” that converts f ( x₁, x₂ ) into a new function g(x) which contains the same maxima/minima information.

For example: We can create one such path by defining x₁ ≡ x and x₂ ≡ A sin(B x + C), where A, B and C are constants that meet our requirements for search space and mesh size. If we then substitute these into f ( x₁, x₂ ) we get g(x).

Conceptually speaking, we have taken the “fabric” that is our 3D surface, unraveled it into a single winding thread and plotted its rises and falls onto a 2D plane.

Great! Problem solved! Onto the next one! Right?... WRONG!

This is where the problems start…

The Unsolved Problem: While we have achieved our goal of reducing the number of variables, we’ve created a different problem which I’ll explain with an example.

Imagine we are trying to use the unraveling method to find the minimum of the function f ( x₁, x₂ ) = x₁² + x₂² within the bounds -1 < x₁ < 1 and -1 < x₂ < 1. This is simple enough to solve with standard calculus methods but will do nicely to illustrate the obstacle at hand.

Here’s a wolfram alpha plot of this function in three dimensions:

https://www.wolframalpha.com/input/?i=plot+f+%3D+x_1%5E2+%2B+x_2%5E2+from+x_1%3D-1+to+x_1%3D1+and+from+x_2%3D-1+to+x_2%3D1

If we define the path x₁ = x and x₂ = sin(100*x) for instance, the new function g (x) we need to find the absolute minimum for is:

g (x) = x² + sin²(100*x)

Here’s the chart for that function plotted in wolfram alpha:

https://www.wolframalpha.com/input/?i=plot+g+%3D+x%5E2+%2B+sin%28100*x%29%5E2+from+x%3D-1+to+x%3D1

Do you see what the problem is?

We have taken a function with only one minimum (the absolute minimum) and converted it into a much more complex function with hundreds of local “false” optima. On the other hand, a peculiar “silver lining” is immediately apparent from looking at the chart…

Take a look at what happens if we plot a tighter mesh size with x₁ = x and x₂ = sin(500*x):

https://www.wolframalpha.com/input/?i=plot+g+%3D+x%5E2+%2B+sin%28500*x%29%5E2+from+x%3D-1+to+x%3D1

Plotting the transform as the frequency (tightness of the path) goes to infinity, has the effect of “coloring in” a region whose boundaries are the single variable functions we were originally looking for. In this case the function we are interested is g (x) = x² and is easily visible to the human eye as the bottom boundary of the region.

The functions defining this edge are what mathematicians call the envelope of the function (since all the points of the original function fit neatly inside of it). Unfortunately finding the envelope of an arbitrary function can involve things like Hilbert transforms, and is no trivial task.

Long story short, if we cannot solve this problem, then the idea is toast! So what could we possibly do? That is the million dollar question and—while I have made some progress toward what the answer might be—I still do not have that answer my friends. That is why we’re here desperately asking the internet for guidance.

I do not want to predispose you: Before I tell you what I did next I wanna see if anybody has some fresh perspectives they can share. Of course—it goes without saying—whomever can solve this problem and get this idea back on track deserves an equal part of the fame and glory.

Even if you do not have an answer I’d love to hear your thoughts. Is it a good concept? Do you think it’s got a chance? Do you know of anything similar?

Thanks,

Daniel Gesua

Answer 1

The basic idea is interesting, but there is a fundamental mathematical obstacle: reducing the dimension does not generally reduce the difficulty of the optimization problem. The complexity that was present in the N-dimensional search space gets transferred into the one-dimensional path.

For example, with

f(x₁,x₂) = x₁² + x₂²

and

x₁ = x,

x₂ = sin(100x),

we obtain

g(x) = x² + sin²(100x).

The many local minima in g are not really “false” minima introduced by the objective function. They arise because the chosen curve repeatedly moves toward and away from the minimum of the original surface. Increasing the frequency makes the path cover the region more densely, but it simultaneously makes g increasingly oscillatory. Thus, the dimensional reduction has exchanged a multidimensional optimization problem for a difficult one-dimensional global optimization problem.

There is also a deeper issue with an exact version of the proposal. A well-behaved one-dimensional curve cannot provide a reversible, one-to-one parametrization of an N-dimensional region for N > 1. There are space-filling curves, such as Peano and Hilbert curves, which continuously map a one-dimensional interval onto a two-dimensional square. However, such mappings cannot simultaneously possess all the properties we would like—for example, being continuous, one-to-one, smoothly invertible, and preserving the useful local geometry of the original optimization problem.

For a finite desired precision, though, the idea becomes much more practical. Discretize each variable:

xᵢ = aᵢ + kᵢΔᵢ.

Each combination of indices (k₁,...,kN) can then be encoded by a single integer k. Consequently, we can define

g(k) = f(x₁(k),...,xN(k)).

This really does transform the finite grid search into a one-dimensional search, and the transformation can be reversed to recover the original coordinates. Space-filling-curve orderings, such as Hilbert or Morton/Z-order, can even be used so that nearby values of k tend to correspond to nearby points in the original space.

The catch is computational complexity. Suppose each of N variables is represented by M possible values. The original search contains

M^N

possible points. Encoding those M^N points with one variable does not make them disappear; the new one-dimensional variable simply has M^N possible values. This is essentially the curse of dimensionality.

There is one particularly important issue with the proposed sine construction. Setting x₁=x means that for each value of x₁ the curve provides only one corresponding x₂. Therefore, it does not actually sample every point of the rectangle at a fixed finite frequency. Making the oscillations increasingly rapid can make the sampling arbitrarily fine in an appropriate sense, but the limit is precisely where the resulting one-dimensional function becomes increasingly difficult to optimize.

So I would not say the idea is “toast.” A productive modification would be:

Replace the sinusoidal path with a discrete space-filling ordering (such as a Hilbert curve), choose a finite required precision, encode every grid point by one parameter, and then use a global rather than local optimization technique on that parameter.

That gives a mathematically legitimate “unraveling” with a reversible coordinate mapping at finite resolution.

What it unfortunately cannot do, for an arbitrary function, is turn a computationally difficult high-dimensional global optimization problem into an intrinsically easy one-dimensional problem. Without additional assumptions about f—smoothness, convexity, Lipschitz bounds, separability, etc.—the information required to locate the global optimum is still present somewhere. The transformation can reorganize that information, but it cannot generally eliminate the underlying computational complexity.