This morning I ran across a list of 23 math problems compiled by DARPA [link went away]. I assume their choice of exactly 23 problems was meant to be an allusion to Hilbert’s famous list of 23 math problems from 1900.

Some of Hilbert’s problems were a little broad, but most had crisp mathematical statements. DARPA’s list is the opposite: a few of the questions have a crisp statement, but most are very broad. Hilbert’s problems were pure. DARPA’s problems are applied.

One of the questions that stood out to me concerns computational duality.

Duality in mathematics has been a profound tool for theoretical understanding. Can it be extended to develop principled computational techniques where duality and geometry are the basis for novel algorithms?

I think it’s safe to say the answer is “yes” because it already has been done to some degree, though the question remains as to how much more can be done.

With posets and functional programming I can see this being the case but I haven’t seen any convention where it is in current practice. For more complex cases I wonder how much work would need to be done to make it a safe operation or to determine if it is safe to apply the converse relationship. I don’t know much about dualilty in mathematics, but I assume it probably covers more than just converse relationships. Is this true?

Lagrangian duality is a “turn the crank” device that produces both theoretical insight and novel algorithms. Projecting to the l_1 ball in n dimensions is an example: via a dual problem it can be reduced to a one dimensional search.

Even if the dual problem is not much easier to solve than the original as above, but merely as easy, it gives very useful near-optimality certificates that allow for principled stopping conditions, which certainly helps me sleep at night… ;)

The trick with L. duality is that to get the right dual problem, you have to correctly choose the constraints to include in the Lagrangian, and sometimes the right constraint isn’t even in your problem, but in some trivially equivalent problem.