<< 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

- plq_co
- plq_coDirect
- plq_function

### Authors

`Bryan Gardiner`, University of British Columbia, BC, Canada

### Bibliography

- B. Gardiner, Y. Lucet, Submitted February 2010, Convex Hull Algorithms for Piecewise Linear-Quadratic Functions in Computational Convex Analysis.

<< plq_coDirect | plq | plq_deconv_lft >>