<< plq_coDirect plq plq_deconv_lft >>

CCA (Computational Convex Analysis) >> plq > plq_coSplit

plq_coSplit

Piecewise linear quadratic (plq), Convex hull (splitting algorithm)

Calling Sequence

plqco = plq_coSplit(plqf)

Parameters

plqf

matrix. A plq function whose convex hull will be computed.

plqco

matrix. A plq function that is the convex hull of the original function.

Description

Computes the convex hull of a continuous, but not necessarily convex, plq function, where the input and output are given in the form of a plq matrix.

This algorithm works by reformulating the convex hull of f as

where co represents the convex hull, max/min are functions that are the pointwise minima and maxima of their arguments, * is the convex conjugate, and each g_i is defined via

plq_coSplit requires worst-case quadratic time, and best-case linear time. g_i* require O(1) work, but the model may grow as its maximum is computed with each g_i*, so the max takes O(n^2) time to compute, where n is the number of points stored in f's GPH matrix. The final conjugate is a linear operation.

Examples

// The hull of a linear-linear-quadratic function:
plqf = [0,0,0,%inf; 1,0,-1,1; 2,0,1,-1; 3,0,-1,3; 4,0,1,-3; %inf,0,0,%inf];
result = plq_coSplit(plqf),
scf(); plq_plotMultiple(%f, %f, plqf, result);

// The hull of a more complicated function:
plqf = [-3,1,8,16;0,0,1,4;3,0,-1,4;%inf,1,-8,16];
result = plq_coSplit(plqf),
scf(); plq_plotMultiple(%f, %f, plqf, result);

See Also

Authors

Bryan Gardiner, University of British Columbia, BC, Canada

Bibliography


Report an issue
<< plq_coDirect plq plq_deconv_lft >>