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. First, we compute the convex envelope of each piece, which is characterized by a polyhedral subdivision such that over each member of the subdivision, it has a rational form (square of a linear function over a linear function). Then we compute the conjugate of all such rational functions. It is observed that 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.

Our results are an important step toward computing the conjugate of a piecewise quadratic function, and further in obtaining explicit formulas for the convex envelope of piecewise rational functions.

This is joint work with MSc D. Kumar.

Bio: Dr. Yves Lucet received his PhD in convex analysis and optimization in 1997 from Universite de Toulouse III, France. He moved to Canada for a postdoctoral fellowship between Simon Fraser University, University of Edmonton, and University of Victoria. In 2002, he accepted a faculty position in what became the Okanagan campus of the University of British Columbia at which he is a professor of computer science. He has been pursuing his research in computational convex analysis with recent focus on conjugate, biconjugate and convexity detection algorithms. He is also interested in modeling and optimization, and has a long running project with industry-sponsored funding on the optimization of road designs.

Free entrance.
Welcome to everyone!