back to workshops

 

104 Watson
Monday, July 1, 2002
10:00 a.m. to 5:30 p.m.



CIMMS Focused Workshop on
Networks, Optimization, and Duality

About This Workshop | Schedule | Relevant Links | CIMMS Home


WELCOME
to the CIMMS Workshop on "Optimization, Networks and Duality"

This workshop is inspired by the great success of the recent workshop at IPAM on large scale communications networks; see

http://www.ipam.ucla.edu/programs/cn2002/

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.

top


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).

top

104 Watson
Monday, July 1, 2002
10:00 a.m. to 5:30 p.m.

Schedule (pdf)


MONDAY, JULY 1, 2002

Moderator: TBA

10-11 a.m.

John Doyle, Caltech
Complexity Implies Fragility (presentation pdf)

11:00-noon

Steven Low, Caltech
A Duality Model of Internet Congestion Control (presentation pdf)

noon-1:00

Catered Lunch


Afternoon Session:

1:00-2:00

Vijay V. Vazirani, Georgia Tech
The Primal-Dual Schema and its Applications to Game Theory

2:00-3:00

Sanjay Lall, Stanford University
Duality and asynchronous distributed algorithms for variational mechanics and feedback control of networks.

3:00-3:30
Coffee Break

3:30-4:30

Matt West, Caltech
The duality of Lagrangian and Hamiltonian mechanics in continuous and discrete time

4:30-5:30

John Doyle (Chair), Caltech
Wrap-up Discussions

   

top

 

WEB LINKS TO RELEVANT PAPERS

 

WEB LINKS TO IPAM ACTIVITES

http://www.ipam.ucla.edu/programs/cn2002/

back to workshops