Convex optimization

MGT-418 / 5 credits

Teacher: Kuhn Daniel

Language: English

Summary

This course introduces the theory and application of modern convex optimization from an engineering perspective.

Content

Convex optimization is a fundamental branch of applied mathematics that has applications in almost all areas of engineering, the basic sciences and economics. For example, it is not possible to fully understand support vector machines in statistical learning, nodal pricing in electricity markets, the fundamental welfare theorems in economics, or Nash equilibria in two-player zero-sum games without understanding the duality theory of convex optimization.

The course primarily focuses on techniques for formulating decision problems as convex optimization models that can be solved with existing software tools. The exact formulation of an optimization model often determines whether the model can be solved within seconds or only within days, and whether it can be solved for ten variables or up to 10^6 variables. The course does not address optimization algorithms but covers the theory that is necessary to follow advanced courses on algorithm design such as EE-556: Mathematics of data: from theory to computation.

 

Tentative Course Outline:

Week 1: Introduction / Convex Sets

Week 2: Convex Sets / Convex Functions

Week 3: Convex Functions / Convex Optimization Problems

Week 4: Convex Optimization Problems

Week 5: Introduction to Duality Theory

Week 6: Optimality Conditions / Separation Theorems

Week 7: Strong Duality

Week 8: Optimization in Statistics and Machine Learning

Week 9: Optimization in Statistics and Machine Learning

Week 10: Convexifying Nonconvex Problems

Week 11: Convexifying Nonconvex Problems

Week 12: Robust Optimization

Week 13: Robust Optimization

Week 14: Stochastic Programming

Learning Prerequisites

Required courses

Students are assumed to have good knowledge of linear algebra and analysis.

Important concepts to start the course

Some familiarity with linear programming or other optimization paradigms is useful but not necessary. Students are expected to be familiar with PYTHON.

Learning Outcomes

By the end of the course, the student must be able to:

  • Model and solve decision problems affected by uncertainty
  • Formalize decision problems in engineering and economics as mathematical optimization models
  • Solve the resulting models with off-the-shelf optimization software and interpret the results
  • Assess / Evaluate the computational complexity of different classes of optimization problems and use modeling techniques to make specific optimization problems more tractable

Transversal skills

  • Communicate effectively with professionals from other disciplines.
  • Use both general and domain specific IT resources and tools
  • Assess one's own level of skill acquisition, and plan their on-going learning goals.
  • Write a scientific or technical report.

Teaching methods

Classical formal teaching interlaced with practical exercices and computational courseworks.

Assessment methods

30% Midterm exam

20% Computational projects

50% Final exam

Supervision

Office hours Yes
Assistants Yes
Forum Yes

Resources

Bibliography

  • Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004
  • Aharon Ben-Tal and Arkadi Nemirovski, Lectures on Modern Convex Optimization, SIAM, 2001
  • Yurii Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2004
  • David Luenberger and Yinyu Ye, Linear and Nonlinear Programming, Springer, 2008
  • R. Tyrrell Rockafellar, Conjugate Duality and Optimization, SIAM, 1974
  • Joshua A. Taylor, Convex Optimization of Power Systems, Cambridge University Press, 2015

Ressources en bibliothèque

Moodle Link

In the programs

  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional
  • Exam form: Written (winter session)
  • Subject examined: Convex optimization
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 2 Hour(s) per week x 14 weeks
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.