Convex Optimization

  • Lecturer: Prof. Stefania Petra
  • Exercises: Stefania Petra, Matthias Zisler
  • Format:
    • No in-person lecture.
    • Short videos that explain each subtopic from a top-down viewpoint.
    • Detailed lecture notes that you read on your own.
    • Exercise sheets you work on your own. Solutions will be discussed in Zoom.
  • Language: English
  • SWS: 4
  • ECTS: 6 + 2
  • Lecture Id: MM35, Spezialisierungsmodul Numerik und Optimierung
  • Supplementary Practical: For participating in the optional Programming Project in the semester break you get two extra credits.
  • Registration: Please register in Müsli and Moodle.
  • Prior Knowledge: Required: Lineare Algebra and Analysis

Content

The lecture gives an introduction into the field of convex optimization and details the most important numerical methods for the solution of convex optimization problems.

  • Preliminaries: Convex sets, convex functions, convex optimization problems (LPs, QPs, SOCPs, SDPs)
  • Theory: Separation theorems, duality, subdifferential calculus, existence and optimality
  • Algorithms: Gradient-based methods for smooth optimization, proximal-point and splitting methods
  • Applications: Convex models in mathematical imaging

}

Lecture Notes

Literature

  • R.T. Rockafellar, R.J.-B. Wets, Variational Analysis, Springer, 2004
  • R. Rockafellar. Convex Analysis. Princeton Univ. Press, 1970
  • A. Auslender, M. Teboulle, Asymptotic Cones and Functions in Optimization and Variational Inequalities, Springer, 2003
  • S. Boyd, L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004
  • A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization, SIAM, 2001
  • Y. Nesterov. Introductory Lectures on Convex Optimization. Kluwer Acad. Publ., 2004
  • H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2nd edition, 2017

https://us02web.zoom.us/j/87013567712?pwd=LzNBejNLR01KaHlZUDl4eHVIRjlRdz09

Meeting ID: 870 1356 7712 Passcode: 488223

Exercises

You are supposed to solve at least 50% of the numerical exercises (Matlab, Pyhton) in order to participate in the exam. There will be no points, only “OK”, “Not OK” or “ ” if nothing was handed in

Introduction to Matlab and CVX

CVX and Python

Solutions to Practical Exercises

Software Practical: Convex Optimization

The software practical is suited for students attending the lecture on Convex Optimization that additionally wish to apply the algorithms and concepts to concrete examples in order to get a deeper understanding.

Registration: in the lecture, or mail to Stefania Petra.

Assignment

First choose a paper and a concrete problem instance like denoising, deblurring, segmentation, reconstruction (Radon, MRI), optimal transport. Your task is to implement the algorithm in MATLAB or Python. Write a small report with 5-8 pages to describe the algorithm, convergence properties and your problem setup along with the results of your experiments. Please use the latex template files.

You can hand in your code+report at the end of the this term.

Imaging Problems

Paper

Note, if a paper list of papers is already taken, you can ask for a similar one.

  • A fast iterative shrinkage-thresholding algorithm for linear inverse problems by Beck, Amir and Teboulle, Marc, SIAM Journal on Imaging Sciences, 2009, paper
  • Iterative Bregman projections for regularized transportation problems by Benamou, Jean-David and Carlier, Guillaume and Cuturi, Marco and Nenna, Luca and Peyre, Gabriel, SIAM Journal on Scientific Computing, 2015 paper
  • A convex approach to minimal partitions by Chambolle, Antonin and Cremers, Daniel and Pock, Thomas, SIAM Journal on Imaging Sciences, 2012, paper
  • A first-order primal-dual algorithm for convex problems with applications to imaging by Chambolle and Pock, Journal of mathematical imaging and vision, 2011, paper
  • Improving “Fast Iterative Shrinkage-Thresholding Algorithm”: Faster, Smarter and Greedier by Liang, Jingwei and Schönlieb, Carola-Bibiane, arXiv 2019, paper
  • Fast alternating direction optimization methods by Goldstein, Tom and O'Donoghue, Brendan and Setzer, Simon and Baraniuk, Richard, SIAM Journal on Imaging Sciences, 2014, paper
  • The primal-dual hybrid gradient method for semiconvex splittings by Möllenhoff, Thomas and Strekalovskiy, Evgeny and Moeller, Michael and Cremers, Daniel, SIAM Journal on Imaging Sciences, 2015, paper
  • Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm by Sidky, Emil Y and J{\o}rgensen, Jakob H and Pan, Xiaochuan, Physics in medicine and biology, 2012, paper
  • Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems by Beck and Teboulle, IEEE Transactions on Image Processing, 2009, paper
  • Bregman iterative algorithms for l1-Minimization with applications to Compressed Sensing by Yin, Wotao and Osher, Stanley and Goldfarb, Donald and Darbon, Jerome, SIAM Journal on Imaging Sciences, 2008, paper
Copyright 2013–2024 IPA-Group, Legal Notice, Privacy Policy