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

Author

Yves Lucet, University of British Columbia, BC, Canada