Name

fusion — [Internal function] Merge 2 increasing sequences using classical programming; used to compute the Legendre-Fenchel conjugate.

Calling Sequence

fH = fusion(C,S)

Parameters

C

Column vector. C(i) = (f(X(i+1) - f(X(i)) / (X(i+1) - X(i)) for some function f on a grid X.

S

Column vector. The grid on which we want to compute the conjugate: f* is evaluated on S.

fH

Column vector. Index at which the slope S(i) support the epigraph.

Description

  • Calling fusion(C,S) gives the resulting indices fH(j) where the slope S(j) supports the epigraph of the underlying function f. All in all, it amounts to finding the first index i such that C(i-1) <=S(j) < C(i).

  • This function uses classical programming i.e. loops to guarantee a linear worst-case running time. See fusionsci for a scilab specific implementation.

  • This function is not intended to be used directly but to be called during the computation of the conjugate using the LLT algorithm by the function pl_lft_llt.

Examples

    X=[-5:0.5:5]';
    Y=X.^2;
    C=(Y(2:size(Y,1))-Y(1:size(Y,1)-1))./(X(2:size(X,1))-X(1:size(X,1)-1));
    S=C-0.25*ones(size(C, 1));
    [fH]=fusion(C,S)
  

See Also

fusionsci , pl_lft_llt

Authors

Yves Lucet, University of British Columbia, BC, Canada