# 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