Discrete and Continuous Optimization (summer 2017)

Time and Place

• Lecture: Thursdays 14:00 to 15:30 in S9

• Tutorial: Thursdays 15:40 to 17:10 in S6

Office hours:

By email appointment.

Topics

1. Introduction to mathematical optimization (> 13.4.2017)

2. Unconstrained optimization

   • First and second order optimality conditions

   • Least square method (< 13.4.2017)

3. Convexity (> 20.4.2017)

   • Convex sets

   • Convex Functions (< 20.4.2017)

   • First and second order characterizations (> 28.4.2017)

4. Convex Optimization

   • Basic properties (< 28.4.2017)

   • Quadratic programming (> 4.5.2017)

   • Cone programming

     • Duality (< 4.5.2017)

     • Cone quadratic programming (> 11.5.2017)

     • Semidefinite programming (< 11.5.2017)

   • Computational complexity

     • The good case: ellipsoid method (> 18.5.2017)

     • The bad case: copositive programming

5. Karush-Kuhn-Tucker optimality conditions

   • Equation case

   • General case (< 18.5.2017)

6. Algorithms (> 25.5.2017)

   • Line search: Armijo rule

   • Unconstrained problems: Gradient method

   • Constrained problems

     • Methods of feasible directions

     • Penalty and barrier methods (< 25.5.2017)

Literature

1. S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

2. D. Luenberger and Ye. Linear and Nonlinear Programming. Springer, New York, third edition, 2008.

3. M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming. Theory and Algorithms. 3rd ed. John Wiley & Sons., NJ, 2006.

Other links

• First half of the lecture held by Hans Raj Tiwary

• F. Augugliaro, A.P. Schoellig, and R. D’Andrea, Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach, EEE/RSJ International Conference on Intelligent Robots and Systems, 2012: pp. 1917–1922.

  • [Youtube video]