Courses:

Algebraic Techniques and Semidefinite Optimization >> Content Detail



Study Materials



Readings

Amazon logo 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



LEC #TOPICSREADINGS
1Introduction

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.
2PSD 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.
3Binary 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.
4Review: 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.
5Univariate 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.
6Resultants

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.
7Hyperbolic 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.
8SDP 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.
9Binomial 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.
10Nonegativity 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.
11SOS 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.
12Recovering 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.
13Polynomial 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.
14Monomial 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.
15Zero-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.
16Generalizing 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)
17Infeasibility 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)
18Quantifier 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.
19Certificates

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.
20Positive 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.
21Groups 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.
22Sums of Squares Programs and Polynomial InequalitiesParrilo, P. A. "Sums of Squares Programs and Polynomial Inequalities." Preprint.

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.