| LEC # | TOPICS | READINGS |
|---|---|---|
| 1 | Introduction Review of Convexity and Linear Programming | Bertsekas, Dimitri P., Angelia Nedic, and Asuman E. Ozdaglar. Convex Analysis and Optimization. Belmont, MA: Athena Scientific, 2003. ISBN: 1886529450. Bertsimas, Dimitris, and John N. Tsitsiklis. Introduction to Linear Optimization. Belmont, MA: Athena Scientific, 1997. ISBN: 1886529191. Ben-Tal, A., and Arkadii S. Nemirovskii. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS/SIAM Series on Optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2001. ISBN: 0898714915. Boyd, Steven, and Lieven Vandenberghe. Convex Optimization. New York, NY: Cambridge University Press, 2004. ISBN: 0521833787. Rockafellar, R. Tyrrell. Convex Analysis. Princeton, NJ: Princeton University Press, Princeton, 1970. ISBN: 0691080690. Ziegler, Günter M. Lectures on Polytopes. Vol. 152 of Graduate Texts in Mathematics. New York, NY: Springer-Verlag, 1995. ISBN: 0387943293. |
| 2 | PSD Matrices Semidefinite Programming | Boyd, Steven, and Lieven Vandenberghe. Convex Optimization. New York, NY: Cambridge University Press, 2004. ISBN: 0521833787. Lovász, L. "On the Shannon Capacity of a Graph." IEEE Transactions on Information Theory 25, no. 1 (1979): 1-7. Ramana, M. V. "An Exact Duality Theory for Semidefinite Programming and its Complexity Implications." Math Programming 77, no. 2, Ser. B (1997): 129-162. Ramana, M. V., L. Tunçel, and H. Wolkowicz. "Strong Duality for Semidefinite Programming." SIAM J Optim 7, no. 3 (1997): 641-662. |
| 3 | Binary Optimization Bounds: Goemans-Williamson and Nesterov Linearly Constrained Problems | Ben-Tal, A., and Arkadii S. Nemirovskii. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS/SIAM Series on Optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2001. ISBN: 0898714915. Garey, M. R., and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. New York, NY: W. H. Freeman and Company, 1979. ISBN: 0716710447. Goemans, M. X., and D. P. Williamson. "Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming." Journal of the ACM 42, no. 6 (1995): 1115-1145. Megretski, A. "Relaxations of Quadratic Programs in Operator Theory and System Analysis." In Systems, Approximation, Singular Integral Operators, and Related Topics (Bordeaux, 2000). Edited by Alexander A. Borichev and N. K. Nikolski. Vol. 129 of Operator Theory Advances and Applications. Boston, MA: Birkhäuser Verlag, 2001, pp. 365-392. ISBN: 3764366451. |
| 4 | Review: Groups, Rings, Fields Polynomials and Ideals | Bochnak, J., M. Coste, and M.-F. Roy. Real Algebraic Geometry. New York, NY: Springer, 1998. ISBN: 3540646639. Cox, D. A., J. B. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York, NY: Springer, 1997. ISBN: 0387946802. Dummit, David S., and Richard M. Foote. Abstract Algebra. Englewood Cliffs, NJ: Prentice Hall, 1991. ISBN: 0130047716. Lang, Serge. Algebra. Reading, MA: Addison-Wesley, 1971. ISBN: 0201041774. |
| 5 | Univariate Polynomials Root Bounds and Sturm Sequences Counting Real Roots Nonnegativity Sum of Squares Positive Semidefinite Matrices | Basu, S., R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics). Vol. 10. New York, NY: Springer-Verlag, 2003. ISBN: 3540009736. Horn, Roger A., and Charles R. Johnson. Matrix Analysis. Cambridge, UK: Cambridge University Press, 1995. ISBN: 0521305861. |
| 6 | Resultants Discriminants Applications The set of Nonnegative Polynomials | Andradas, C. "Characterization and description of basic semialgebraic sets." In Algorithmic and Quantitative Real Algebraic Geometry (Piscataway, NJ, 2001). Edited by Basu, Saugata and Laureano Gonzalez Vega. DIMACS Ser Discrete Math Theoret Comput Sci, 60. Providence, RI: American Mathematical Society, 2003. pp. 1-12. ISBN: 0821828630. Cox, D. A., J. B. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York, NY: Springer, 1997. ISBN: 0387946802. Faybusovich, L. "Self-concordant Barriers for Cones Generated by Chebyshev Systems." SIAM J Optim 12, no. 3 (2002): 770-781. Kao, C. Y., and A. Megretski. "A New Barrier Function for IQC Optimization Problems." In Proceedings of the American Control Conference. Piscataway, NJ: IEEE, 2002. ISBN: 0780372980. Ramana, M., and A. J. Goldman. "Some Geometric Results in Semidefinite Programming." J Global Optim 7, no.1 (1995): 33-50. Sturmfels, B. "Introduction to Resultants." In Applications of Computational Algebraic Geometry (San Diego, CA, 1997). Edited by David A. Cox, Bernd Sturmfels, and Dinesh N. Manocha. Vol. 53. Proc Sympos Appl Math. Providence, RI: American Mathematical Society, 1998, pp. 25-39. ISBN: 0821807501. |
| 7 | Hyperbolic Polynomials SDP Representability | Bauschke, H. H., O. Güler, A. S. Lewis, and H. S. Sendov. "Hyperbolic polynomials and convex analysis." Canad J Math 53, no. 3 (2001): 470-488. Boyd, Steven, and Lieven Vandenberghe. Convex Optimization. New York, NY: Cambridge University Press, 2004. ISBN: 0521833787. Gårding, L. "An Inequality for Hyperbolic Polynomials." J Math Mech 8 (1959): 957-965. Güler, O. "Hyperbolic polynomials and interior point methods for convex programming." Math Oper Res 22, no. 2 (1997): 350-377. Nesterov, Y. E., and A. Nemirovski. Interior-Point Polynomial Methods in Convex Programming. Vol. 13. Studies in Applied Mathematics. Philadelphia, PA: SIAM, 1994. ISBN: 0898713196. Renegar, J. "Hyperbolic Programs, and Their Derivative Relaxations." Preprint, 2005. |
| 8 | SDP Representability Convex Sets in R2 Hyperbolicity and the Lax Conjecture Relating SDP-representable Sets and Hyperbolic Polynomials Characterization | Helton, J. W., and V. Vinnikov. Linear Matrix Inequality Representation of Sets. Preprint. Lax, P. D. "Differential equations, Difference Equations, and Matrix Theory." Comm Pure Appl Math 11 (1958): 175-194. Lewis, A. S., P. A. Parrilo, and M. V. Ramana. "The Lax Conjecture is True." Proc Amer Math Soc 133, no. 9 (2005): 2495-2499. |
| 9 | Binomial Equations Newton Polytopes The Bézout and BKK Bounds Application: Nash Equilibria | Sturmfels, B. Solving Systems of Polynomial Equations. Providence, RI: American Mathematical Society, 2002. ISBN: 0821832514. |
| 10 | Nonegativity and Sums of Squares Sums of Squares and Semidefinite Programming Applications and Extensions Multivariate Polynomials Duality and Density | Reznick, B. "Extremal PSD Forms With Few Terms." Duke Mathematical Journal 45, no. 2 (1978): 363-374. Reznick, B. "Some Concrete Aspects of Hilbert's 17th Problem." In Real Algebraic Geometry and Ordered Structures. Edited by Charles N. Delzell, and James J. Madden. Vol. 253. Contemporary Mathematics. Providence, RI: American Mathematical Society, 2000, pp. 251-272. ISBN: 0821808044. |
| 11 | SOS Applications Moments Bridging the Gap | Parrilo, P. A. "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization." PhD diss., California Institute of Technology, May 2000. Papachristodoulou, A., and S. Prajna. "On the Construction of Lyapunov Functions Using the Sum of Squares Decomposition." In Proceedings of the 41st IEEE Conference on Decision and Control. New York, NY: IEEE, 2002. ISSN: 07431546. Prajna, S., A. Papachristodoulou, and P. A. Parrilo. SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB®, 2002-05. Available from SOSTOOLS and SOSTOOLS. |
| 12 | Recovering a Measure from its Moments A Probabilistic Interpretation Duality and Complementary Slackness Multivariate Case Density Results | Blekherman, G. "There are Significantly More Nonnegative Polynomials Than Sums of Squares." Preprint, 2004. Lasserre, J. B. "Global Optimization With Polynomials and the Problem of Moments." SIAM J Optim 11, no. 3 (2001): 796-817. |
| 13 | Polynomial Ideals Algebraic Varieties Quotient Rings Monomial Orderings | Cox, D. A., J. B. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York, NY: Springer, 1997. ISBN: 0387946802. |
| 14 | Monomial Orderings Gröbner Bases Applications and Examples Zero-dimensional Ideals | Adams, William W., and Philippe Loustaunau. An Introduction to Gröbner Bases. Vol. 3. Graduate Studies in Mathematics. Providence, RI: American Mathematical Society, 1994. ISBN: 0821838040. Becker, Thomas, and Volker Weispfenning. Gröbner Bases. Vol. 141. Graduate Texts in Mathematics. New York, NY: Springer-Verlag, 1993. ISBN: 0387979719. Cox, D. A., J. B. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York, NY: Springer, 1997. ISBN: 0387946802. CoCoATeam. "CoCoA: A System for Doing Computations in Commutative Algebra." Greuel, G.-M., G. Pfister, and H. Schönemann. "Singular 3.0." A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2005. Grayson, D. R., and M. E. Stillman. "Macaulay 2." A Software System for Research in Algebraic Geometry. Kreuzer, Martin, and Lorenzo Robbiano. Computational Commutative Algebra 1. Berlin, Germany: Springer-Verlag, 2000. ISBN: 354067733X. |
| 15 | Zero-dimensional Ideals Hilbert Series | Conti, P., and C. Traverso. "Buchberger Algorithm and Integer Programming." In Applied Algebra, Algebraic Algorithms and Error-correcting Codes: 9th International Symposium (New Orleans, LA, 1991). Edited by H. F. Mattson, Teo Mora, and T. R. N. Rao. Lecture Notes in Computer Science, 539. New York, NY: Springer-Verlag, 1991, pp. 130-139. ISBN: 0387545220. Sturmfels, B., and R. R. Thomas. "Variation of Cost Functions in Integer Programming." Math Programming 77 Ser. A, no. 3 (1997): 357-387. Thomas, R., and R. Weismantel. "Truncated Gröbner Bases for Integer Programming." Appl Algebra Engrg Comm Comput 8, no. 4 (1997): 241-256. |
| 16 | Generalizing the Hermite Matrix Parametric Versions SOS on Quotients | Parrilo, P. A. An Explicit Construction of Distinguished Representations of Polynomials Nonnegative Over Finite Sets. IfA Technical Report AUT02-02, March 2002. ETH Zürich, 2002. (PDF) |
| 17 | Infeasibility of Real Polynomial Equations Certificates The Zero-dimensional Case Optimization | Davis, M. "Hilbert's Tenth Problem is Unsolvable." Amer Math Monthly 80 (1973): 233-269. Jeroslow, R. G. "There Cannot Be Any Algorithm for Integer Programming With Quadratic Constraints." Operations Res 21 (1973): 221-224. Parrilo, P. A. An Explicit Construction of Distinguished Representations of Polynomials Nonnegative Over Finite Sets. IfA Technical Report AUT02-02, March 2002. ETH Zürich, 2002. (PDF) |
| 18 | Quantifier Elimination Tarski-Seidenberg Cylindrical Algebraic Decomposition (CAD) | Anderson, B. D. O., N. K. Bose, and E. I. Jury. "Output Feedback Stabilization and Related Problems-Solution Via Decision Methods." IEEE Transactions on Automatic Control 20 (1975): 53-66. Blondel, Vincent, and M. Gevers. "Simultaneous Stabilizability of Three Linear Systems is Rationally Undecidable." Mathematics of Control, Signals, and Systems 6, no. 2 (1993): 135-145. Blondel, Vincent. Simultaneous Stabilization of Linear Systems. Lecture Notes in Control and Information Sciences, 191. New York, NY: Springer-Verlag, 1994. ISBN: 0387198628. Basu, Saugata, Richard Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Vol. 10. Algorithms and Computation in Mathematics. New York, NY: Springer-Verlag, 2003. ISBN: 3540009736. Brown, C. W. QEPCAD - Quantifier Elimination by Partial Cylindrical Algebraic Decomposition, 2003. Caviness, Bob F., and J. R. Johnson, eds. Quantifier Elimination and Cylindrical Algebraic Decomposition (Texts and Monographs in Symbolic Computation). New York, NY: Springer-Verlag, 1998. ISBN: 3211827943. Collins, G. E. "Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition." In Automata Theory and Formal Languages (Second GI Conf, Kaiserslautern, 1975). Edited by H. Brakhage. Lecture Notes in Computer Science, 33. New York, NY: Springer-Verlag, 1975, pp. 134-183. ISBN: 0387074074. Renegar, J. "Recent Progress on the Complexity of the Decision Problem for the Reals." In Discrete and Computational Geometry (New Brunswick, NJ, 1989/1990). Edited by Goodman, Jacob, Richard D. Pollack, and William L. Steiger. DIMACS Ser Discrete Math Theoret Comput Sci, 6. Providence, RI: American Mathematical Society, 1991, pp. 287-308. ISBN: 0821865951. |
| 19 | Certificates Psatz Revisited Copositive Matrices and Pólya's Theorem Positive Polynomials | Bochnak, J., M. Coste, and M.-F. Roy. Real Algebraic Geometry. New York, NY: Springer, 1998. ISBN: 3540646639. Kumar, P. R., and S. P. Meyn. "Duality and Linear Programs for Stability and Performance Analysis of Queuing Networks and Scheduling Policies." IEEE Trans Automat Control 41, no. 1 (1996): 4-17. Marshall, M. Positive Polynomials and Sums of Squares. Dottorato de Ricerca in Matematica. Dept di Mat, Univ Pisa, 2000. Parrilo, P. A. "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization." PhD diss, California Institute of Technology, May 2000. Prestel, A., and C. N. Delzell. Positive Polynomials: From Hilbert's 17th Problem to Real Algebra. Springer Monographs in Mathematics. New York, NY: Springer, 2001. ISBN: 3540412158. Schmüdgen, K. "The K-moment Problem for Compact Semialgebraic Sets." Math Ann 289 (1991): 203-206. |
| 20 | Positive Polynomials Schmüdgen's Theorem | Berg, Christian, Jens P. R. Christensen, and Paul Ressel. Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions. Graduate Texts in Mathematics, 100. New York, NY: Springer-Verlag, 1984. ISBN: 0387909257. Bochnak, J., M. Coste, and M.-F. Roy. Real Algebraic Geometry. New York, NY: Springer-Verlag, 1998. ISBN: 3540646639. Lasserre, J. B. "Global optimization with polynomials and the problem of moments." SIAM J Optim 11, no. 3 (2001): 796-817. Marshall, M. Positive Polynomials and Sums of Squares. Dottorato de Ricerca in Matematica. Dept di Mat, Univ Pisa, 2000. Megretski, A. "Positivity of Trigonometric Polynomials." In Proceedings of the 42nd IEEE Conference on Decision and Control (2003): 3814-3817. ISSN: 07431546. Parrilo, P. A. "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization." PhD diss., California Institute of Technology, May 2000. ———. "Semidefinite Programming Relaxations for Semialgebraic problems." Math Prog 96 Ser. B, no. 2 (2003): 293-320. Prestel, A., and C. N. Delzell. Positive Polynomials: From Hilbert's 17th Problem to Real Algebra. Springer Monographs in Mathematics. New York, NY: Springer-Verlag, 2001. ISBN: 3540412158. Putinar, M. "Positive Polynomials on Compact Semi-algebraic Sets." Indiana Univ Math J 42, no. 3 (1993): 969-984. Rudin, Walter. Fourier Analysis on Groups. Wiley Classics Library. New York, NY: John Wiley & Sons Inc., 1990. ISBN: 047152364X. Schmüdgen, K. "The K-moment Problem for Compact Semialgebraic Sets." Math Ann 289 (1991): 203-206. Stengle, G. "Complexity Estimates for the Schmüdgen Positivstellensatz." J Complexity 12, no. 2 (1996): 167-174. |
| 21 | Groups and their Representations Algebra Decomposition | Boyd, S., P. Diaconis, P. A. Parrilo, and L. Xiao. "Symmetry Analysis of Reversible Markov Chains." Internet Math 2, no. 1 (2005): 31-71. de Klerk, E., J. Maharry, D.V. Pasechnik, R. B. Richter, and G. Salazar. "Improved Bounds for the Crossing Numbers of K_m,n and K_n." SIAM J. Discr. Math. 20, (2006): 189-202. Fässler, Albert, and Eduard Stiefel. Group Theoretical Methods and Their Applications. Boston, MA: Birkhäuser, 1992. ISBN: 0817635270. Gatermann, K., and P. A. Parrilo. "Symmetry Groups, Semidefinite Programs, and Sums of Squares." Journal of Pure and Applied Algebra 192, nos. 1-3 (2004): 95-128. Parrilo, P. A., and R. Peretz. "An Inequality for Circle Packings Proved by Semidefinite Programming." Discrete and Computational Geometry 31, no. 3 (2004): 357-367. Schrijver, A. "New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming." IEEE Transactions on Information Theory 51, no. 8 (2005): 2859-2866. Serre, J.-P. Linear Representations of Finite Groups. New York, NY: Springer-Verlag, 1977. ISBN: 0387901906. |
| 22 | Sums of Squares Programs and Polynomial Inequalities | Parrilo, P. A. "Sums of Squares Programs and Polynomial Inequalities." Preprint. |
Table of Contents
Study Materials
Readings
 Help support MIT OpenCourseWare by shopping at Amazon.com! MIT OpenCourseWare offers direct links to Amazon.com to purchase the books cited in this course. Click on the book titles and purchase the book from Amazon.com, and MIT OpenCourseWare will receive up to 10% of all purchases you make. Your support will enable MIT to continue offering open access to MIT courses. |
Suggested Texts
Cox, D. A., John B. Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York, NY: Springer-Verlag, 1997. ISBN: 0387946802.
de Klerk, Etienne. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications. Boston, MA: Kluwer Academic Publishers, 2002. ISBN: 1402005474.
Mishra, Bhubaneswar. Algorithmic Algebra. New York, NY: Springer-Verlag, 1993. ISBN: 0387940901.
Sturmfels, Bernd. Solving Systems of Polynomial Equations. Providence, RI: American Mathematical Society, 2002. ISBN: 0821832514.
Wolkowicz, Henry, Romesh Saigal, and Lieven Vandenberghe, eds. Handbook of Semidefinite Programming. Boston, MA: Kluwer Academic Publishers, 2000. ISBN: 0792377710.
Yap, Chee-Keng. Fundamental Problems of Algorithmic Algebra. New York, NY: Oxford University Press, 2000. ISBN: 0195125169.
Readings by Session