# 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.**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

- week 1, Source Problems will be discussed on 04.11, 11:15-12:45 via Zoom Slides
- week 2, Examples of Convex Sets: Hyperplanes, Linear Subspaces, Affine and Convex Hulls, Simplices will be presented
**offline**on Wednesday 11.11 Slides Video - week 3, Examples of Convex Sets: Polyhedral Sets, Cones will be presented
**offline**on Wednesday 18.11 Slides Video - week 10, Nonexpansive Operators
- week 11, Splitting Methods

### 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

### Link for Tutorial

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

- week 3, Sheet 2 will be discussed on Thur. 19.11, 14:15-15:45, via Zoom, Data for exercise 2.5 Matlab Data Python Data Solutions
**update** - week 9, Sheet 8 will be discussed on Thur. 21.01, 14:15-15:45, via Zoom Data Solutions Solution in Mathematica to practical exercise
- week 14, mock exam solutions will be discussed on Thur. 25.02, 14:15-15:45, via Zoom and will not be uploaded here!

### 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