Seminar

http://events.berkeley.edu/index.php/calendar/sn/math.html?event_ID=114447

Lecture 3: Mathematics and Computation (through the lens of one problem and one algorithm). Proving Analytic Inequalities.

The celebrated Brascamp-Lieb (BL) inequalities, and their reverse form of Barthe, is a powerful framework which unifies and generalizes many important inequalities in analysis, convex geometry and information theory.

I will exemplify BL inequalities, building to the general set-up. I will describe the structural theory that characterizes existence and optimality of these inequalities in terms of their description (called BL-data). But can one efficiently compute existence and optimality from given BL-data?

I will describe a recent polynomial time algorithm for these problems, based on a natural alternate minimizaion approach and operator scaling analysis discussed in the first lecture. It also supplies alternative proofs to some of the structural results.

This algorithm may be viewed (via the structural theory) in two ways that make it potentially exciting for new applications in optimization. First, it efficiently solves a large natural class of non-convex programs. Second, it efficiently solves a large natural class of linear programs with exponentially many inequalities.

This lecture is self-contained, independent of the previous two. No special background is assumed. Most of this presentation is based on the paper https://arxiv.org/abs/1607.06711