NME130/Optimization

Present: John Doyle, Ben Recht, Javad Lavaei, Andy Lamperski, Ufuk Topcu, Richard Murray, Steven Low, Tracey Ho

Starting list of topics (from previous discussions)

• Linear programming/duality
• Optimization and lower bounds, with applications in control
• Computational complexity?
• Convex analysis

John Doyle presentation

Design lattice

At a higher level (?), this will be done in the context of lattices (to talk about complexity)

• Duality
• Crashes/barriers/proofs
• Complex descriptions
• Robustness and fragility
• Proof complexity
• Complexity and fragility
• ???

The idea here is to cover the notions of complexity and what leads to problem complexity, proof complexity, etc. Lattices provides a natural set of questions to ask (max flow, paths, design of the lattice itself). Can link to primal/dual methods (horizontal vs vertical paths) ⇒ get duality right up front. Should be able to get to the following issues:

• Functionality and constraints
• Can seqway to linear programs, boolean SAT, cellular automata, P/NP/coNP (hard to find, easy to check)
  • Need to figure out who much to go into P, NP, coNP, etc
• Minimax framework (find most robust path)
• Leads to complexity implies fragility

Graphs and linear programs

These are the standard tools that will be taught in class:

• MaxFlow = MinCut
• LP duality
• Distributed
• LP relaxations
• SDPs/relaxations

Can related all of this to the lattice picture, but basically show the same results:

• Complexity implies fragility
• Can segue off to SOS, etc

Applications

Not so clear what to do here: biology, networks, power flows, etc

Discussion items

• What application should we use to describe/motivate this? Lattices? Network flows?
• Should we do a high-level lattice picture first, or dive into the mathematics of linear programming
• How much of this goes in the optimization and algorithms "course" versus into NME 130