Topic: Optimization problems without convexity properties appear in many areas of science, engineering, operations research, and mathematics. The standard methods of numerical optimization (interior point, SQP, ...) are local in nature: Even if the method has "global convergence", this just means it converges to *some* point, in the best case a local optimum. No guarantees can be made how far the local optimum is off from the true, global optimum. In the past few years, techniques for global optimization have been developed, which give provably optimal solutions, or at least provable approximation guarantees. We study the mathematics of these techniques, both for continuous and integer and mixed-integer problems. Target audience: Target audience are students who took 258A and/or 258B during 2009/10, and students who took the Numerical Optimization course taught in Engineering in Fall 2010, or another course in optimization. I will make the course sufficiently self-contained so that it is also accessible to students who did not take these courses. Room: MSB 3106 Time/Location: WF 11-12.30 Please let me know as soon as possible if this conflicts with another course you're taking. We can still try to find a better time! Detailed list of topics: We will study a selection of topics from the following. convexification, spatial branching, domain reduction, nonlinear cutting planes techniques, reformulation-linearization technique, algorithms and software, polynomial optimization, method of moments, generating function methods for nonlinear mixed-integer optimization, complexity analysis, nonlinear combinatorial optimization problems. The detailed syllabus will be developed dynamically. Textbook: None. I will teach from my own preliminary notes. Additional reading will be announced. Part of the grade of the course will be the production of preliminary lecture notes for the course in LaTeX. Grading: 50% Notetaking, 50% Homework/Project. |