MA 796S/OR 791K - Readings List

Conic Programming

• Arkadi Nemirovski, Advances in convex optimization: Conic programming, Preprint based on the plenary lecture given by Arkadi Nemirovski at the International Congress of Mathematicians, Madrid, 2006.

Semidefinite Programming

• Lieven Vandenberghe and Stephen Boyd, Semidefinite programming, SIAM Review, 38(1996), pp. 49-95.
• Etienne De Klerk, Aspects of Semidefinite Programming: Interior Point Methods and Selected Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002 (D.H. Hill Library - Call No: T57.74 .K59 2002).
• Michael Todd, Semidefinite optimization, Acta Numerica, 10(2001), pp. 515-560.

Second Order Cone Programming

• Farid Alizadeh and Donald Goldfarb, Second order cone programming, Mathematical Programming, 95(2003), pp. 3-51.

Duality Theory in Conic Programming

• Motakuri Ramana, An exact duality theory for semidefinite programming and its complexity implications, Mathematical Programming, 77(1997), pp. 129-162.

Complementarity, Extreme Points, and Nondegeneracy in Semidefinite Programming

• Farid Alizadeh, Jean-Pierre A. Haeberly, and Michael L. Overton, Complementarity and nondegeneracy in semidefinite programming, Mathematical Programming, 77(1997), pp. 111-128.
• Gabor Pataki, The geometry of semidefinite programming, In Handbook of Semidefinite Programming, edited by H. Wolkowicz, R. Saigal, and L. Vandenberghe, Kluwer Academic Publishers, Dordrect, The Netherlands, 2000, pp. 29-65.

Interior Point Methods for Linear and Conic Programming

• Stephen Wright, Primal-Dual Interior Point Methods (D.H. Hill Library - Call No: T57.74 .W75 1997), SIAM, Philadelphia, 1997.
• Yinyu Ye, Interior Point Algorithms: Theory and Analysis (D.H. Hill Library - Call No: QA402.5 .Y4 1997), Wiley Interscience, 1997.
• James Renegar, A Mathematical View of Interior Point Methods in Convex Optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001.

Interior Point Methods for Semidefinite Programming

