Computational Convexity - Optimal Containment (MA5206) lecture

 

lecturer:	Rene Brandenberg
learning assistant and organization:	Rene Brandenberg

News

Dates of lectures/exercise classes and office hours

Lecture notes

Tutorials

Exercise sheets

Literature

FAQ

News

• (2012-05-10) Problem sheet 3 corrected!
• (2012-05-07) Please notice that we have changed the starting times of the lectures again.
• (2012-05-03) Next thursday, 10th of may is again a normal lecture. The excercise class will take place at monday, 14th.
• (2012-04-18) This week there will be a normal lecture instead of an excercise class at thursday 8.30. In the two weeks after pentecost I'm not at TU, so that I would miss an excercise class and two lectures. One of the lectures is replaced by the lecture this thursday. The others (excercise and lecture) will most probably be taught by Stefan König. Details will be given later (here and within the lectures)

Dates of lectures/exercise classes and office hours

type	day	time	room	starting date	closing date	teacher
lecture	monday	12:30 a.m. to 2:00 p.m.	02.08.011	april 16th	july 16th	René Brandenberg
lecture	tuesday	12:15 a.m. to 1:45 p.m.	02.08.011	april 17th	july 17th	René Brandenberg
excercise	thursday	8:30 a.m. to 10:00 a.m.	02.08.011	april 19th	july 19th	René Brandenberg

Lecture Notes

Datum	Datei	Themen
2012-04-16	pdf	slides of the introductory talk
2012-04-17	pdf	lecture1: basics from convex analysis/geometry, part 1
2012-04-17	pdf	lecture2: basics from convex analysis/geometry, part 2
2012-04-23	pdf	lecture3: complexity theory: basics
2012-04-24	pdf	lecture4: complexity theory: NP-hardness
2012-04-30	pdf	lecture5: complexity theory: some reductions
2012-05-07	pdf	lecture6: complexity theory: optimization problems
2012-05-08	pdf	lecture7: norm maximization
2012-05-10	pdf	lecture8: mcp-hom, foundations, part 1
2012-05-15	pdf	lecture9: mcp-hom, foundations, part 2

Excercises

Problem Sheet	Excercise Class	Solutions
Sheet 1	2012-04-26	Sheet 1
Sheet 2	2012-05-03	Sheet 2
Sheet 3	2012-05-14	Sheet 3
Sheet 4	2012-05-22

Literature

In General (Convex Analysis, Optimization, and Complexity Theory)

• Gritzmann. Vieweg Studium, Nr.90, Optimierung (german, not yet available)

On Convex Analysis and Convex Geometry

• Rockafellar. Convex Analysis. Princeton University Press, 1996.
• Schneider. Convex Bodies: The Brunn-Minkowski Theory, 2008.
• Ziegler. Lectures on Polytopes, 2008.

On Complexity Theory

• Garey, Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness,1979.
• Papadimitriou. Computational Complexity, 1994.
• Wegner. Complexity Theory: Exploring the Limits of Efficient Algorithms, 2005.

Special Papers On Norm Maximization

• Brieden. Geometric optimization problems likely not contained in APX. Discrete Comput. Geom., 28:201-209, 2002.
• Brieden, Gritzmann, Kannan, Klee, Lovasz, Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48:63-105, 2001.
• Brieden, Gritzmann, Klee. Inapproximability of some geometric and quadratic optimization problems. In P.M. Pardalos, editor, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, pages 96-115. Kluwer, 2000.

Special Papers On Radii And Containment

• Gritzmann, Klee. Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280, 1992.
• Grünbaum. Measures of symmetry for convex sets. Proc. Symp. Pure Math., 1 (Convexity), pages 271-284, 1963.

What is Computational Convexity?

Also sometimes seen as some part of Computational Geometry, the main ideas and techniques of Computational Convexity have their origin in fields like Linear Programming, Polyhedral Combinatorics, and Algorithmic Theory of Convex Bodies, all subsummable backwardly under the notion of Computational Convexity.

Two focuses describe the main difference betweeen Computational Convexity and typical Computational Geometry: First, instead of the typical euclidean geometry often general normed spaces are considered, and secondly, the dimension is part of the algorithmic input, as, e.g., typical in Linear Programming.

What is Optimal Containment?

In a basic Optimal Containment problem we want to compute (or approximate) extremal representatives within a given family of convex bodies , contained in or containing a fixed set. For example, given a set of points one wants to find the smallest -dimensional cube containing it, where smallest means the scaling factor (the dilatation) and the considered family is the orbit of the standard unit cube under homothetics (dilatation and translation) or similarities (allowing also rotations).

A special case of Optimal Containment are radii of convex sets. The computation of the four basic radii (inner- and outer radius, width and diameter) is a classical problem in convex geometry. Generalizing and unifying these, several series of succesive inner and outer radii of convex bodies maybe considered. E.g. the radius of a largest -dimensional ball contained in a given set connects diameter (1-dimensional ball) and inradius (d-dimensional) ball.

An optimal embedding for maximizing the radius of a disc (a 2-dimensional ball) in a 3-dimensional cube, an inner 2-radius of that cube.

Who is adressed by this lecture?

This lecture is mainly adressed to students within the masters in mathematics and mathematics of operations research. However, all other studentents having a good knowledge in Convex Analysis / Convex Geometry and Linear Optimization are welcome, too. A basic knowledge in complexity and discrete optimization may be of some value but not neccesary.