Prerequisites: There are no graduate-level prerequisites for this course. In particular, it is independent of MAT 258A "Numerical Optimization" and MAT 258B "Discrete and Mixed Integer Optimization". If you want to learn the basics of polyhedral theory and linear optimization thoroughly (we do review everything as needed), I recommend taking or auditing class MAT 168 (Prof. A. Fannjiang, MWF 3:10-4) concurrently.Course Time: MW 10:00–11:25. Room: 2112 MSB Instructor: Matthias Köppe Office hours: MW after class (11:30-12) or by appointment. Announcements and Assignments: I will be using SmartSite to announce reading and homework, and distribute grades. Auditors: Please let me know your Kerberos id, so I can give you access to SmartSite. Grading: This class is intended to expose graduate students to current research topics in optimization. Every registered student is required to present a topic in class and produce a corresponding write-up. The topic could be a paper from the recent research literature; there are also opportunities for research projects. Suggestions for topics are made in class and via announcements on SmartSite. Topics: We study modern techniques of convex and mixed integer optimization and their applications. The overarching theme linking these cutting-edge topics: Structure of projections of high-dimensional convex sets.Tentative schedule:Weeks 1–4: Extended formulations (linear and semidefinite) for combinatorial optimization problems Guest lecture (Monday 4/14, 10:00) and seminar talk (Monday 4/14 12:10) – Dr. Thomas Rothvoss (U. Washington), The matching polytope has exponential extension complexity Literature: [EF1] OPTIMA 85, Mathematical Optimization Society Newsletter, issue 85, April 2011. http://www.mathopt.org/Optima-Issues/optima85.pdf [EF2] M. Conforti, G. Cornuejols, and G. Zambelli, Extended Formulations in Combinatorial Optimization, Annals of Operations Research 204 (2013) 97-143. doi:10.1007/s10479-012-1269-0 (via UC Library). Survey with many references.[EF3] V. Kaibel, S. Weltge, Lower Bounds on the Sizes of Integer Programs Without Additional Variables, arXiv:1311.3255 [math.CO] [EF4] P.-F. Tsai, Tight Flow-Based Formulations for the Asymmetric Traveling Salesman Problem and Their Applications to some Scheduling Problems, Dissertation, Virginia Tech, 2006, http://scholar.lib.vt.edu/theses/available/etd-05232006-195259/unrestricted/dissertation_peifang_tsai.pdf [EF5] F. Vanderbeck, L. Wolsey, Reformulation and Decomposition of Integer Programs, in: 50 Years of Integer Programming 1958–2008, doi:10.1007/978-3-540-68279-0_13 (via UC Library) [EF6] A. Saxena, P. Bonami, J. Lee, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, Math. Program. 130 (2011), 359–413, doi:10.1007/s10107-010-0340-3 (via UC Library) [EF7] S. Iwata, N. Kamiyama, N. Katoh, S. Kijima, Y. Okamoto, Extended Formulations for Sparsity Matroids, arXiv:1403.7272 [math.CO] [EF8] G. Braun, S. Pokutta, The matching polytope does not admit fully-polynomial size relaxation schemes, arXiv:1403.6710 [cs.CC] [EF9] V. Kaibel, S. Weltge, A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially, arXiv:1307.3543 [math.CO]Weeks 4–7: Geometry of compressive sensing (Tao, Donoho, Candès, ...) Guest lecture (Monday 5/5, 10:00) – Dr. Thomas Strohmer (UC Davis, Mathematics) Literature: The lecture will be based on the recent book [CS1]. See www.compressedsensing.com for an extensive bibliography. [CS1] S. Foucart, H. Rauhut: A mathematical introduction to compressive sensing, Birkhäuser, 2013. http://link.springer.com/book/10.1007%2F978-0-8176-4948-7 Weeks 7–9: Infinite-dimensional relaxations of mixed-integer optimization problems (Gomory, Johnson, ...) Literature: [IR1] A. Basu, M. Conforti, G. Cornuéjols, and G. Zambelli, A counterexample to a conjecture of Gomory and Johnson, Mathematical Programming Ser. A 133 (2012), 25–38. [IR2] A. Basu, R. Hildebrand, and M. Köppe, Equivariant perturbation in Gomory and Johnson’s infinite group problem. I. The one-dimensional case, eprint arXiv:1206.2079 [math.OC], 2012. [IR3] A. Basu, R. Hildebrand, M. Köppe, and M. Molinaro, A (k + 1)-slope theorem for the k-dimensional infinite group relaxation, SIAM Journal on Optimization 23 (2013), no. 2, 1021–1040, doi:10.1137/110848608. [IR4] M. Conforti, G. Cornuéjols, and G. Zambelli, Corner polyhedra and intersection cuts, Surveys in Operations Research and Management Science 16 (2011), 105–120. [IR5] J.-P. P. Richard and S. S. Dey, The group-theoretic approach in mixed integer programming, 50 Years of Integer Programming 1958–2008 (M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, eds.), Springer Berlin Heidelberg, 2010, pp. 727–801, doi:10.1007/978-3-540-68279-0_19, ISBN 978-3-540-68274-5. Week 10: Graver basis techniques for exponential-size integer optimization problems (Onn, ...) We focus on the convex integer maximization case, based on projections and controlled edge directions [GB1, Chapters 2, 3.3.3], [GB3]. The state of the art in Graver-based convex integer minimization can be found in [GB2, Chapters 3–4]. Some open problems in this area (S. Onn). Literature: [GB1] Shmuel Onn, Nonlinear Discrete Optimization, Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010. e-book (free). [GB2] Jesús A. De Loera, Raymond Hemmecke, and Matthias Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization, SIAM, 2012. e-book (via UC Library). [GB3] Michal Melamed, Shmuel Onn, Convex integer optimization by constantly many linear counterparts, Linear Algebra and its Applications, 2014, doi: 10.1016/j.laa.2014.01.007 (via UC Library). Background reading: On Combinatorial Optimization (a subfield of discrete optimization).
On Integer Optimization:
On Mixed-Integer Nonlinear Optimization and Global Optimization:
For a background on linear optimization:Most textbooks on linear optimization give sufficient background. Here are two examples:
Further resources:
Software
|