Readings

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

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.