Open Collections

Karmarkar, Tanmaya Narendra

University of British Columbia

Computing the minima of a convex function is much easier than computing the same for a nonconvex function. Every nonconvex function has the same minimum as its convex envelope and the minima of the nonconvex function are contained in the set of minima of its convex envelope. We compute the conjugate of a bivariate piecewise linear-quadratic (PLQ) function as a first step toward the computation of the convex envelope. Our algorithm starts with computing the convex envelope of each piece obtaining a rational function defined over a polyhedral subdivision. Then we compute the conjugate of each of those pieces and obtain a fractional form defined over a parabolic subdivision. The last step is to compute the maximum of all those functions to obtain the conjugate of the original piecewise linear-quadratic function as a piecewise function defined on a parabolic subdivision. Our implementation in MATLAB uses symbolic computation and rational numbers to avoid any floating-point errors. We have developed the theory to compute the conjugate by computing the maximum of the conjugates corresponding to all the pieces and have implemented the code to compute the convex envelope, conjugate of each piece and the conjugate of the PLQ function.

Text

2024-07-05

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/88581

Computer Science

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/