Computing the conjugate of convex piecewise linear-quadratic bivariate functions

• 成果类型: Article
• 署名作者: Gardiner, Bryan; Lucet, Yves
• 署名单位: University of British Columbia; University of British Columbia Okanagan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0666-8
• 发表日期: 2013
• 页码: 161-184
• 关键词: legendre-fenchel transform; proximal average; computation

摘要

We present a new algorithm to compute the Legendre-Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case complexity. We present the algorithm, and illustrate it with numerical examples. We proceed to build a toolbox for convex bivariate PLQ functions by implementing the addition, and scalar multiplication operations. Finally, we compose these operators to compute classical convex analysis operators such as the Moreau envelope, and the proximal average.