everything.study
6.972

Algebraic Techniques and Semidefinite Optimization

Graduate · Historical course

Spring 2006

This research-oriented course will focus on algebraic and computational techniques for optimization problems involving polynomial equations and inequalities with particular emphasis on the connections with semidefinite optimization. The course will develop in a parallel fashion several algebraic and numerical approaches to polynomial systems, with a view towards methods that simultaneously incorporate both elements. We will study both the complex and real cases, developing techniques of general applicability, and stressing convexity-based ideas, complexity results, and efficient implementations. Although we will use examples from several engineering areas, particular emphasis will be given to those arising from systems and control applications.

Readings

  • 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.
    Listed reading
  • de Klerk, Etienne. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications . Boston, MA: Kluwer Academic Publishers, 2002. ISBN: 1402005474.
    Listed reading
  • Mishra, Bhubaneswar. Algorithmic Algebra . New York, NY: Springer-Verlag, 1993. ISBN: 0387940901.
    Listed reading
  • Sturmfels, Bernd. Solving Systems of Polynomial Equations . Providence, RI: American Mathematical Society, 2002. ISBN: 0821832514.
    Listed reading
  • Wolkowicz, Henry, Romesh Saigal, and Lieven Vandenberghe, eds. Handbook of Semidefinite Programming . Boston, MA: Kluwer Academic Publishers, 2000. ISBN: 0792377710.
    Listed reading
  • Yap, Chee-Keng. Fundamental Problems of Algorithmic Algebra . New York, NY: Oxford University Press, 2000. ISBN: 0195125169.
    Listed reading
  • Bertsekas, Dimitri P., Angelia Nedic, and Asuman E. Ozdaglar. Convex Analysis and Optimization . Belmont, MA: Athena Scientific, 2003. ISBN: 1886529450.
    Listed reading
  • Bertsimas, Dimitris, and John N. Tsitsiklis. Introduction to Linear Optimization . Belmont, MA: Athena Scientific, 1997. ISBN: 1886529191.
    Listed reading
  • 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.
    Listed reading
  • Boyd, Steven, and Lieven Vandenberghe. Convex Optimization . New York, NY: Cambridge University Press, 2004. ISBN: 0521833787.
    Listed reading
  • Rockafellar, R. Tyrrell. Convex Analysis . Princeton, NJ: Princeton University Press, Princeton, 1970. ISBN: 0691080690.
    Listed reading
  • Ziegler, Günter M. Lectures on Polytopes . Vol. 152 of Graduate Texts in Mathematics. New York, NY: Springer-Verlag, 1995. ISBN: 0387943293.
    Listed reading
  • Lovász, L. “On the Shannon Capacity of a Graph.” IEEE Transactions on Information Theory 25, no. 1 (1979): 1-7.
    Listed reading
  • Ramana, M. V. “An Exact Duality Theory for Semidefinite Programming and its Complexity Implications.” Math Programming 77, no. 2, Ser. B (1997): 129-162.
    Listed reading
  • Ramana, M. V., L. Tunçel, and H. Wolkowicz. “Strong Duality for Semidefinite Programming.” SIAM J Optim 7, no. 3 (1997): 641-662.
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • Bochnak, J., M. Coste, and M.-F. Roy. Real Algebraic Geometry . New York, NY: Springer, 1998. ISBN: 3540646639.
    Listed reading
  • 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.
    Listed reading
  • Dummit, David S., and Richard M. Foote. Abstract Algebra . Englewood Cliffs, NJ: Prentice Hall, 1991. ISBN: 0130047716.
    Listed reading
  • Lang, Serge. Algebra . Reading, MA: Addison-Wesley, 1971. ISBN: 0201041774.
    Listed reading
  • 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.
    Listed reading
  • Horn, Roger A., and Charles R. Johnson. Matrix Analysis . Cambridge, UK: Cambridge University Press, 1995. ISBN: 0521305861.
    Listed reading
  • 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.
    Listed reading
  • Faybusovich, L. “ Self-concordant Barriers for Cones Generated by Chebyshev Systems .” SIAM J Optim 12, no. 3 (2002): 770-781. ↗
    Listed reading
  • 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.
    Listed reading
  • Ramana, M., and A. J. Goldman. “Some Geometric Results in Semidefinite Programming.” J Global Optim 7, no.1 (1995): 33-50.
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • Gårding, L. “An Inequality for Hyperbolic Polynomials.” J Math Mech 8 (1959): 957-965.
    Listed reading
  • Güler, O. “Hyperbolic polynomials and interior point methods for convex programming.” Math Oper Res 22, no. 2 (1997): 350-377.
    Listed reading
  • 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.
    Listed reading
  • Renegar, J. “Hyperbolic Programs, and Their Derivative Relaxations.” Preprint, 2005.
    Listed reading
  • Helton, J. W., and V. Vinnikov. Linear Matrix Inequality Representation of Sets . Preprint. ↗
    Listed reading
  • Lax, P. D. “Differential equations, Difference Equations, and Matrix Theory.” Comm Pure Appl Math 11 (1958): 175-194.
    Listed reading
  • 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.
    Listed reading
  • Reznick, B. “Extremal PSD Forms With Few Terms.” Duke Mathematical Journal 45, no. 2 (1978): 363-374.
    Listed reading
  • 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.
    Listed reading
  • Parrilo, P. A. “ Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization .” PhD diss., California Institute of Technology, May 2000. ↗
    Listed reading
  • 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.
    Listed reading
  • Prajna, S., A. Papachristodoulou, and P. A. Parrilo. SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB®, 2002-05. Available from SOSTOOLS and SOSTOOLS . ↗
    Listed reading
  • Blekherman, G. “There are Significantly More Nonnegative Polynomials Than Sums of Squares.” Preprint, 2004.
    Listed reading
  • Lasserre, J. B. “Global Optimization With Polynomials and the Problem of Moments.” SIAM J Optim 11, no. 3 (2001): 796-817.
    Listed reading
  • 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.
    Listed reading
  • Becker, Thomas, and Volker Weispfenning. Gröbner Bases . Vol. 141. Graduate Texts in Mathematics. New York, NY: Springer-Verlag, 1993. ISBN: 0387979719.
    Listed reading
  • 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. ↗
    Listed reading
  • Kreuzer, Martin, and Lorenzo Robbiano. Computational Commutative Algebra 1 . Berlin, Germany: Springer-Verlag, 2000. ISBN: 354067733X.
    Listed reading
  • 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.
    Listed reading
  • Sturmfels, B., and R. R. Thomas. “Variation of Cost Functions in Integer Programming.” Math Programming 77 Ser. A, no. 3 (1997): 357-387.
    Listed reading
  • Thomas, R., and R. Weismantel. “Truncated Gröbner Bases for Integer Programming.” Appl Algebra Engrg Comm Comput 8, no. 4 (1997): 241-256.
    Listed reading
  • Davis, M. “Hilbert’s Tenth Problem is Unsolvable.” Amer Math Monthly 80 (1973): 233-269.
    Listed reading
  • Jeroslow, R. G. “There Cannot Be Any Algorithm for Integer Programming With Quadratic Constraints.” Operations Res 21 (1973): 221-224.
    Listed reading
  • 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 ) ↗
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • Blondel, Vincent. Simultaneous Stabilization of Linear Systems . Lecture Notes in Control and Information Sciences, 191. New York, NY: Springer-Verlag, 1994. ISBN: 0387198628.
    Listed reading
  • 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.
    Listed reading
  • Brown, C. W. QEPCAD - Quantifier Elimination by Partial Cylindrical Algebraic Decomposition , 2003. ↗
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • Marshall, M. Positive Polynomials and Sums of Squares . Dottorato de Ricerca in Matematica. Dept di Mat, Univ Pisa, 2000.
    Listed reading
  • Parrilo, P. A. “ Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization .” PhD diss, California Institute of Technology, May 2000. ↗
    Listed reading
  • 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.
    Listed reading
  • Schmüdgen, K. “The K-moment Problem for Compact Semialgebraic Sets.” Math Ann 289 (1991): 203-206.
    Listed reading
  • 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.
    Listed reading
  • Bochnak, J., M. Coste, and M.-F. Roy. Real Algebraic Geometry . New York, NY: Springer-Verlag, 1998. ISBN: 3540646639.
    Listed reading
  • Lasserre, J. B. “Global optimization with polynomials and the problem of moments.” SIAM J Optim 11, no. 3 (2001): 796-817.
    Listed reading
  • Megretski, A. “Positivity of Trigonometric Polynomials.” In Proceedings of the 42nd IEEE Conference on Decision and Control (2003): 3814-3817. ISSN: 07431546.
    Listed reading
  • ———. “Semidefinite Programming Relaxations for Semialgebraic problems.” Math Prog 96 Ser. B, no. 2 (2003): 293-320.
    Listed reading
  • 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.
    Listed reading
  • Putinar, M. “Positive Polynomials on Compact Semi-algebraic Sets.” Indiana Univ Math J 42, no. 3 (1993): 969-984.
    Listed reading
  • Rudin, Walter. Fourier Analysis on Groups . Wiley Classics Library. New York, NY: John Wiley & Sons Inc., 1990. ISBN: 047152364X.
    Listed reading
  • Stengle, G. “Complexity Estimates for the Schmüdgen Positivstellensatz.” J Complexity 12, no. 2 (1996): 167-174.
    Listed reading
  • Boyd, S., P. Diaconis, P. A. Parrilo, and L. Xiao. “Symmetry Analysis of Reversible Markov Chains.” Internet Math 2, no. 1 (2005): 31-71.
    Listed reading
  • 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. ↗
    Listed reading
  • Fässler, Albert, and Eduard Stiefel. Group Theoretical Methods and Their Applications . Boston, MA: Birkhäuser, 1992. ISBN: 0817635270.
    Listed reading
  • 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.
    Listed reading
  • 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.
    Listed reading
  • Schrijver, A. “New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming.” IEEE Transactions on Information Theory 51, no. 8 (2005): 2859-2866.
    Listed reading
  • Serre, J.-P. Linear Representations of Finite Groups . New York, NY: Springer-Verlag, 1977. ISBN: 0387901906.
    Listed reading
  • LEC #: 22 · TOPICS: Sums of Squares Programs and Polynomial Inequalities · READINGS: Parrilo, P. A. “Sums of Squares Programs and Polynomial Inequalities.” Preprint.
    Reading assignment
  • We will use a variety of book chapters and current papers. Some of these are listed in the readings section. ↗
    Listed reading
Sources