NME130/Optimization

From MurrayWiki
Revision as of 17:57, 16 May 2009 by Murray (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

Summary