https://murray.cds.caltech.edu/index.php?action=history&feed=atom&title=NME130%2FOptimizationNME130/Optimization - Revision history2026-09-07T03:37:01ZRevision history for this page on the wikiMediaWiki 1.44.2https://murray.cds.caltech.edu/index.php?title=NME130/Optimization&diff=9358&oldid=prevMurray at 17:57, 16 May 20092009-05-16T17:57:26Z<p></p>
<p><b>New page</b></p><div>{{righttoc}}<br />
<br />
Present: John Doyle, Ben Recht, Javad Lavaei, Andy Lamperski, Ufuk Topcu, Richard Murray, Steven Low, Tracey Ho<br />
<br />
Starting list of topics (from previous discussions)<br />
* Linear programming/duality<br />
* Optimization and lower bounds, with applications in control<br />
* Computational complexity?<br />
* Convex analysis<br />
<br />
== John Doyle presentation ==<br />
<br />
=== Design lattice ===<br />
At a higher level (?), this will be done in the context of lattices (to talk about complexity)<br />
* Duality<br />
* Crashes/barriers/proofs<br />
* Complex descriptions<br />
* Robustness and fragility<br />
* Proof complexity <br />
* Complexity and fragility<br />
* ???<br />
<br />
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) {{implies}} get duality right up front. Should be able to get to the following issues:<br />
* Functionality and constraints<br />
* Can seqway to linear programs, boolean SAT, cellular automata, P/NP/coNP (hard to find, easy to check)<br />
** Need to figure out who much to go into P, NP, coNP, etc<br />
* Minimax framework (find most robust path)<br />
* Leads to complexity implies fragility<br />
<br />
=== Graphs and linear programs ===<br />
These are the standard tools that will be taught in class:<br />
* MaxFlow = MinCut<br />
* LP duality<br />
* Distributed<br />
* LP relaxations<br />
* SDPs/relaxations<br />
<br />
Can related all of this to the lattice picture, but basically show the same results:<br />
* Complexity implies fragility<br />
* Can segue off to SOS, etc<br />
<br />
=== Applications ===<br />
Not so clear what to do here: biology, networks, power flows, etc<br />
<br />
== Discussion items ==<br />
* What application should we use to describe/motivate this? Lattices? Network flows?<br />
* Should we do a high-level lattice picture first, or dive into the mathematics of linear programming<br />
* How much of this goes in the optimization and algorithms "course" versus into NME 130<br />
<br />
== Summary ==</div>Murray