de | en

Convex Optimization

Modul EI74351

Dieses Modul wird durch Fakultät für Elektrotechnik und Informationstechnik bereitgestellt.

Diese Modulbeschreibung enthält neben den eigentlichen Beschreibungen der Inhalte, Lernergebnisse, Lehr- und Lernmethoden und Prüfungsformen auch Verweise auf die aktuellen Lehrveranstaltungen und Termine für die Modulprüfung in den jeweiligen Abschnitten.

Basisdaten

EI74351 ist ein Semestermodul in Englisch auf Master-Niveau das im Wintersemester angeboten wird.

Das Modul ist Bestandteil der folgenden Kataloge in den Studienangeboten der Physik.

  • Allgemeiner Katalog der nichtphysikalischen Wahlfächer
GesamtaufwandPräsenzveranstaltungenUmfang (ECTS)
180 h 60 h 6 CP

Inhalte, Lernergebnisse und Voraussetzungen

Inhalt

Introduction: basic definitions and fundamentals, problem statement.
Convex analysis: convex sets, convex functions.
Linear programming: extremal points and directions, simplex algorithm.
Optimality conditions: Fritz John conditions, Karush-Kuhn-Tucker conditions, constraint qualifications.
Lagrangian duality: duality theorems.
Algorithms: general concept, unconstrained optimization, constrained optimization.
Solutions for the dual problem: sub gradient method, cutting plane algorithm.
Interior-point method: barrier functions, IP algorithm.
Applications: problems form multi-user information theory, resource allocation, parameter optimization in layered and distributed communication systems.

Lernergebnisse

After successfully passing the module, the students are able to characterize given mathematical optimization problems in terms of convex analysis on convex sets and convex functions and to derive optimality conditions related to F. John (FJ) and W. Karush, H. W. Kuhn and A. W. Tucker (KKT) for equality and inequality constraints, including the discussion of qualification constraints. Furthermore, the students are able to derive and to apply the weak and strong duality theorem and the saddle point theorem for the analysis and the appropriate reformulation of given optimization problems into prior and dual optimization problems and their related primal reconstruction algorithms. The student will be able to derive and apply gradient and subgradient based optimization methods and to take into account respective algorithms for a step size control. The students are also able to derive and apply the cutting plane method to reformulate convex optimization problems into a series of linear master problems. Finally, the students are able to derive and to apply a variety of state-of-the art algorithms, namely the simplex algorithm for linear programs, the gradient descent and the Newton algorithms for convex optimization problems, the Armijo-Goldstein rule for step-size control, and a few basis versions of interior point solvers.

Voraussetzungen

Linear Algebra and Calculus.

Lehrveranstaltungen, Lern- und Lehrmethoden und Literaturhinweise

Lehrveranstaltungen und Termine

ArtSWSTitelDozent(en)Termine
VI 4 Convex Optimization Mi, 13:15–14:45, 0101.Z1.070
Fr, 11:30–13:00, 0101.Z1.095

Lern- und Lehrmethoden

Learning method:
In addition to the individual methods of the students, consolidated knowledge is aspired by repeated lessons in exercises and tutorials.
Teaching method:
During the lectures, students are instructed in a teacher-centric style. The exercises are held in a student-centenered way.

Medienformen

The following kinds of media are used:
- Presentations
- Lecture notes
- Exercises with solutions as download.

Literatur

The following literature is recommended:
- M. S. Bazare, H. D. Serail, and C. M. Shetty. Nonlinear Programming: Theory and Algorithms. Wiley, 2006.
- D. Bertsekas and A. Nedic. Convex Analysis and Optimization. Athena Scientific, 2003.
- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge, 2004.

Modulprüfung

Beschreibung der Prüfungs- und Studienleistungen

Written examination, 90 min (evaluation of basic theoretical concepts presented in the lecture and tutorials). Up to 20% of the examination can be conducted in the form of multiple choice questions.With maximally 5 sheets of A4 paper as helping material, the students formulate, classify, and solve convex optimization problems. They answer comprehension questions and are able to discuss the different algorithms to obtain the solutions.

Wiederholbarkeit

Eine Wiederholungsmöglichkeit wird im Folgesemester angeboten.

Nach oben