Lagrangian Surfaces Applet - NASA Ames


This demo usually takes just a few seconds to load. If your browser cannot display the interactive interface, please click here for help with installing an updated version of Java for your browser.

This applet demonstrates the use of Probability Collectives to optimize a function G(x) over a discrete, categorical variable x.

More precisely, x is a vector of two binary values. It can take the values (1,1), (1,2), (2,1), or (2,2). (The problem is artificially simple to aid visualization.)

G(x) has a value for each of the values of x, as listed on the left side of the display. Our goal is to find the value of x that minimizes G(x).

Our PC approach is to convert this discrete problem to a continuous one, then use any one of several possible solution methods (e.g., gradient descent) to solve that continuous problem. This conversion permits use of well-developed analytic tools.

* * *

More precisely, we define a four-valued probability distribution q(x). We further choose q(x) to be a product (or separable) probability distribution such that q(x1,x2)=q1(x1)•q2(x2). Let (q1,q2)=(1,1) specify that x1=1 has probability 1 and x2=1 has probability 1. (In other words, x=(1,1) with absolute certainty.) As another example, (q1,q2)=(0,0) assigns all of the probability to x=(2,2). In general, any such q can be represented by two real numbers q1 and q2 in the range [0,1].

Intuitively (but not in fact), the color plot at the left represents the quality of a particular choice of q=(q1,q2).

More formally, the color field represents a function F(q1,q2) equal to G(x)q(x)+TS(q), where T is a temperature parameter and S is the entropy of distribution q(x).

The horizontal axis is q1, the probability that x1=1; the vertical axis is q2. The goal is to find low values of F(q).

To run the Lagrangian optimization demo, use the defaults or enter your own values for G(x), the starting probability distribution (q1,q2), the temperature T, and a step size. (The underlying surface will not update until you hit "Solve.")

Now choose a solution method and click on "Solve." The demo will show the solution method's search for a probability distribution (i.e., a point on the surface) minimizing the objective function F(q).

Once the solution is found, one reduces temperature T. Iterating this process forces the minimum of F(q) toward one of the four corners. Once the algorithm arrives at that corner, you can read out the x minimizing G(x) in terms of the following matrix:


You may want to set the color quantization so that you can easily see the gradient of the surface. (32 works pretty well.) Or maintain high quantization but use the "High Detail" option to visualize the local gradients.

You can run and compare multiple solution methods with a given set of parameters. Click on "Clear" to erase the trajectories and start over.

Applet author: Eugene Turkov