Date: Mon, 02 Dec 1996 15:18:34 GMT Server: NCSA/1.4.2 Content-type: text/html
- Define linear programming (NR 10.8.1-10.8.5) objective function nonnegative values (amount of stuff). combinatorial hard polynomial hard define quadratic programming (M 1.11) NP hard algorithms for PSD case (example? mimum distance, M p.26,27) - geometric interpretation simplex solution on the boundary -- at a vertex (no solution if it's open and maximum "spills" - define: feasible vector feasible basic vector (vertex) (no feasible vectors if it's overconstrained) - combinatorial problem: which vertex? - slack variables. turn inequalities into equalities. turn things into standard form. - techniques: simplex method -- generally fast, worst-case exponential searches vertices ellipsoid method -- provably polynomial, impractical closes in on vertices karmakar -- provably polynomial, arguably practical searches interior points - do simplex method for reduced form. (NR 10.8.8, 10.8.9) - define linear complementary problem (M 1.6-1.8) note: square matrix choice of w or z is 0 no objective function! - turn LP into LCP (M 1.9-1.10) - turn LCP into quadratic (trivial: minimize sum of w.z. better be 0!) - can also turn quadratic into LCP. (too hard!)