• Etienne De Klerk, Aspects of Semidefinite Programming: Interior Point Methods and Selected Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002 ((D.H. Hill Library - Call No: T57.74 .K59 2002).
• Steven Benson, Yinyu Ye, and Xiong Zhang, Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM Journal on Optimization, 10(2000), pp. 443-461.
• Yin Zhang, On extending some primal-dual interior point methods for linear programming to semidefinite programming, SIAM Journal on Optimization, 8(1998), pp. 365-386.
• Renato Monteiro, First and second order methods for semidefinite programming, Mathematical Programming, 97(2003), pp. 209-244.

Applications in Combinatorial Optimization

• Etienne De Klerk, Aspects of Semidefinite Programming: Interior Point Methods and Selected Applications, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002 (D.H. Hill Library - Call No: T57.74 .K59 2002).
• Michel Goemans and David Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42(1995), pp. 1115-1145.
• David Williamson, Lecture Notes on Approximation Algorithms, IBM Research Report RC 21273, February 1999.
• Monique Laurent and Franz Rendl, Semidefinite programming and integer programming, In Handbooks in OR & MS, Volume 12, edited by K. Aardal et al., Elsevier, 2005 (D.H. Hill Library - Call No: QA402.5 .D55 2005).

Applications in Robust Optimization

• Aharon Ben Tal and Arkadi Nemirovski, Robust convex optimization, Mathematics of Operations Research, 23(1998), pp. 769-805.
• Aharon Ben Tal and Arkadi Nemirovski, Robust optimization methodology and applications, Mathematical Programming, 92(2002), pp. 453-480.
• Arkadi Nemirovski, Selected topics in robust convex optimization, Preprint based on Nemirovski's plenary lecture at ISMP 2006 in Rio de Janeiro.
• Laurent El Ghaoui and Herve Lebret, Robust solutions to least-squares problems with uncertain data, SIAM Journal on Matrix Analysis and Applications, 18(1997), pp. 1035-1064.
• Dimitris Bertsimas and Melvyn Sim, Robust discrete optimization and network flows, Mathematical Programming, 98(2004), pp. 43-71.
• Donald Goldfarb and Garud Iyengar, Robust portfolio selection problems, Mathematics of Operations Research, 28(2003), pp. 1-38.

Applications in Science and Engineering

• Stephen Boyd, Laurent El Ghaoui, Eric Feron, and Venkataraman Balakrishnan, Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, 1994 (D.H. Hill Library - Call No: QA402.3 .L489 1994).
• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004 (D.H. Hill Library - Call No: QA402.5 .B69 2004).
• Aharon Ben Tal and Arkadi Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001 (D.H. Hill Library - Call No: T57.815 .B46 2001).
• Adrian Lewis and Michael Overton, Eigenvalue optimization, Acta Numerica, 5(1996), pp. 149-190.
• Zhi-Quan Luo Applications of convex optimization in signal processing and digital communication, Mathematical Programming, 97(2003), pp. 177-207.
• Stephen Boyd, Perci Diaconis, and Lin Xiao, Fastest mixing markov chain on a graph, SIAM Review, 46(2004), pp. 667-689.
• Aharon Ben Tal, M. Kocvara, Arkadi Nemirovski, J. Zowe, Free material design via semidefinite programming: The multiload case with contact conditions, SIAM Review, 42(2000), pp. 695-715.
• David Yao, Shuzhong Zhang, and Xun Yu Zhou, Stochastic linear-quadratic control via primal-dual semidefinite programming, SIAM Review, 46(2004), pp. 87-111.
• Jun Sun, Stephen Boyd, Lin Xiao, and Perci Diaconis, The fastest mixing markov process on a graph and a connection to a maximum variance unfolding problem, SIAM Review, 48(2006), pp. 681-699.
• Anthony Man-Cho So and Yinyu Ye, A semidefinite programming approach to tensegrity theory and realizability of graphs, appeared in SODA 2006.
• Dimitris Bertsimas and Ioanna Popescu, Optimal inequalities in probability theory: A convex optimization approach, SIAM Journal on Optimization, 15(2005), pp. 780-804.
• Lieven Vandenberghe, Stephen Boyd, and Katherine Comanor, Generalized Chebyshev bounds via semidefinite programming, SIAM Review, 49(2007), pp. 52-64.
• Imre Polik and Tamas Terlaky, A survey of the S lemma, SIAM Review, 49(2007), pp. 371-418.
• Alexandre d'Aspermont, Laurent El Ghaoui, Michael Jordan, and Gert Lanckriet, A direct formulation for sparse PCA using semidefinite programming, SIAM Review, 49(2007), pp. 434-448.

Applications in Polynomial Programming

• Jean Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal of Optimization, 11(2001), pp. 796-817.
• Jean Lasserre, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM Journal of Optimization, 12(2002), pp. 756-769.
• Pablo Parrilo, Semidefinite programming relaxations for semi-algebraic problems, Mathematical Programming, 96(2003), pp. 293-320.
• Etienne De Klerk and Dima Pasechnik, Approximation of the stability number of a graph via copositive programming, SIAM Journal on Optimization, 12(2002), pp. 875-892.
• Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu, Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM Journal on Optimization, 17(2006), pp. 218-242.
• Jean Lasserre, Convergent SDP relaxations in polynomial optimization with sparsity, Technical Report #05-612, LAAS, Toulouse, France, 2005.
• Monique Laurent, Moment matrices and optimization over polynomials - A survey on selected topics, Preprint, September 2005.
• Didier Henrion and Jean Lasserre, Detecting global optimality and extracting solutions in Gloptipoly, In Positive Polynomials in Control, edited by D. Henrion and A. Garulli, Lecture Notes in Control and Information Science, Volume 312, Springer Verlag, Berlin, 2005, pp. 293-310 (D.H. Hill Library - Call No: QA402.3 .P67 2005).
• Didier Henrion and Jean Lasserre, Gloptipoly: Global optimization over polynomials with Matlab and SeDuMi, ACM Transactions on Mathematical Software, 29(2003), pp. 165-194.
• Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu, SparsePOP: A sparse semidefinite programming relaxation of polynomial optimization problems, Research Report B-414, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Tehnology, Oh-Okayama, Meguro 152-8552, Tokyo, Japan, 2005.