Open Collections

Conjugate of some rational functions and convex envelope of quadratic functions over a polytope

University of British Columbia

Computing the convex envelope or biconjugate is the core operation that bridges the domain of nonconvex analysis with convex analysis. For a bivariate PLQ function de ned over a polytope, we start with computing the convex envelope of each piece. This convex envelope is characterized by a polyhedral subdivision such that over each member of the subdivision, it has an implicitly de ned rational form(square of a linear function over a linear function). Computing this convex envelope involves solving an exponential number of subproblems which, in turn, leads to an exponential time algorithm. After that, we compute the conjugate of each such rational function de- ned over a polytope. It is observed that the conjugate has a parabolic subdivision such that over each member of its subdivision, it has an implicitly de ned fractional form(linear function over the square root of a linear function). This computation of the conjugate is performed with a worst-case linear time complexity algorithm. Finally, some directions and insights about computing the maximum of all the conjugates of each piece of a PLQ function and then the conjugate of that to obtain the biconjugate are provided as conjectures for future work.

Text

2019-01-14

Attribution-NonCommercial-NoDerivatives 4.0 International

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

Computer Science

University of British Columbia

UBCO

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