TY - THES
AU - Trienis, Michael Joseph
PY - 2007
TI - Computational convex analysis : from continuous deformation to finite convex integration
KW - Thesis/Dissertation
LA - eng
M3 - Text
AB - After introducing concepts from convex analysis, we study how to continuously transform one convex
function into another. A natural choice is the arithmetic average, as it is pointwise continuous;
however, this choice fails to average functions with different domains. On the contrary, the proximal
average is not only continuous (in the epi-topology) but can actually average functions with
disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic
average) but also inherits smoothness and differentiability (unlike the arithmetic average).
Then we introduce a computational framework for computer-aided convex analysis. Motivated
by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is
closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope.
As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex
PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit
convex hull algorithm.
Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone
operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions
[5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12,
p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can
be formulated as shortest path problems.
N2 - After introducing concepts from convex analysis, we study how to continuously transform one convex
function into another. A natural choice is the arithmetic average, as it is pointwise continuous;
however, this choice fails to average functions with different domains. On the contrary, the proximal
average is not only continuous (in the epi-topology) but can actually average functions with
disjoint domains. In fact, the proximal average not only inherits strict convexity (like the arithmetic
average) but also inherits smoothness and differentiability (unlike the arithmetic average).
Then we introduce a computational framework for computer-aided convex analysis. Motivated
by the proximal average, we notice that the class of piecewise linear-quadratic (PLQ) functions is
closed under (positive) scalar multiplication, addition, Fenchel conjugation, and Moreau envelope.
As a result, the PLQ framework gives rise to linear-time and linear-space algorithms for convex
PLQ functions. We extend this framework to nonconvex PLQ functions and present an explicit
convex hull algorithm.
Finally, we discuss a method to find primal-dual symmetric antiderivatives from cyclically monotone
operators. As these antiderivatives depend on the minimal and maximal Rockafellar functions
[5, Theorem 3.5, Corollary 3.10], it turns out that the minimal and maximal function in [12,
p.132,p.136] are indeed the same functions. Algorithms used to compute these antiderivatives can
be formulated as shortest path problems.
UR - https://open.library.ubc.ca/collections/24/items/1.0066799
ER - End of Reference