Skip to main content
Seminar | Mathematics and Computer Science Division

Convexity Detection, Computational Convex Analysis, and Multi-Fidelity Surrogate for Road Design

LANS Informal Seminar

Abstract: The talk is a potpourri of my recent research interests with threeindependent 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 (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 third part, I will discuss the road design problem and our recent work on a multi-fidelity surrogate. The goal is to speed up the computation of the lower level problem in a bilevel optimization. The surrogate built has two interesting properties: it is very precise and it has several level of approximations. The results lead to very significant speedups with potential for much more.

This seminar will be streamed.