Constraint Problems

January 23 - February 13

Instructor: Veit Elser

Office hours: Tuesdays 1-3 pm

As a condensed matter theorist it may happen that you find yourself trying to reconstruct something (a signal, molecule, wavefunction) from a variety of clues (measurements, prior knowledge, models). In this segment of Basic Training you will be introduced to a computational technique that has proven remarkably successful at solving a great variety of problems. One of the most important lessons is that many problems that conventionally are formulated in terms of function minimization can be solved more efficiently when expressed in the language of constraints. We therefore start by exploring the kinds of constraints that arise, and the elementary operations, called projections, that form the building blocks of algorithms. Here is a tentative outline:

constraints as sets
projecting to constraints
iterative algorithms as dynamical systems
solving problems by divide & concur

There will be two homework assignments. The first is a survey of constraint projections and will call on your linear algebra skills. In the second assignment you are given a choice of problems to solve on a computer using the new technique. You may use whatever programming language suits you best.

Documents

Optimizing the Metric (notes for the lecture that was cancelled)

Teasers

Homework

First homework assignment, due Friday, February 1, solutions
Second homework assignment, due Wednesday, February 13; data: distances.dat, pair_energies.dat, fourier_mag.dat

Demos (Mathematica 6)

image reconstruction definitions, data, solve
graeco-latin squares definitions, solve
linear diophantine equations definitions, data, solve
disk packing definitions, data, solve
bit retrieval definitions, data, solve, simulated-annealing
distance geometry definitions, data, solve
spin glass definitions, data, solve
complex images definitions, data, solve