<< plq_co plq plq_coSplit >>

CCA (Computational Convex Analysis) >> plq > plq_coDirect

plq_coDirect

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

Calling Sequence

[plqco,iters] = plq_coDirect(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.

iters

Numerial Value. Number of iterations it took in computation

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 performs a left-to-right plane sweep, examining two adjacent pieces at a time. It convexifies two pieces, and moves rightward, adding to the "current convex hull" to the left of the index, or backtracks if convexity was broken at a point. This algorithm runs in linear time, as each iteration either moves rightward, backtracks and merges two pieces, or backtracks without merging, but this can happen at most a linear number of times.

A special case is when three adjacent pieces are quadratic, linear, and quadratic, each quadratic piece contains the vertex of the quadratic, and a linear piece which is not the convex hull is between. To prevent cycling convergent behaviour, the linear piece is directly replaced with the convex hull of the two quadratic pieces.

Examples

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

// The hull of a more complicated function:
plqf =[-3,1,8,16;0,0,-1,-2;3,0,1,-2;%inf,1,-8,16];
result = plq_coDirect(plqf),
scf(); plq_plot(plqf, result);

See Also

Authors

Bryan Gardiner, University of British Columbia, BC, Canada

Used Functions

_plq_conv_on_interval is used to ensure that pieces of a function are convex on an interval.


Report an issue
<< plq_co plq plq_coSplit >>