LANS Informal Seminar: Yves Lucet

Seminar Title: Convexity Detection, Computational Convex Analysis, Multi-fidelity Surrogate for Road Design
Speaker: Yves Lucet, Professor of Computer Science, University of British Columbia – Okanagan

Date/Time: 2019-10-09 10:30
Location: Bldg. 250, Rm. 4301

Description:
The talk is a potpourri of my recent research interests with 3 independent parts.
First, I will describe how to check whether a piecewise function is convex. I will present an algorithm to detect convexity in linear time with respect to the number of edges of the partition defining the domain. The results have interesting applications in optimization problems under convexity constraints.
The second part will focus on computational convex analysis, e.g. how to compute the biconjugate (aka convex envelope) and conjugate for special classes of functions. Computing the closed convex envelope or biconjugate is the core operation that bridges the domain of nonconvex with convex analysis. We focus here on computing the conjugate of a
bivariate piecewise quadratic function defined over a polytope. The conjugate has a parabolic subdivision such that over each member of its subdivision, it has a fractional form (linear function over square root of a linear function). This computation of the conjugate is performed with a worst-case linear time complexity algorithm. I will mention open questions on building scalable data structures based on generalized Voronoi diagrams.
In the 3rd part, I will discuss the road design problem and our recent work on multi-fidelity surrogate. The goal is to speed up the computation of the lower level problem in a bilevel optimization. The surrogate built has 2 interesting properties: it is very precise, and it has several levels of approximations. The results lead to very significant speedups with potential for much more.