CIMMS Focused Workshop on
About This Workshop
| Schedule
| Relevant Links
| CIMMS Home
WELCOME
This workshop is inspired by the great success of the
recent workshop at IPAM on large scale communications networks; see
The CIMMS one day workshop will focus on a particular theme,
namely that of duality and optimization and related techniques.
It is also inspired by some very recent work of the invited
speakers, such as links to spatially distributed mechanics
and asynchronous integration methods.
The goal of the workshop is to provide an informal forum
for the exchange of ideas in this rapidly developing and exciting
area.
| ||||||||||||||||||||||||||||||||||
ORGANIZERS: Jerry Marsden (Caltech, Chair) Melvin Leok (Caltech) |
About This Workshop
The purpose of this workshop is to explore the relations between duality, TCP control, hard computational problems that are intrinsically fragile, optimization problems, and networks in general, and methods used for asynchronous variational integrators in mechanics. Many problems that would otherwise be intrinsically hard or very fragile (even conservation of energy in computational mechanics) can be dealt with using geometric structures, especially duality associated with variational problems. For example, variational integrators build the variational structure into the algorithms and it is as a consequence this that one gets remarkably good energy behavior for mechanical systems. The duality approach in TCP has a very nice mechanical interpretation, which reveals a correspondence between the feedback mechanism in TCP and variational integration for continuum mechanics. There are close connections between multiscale PDE solvers (as described above and e.g., Jaime Peraire (MIT), "A General Lagrangian Formulation for the computation of a-posteriori Finite Element Bounds") and robust control "upper bounds", and Parillos's SOS/SDP relaxations work (and thus computing quantum entanglement, maxcut, etc), Low's duality in networks, and "phase transitions" in computational complexity. One common theme in all this is that there is typically some primal problem that is in coNP, and a dual that is NP, and thus searchable. The dual can give a posteriori bounds on the primal, and when there is no duality gap, can be exact (Parillo's work gives a systematic method for eliminating duality gaps asymptotically for a broad range of coNP hard problems) and can often be solved in a decentralized and asynchronous way (where Low's work on duality in TCP/IP). What is interesting is that this duality all has nice mechanics interpretations, since there are advantages to viewing mechanics and computational problems variationally. Duality may be used to provide proofs verifying the robustness of embedded systems in a networked environment, and in creating inference processes for comparing data and models in biological systems. Also, it gives a unifying framework for treating both the vertical, protocol stack decomposition of networks, and the horizontal, or distributed and asynchronous control that occurs at each level in the stack. One objective is to show that duality ideas can (fairly) systematically produce convergence proofs plus a posteriori error bounds for hopefully radically simplified computational schemes for a wide variety of multiscale and network problems. The computational schemes can be driven by straight computational complexity in solving PDEs on adaptive meshes or in doing variational integrators for mechanics problems or in computing quantum entanglement or other NP hard problems. But the same ideas lead to asynchronous and distributed algorithms for doing robust computations of resource allocations across networks. The duality theory of Linear Programming has had profound influence on the theory of Approximation Algorithms for NP-hard optimization problems. Today's application areas, such as Internet problems, network design and biology, are characterized by massively large problem instances and require reliable solutions, preferably with proven guarantees. The primal-dual schema has been successful on several such NP-hard problems, having provided algorithms with good guarantees and good running times. Recent extensions of this schema to handling non-optimization problems in the nascent area of Algorithmic Game Theory have yielded the first polynomial time algorithm for computing market equilibria in a framework given by Irving Fischer in 1891 (assuming linear utility functions). |
|||||||||||||||||||||||||||||||||
104 Watson
Monday, July 1, 2002 10:00 a.m. to 5:30 p.m. |
Schedule (pdf)
WEB LINKS TO IPAM ACTIVITES |
|||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||
back
to workshops |
|